vog / prs

Tool for parallel reversal schedules

prs – Tool for parallel reversal schedules

This tool generates and analyzes parallel reversal schedules. It has been developed along with the diploma thesis

Parallel reversal schedules using more checkpoints than processors

to support the research. Most of what is formally described there, such as the profile algebra, is also implemented within this tool. Almost all schedule pictures and profiles of the thesis have been automatically generated by this tool. Also, the exhaustive search is implemented here.

The correctness of this program is secured by OCaml’s strict ML typesystem combined with a comprehensive set of unit tests. This allowed for fast refactoring, which enabled this tool to be developed simultaneously with the thesis, influencing each other.

Usage

If prs is called without any arguments, the list of commands is shown:

Usage:
prs s PROCESSES RESOURCES
prs sp PROCESSES RESOURCES
prs gen PROCESSES RESOURCES
prs tree TREE
prs tree_letters TREE
prs tree_search MAX_PROCESSES MAX_RESOURCES MAX_REACH
prs old_tree_search PROCESSES MAX_RESOURCES
prs ascii < PRIME_SCHEDULE
prs ascii_small < PRIME_SCHEDULE
prs fibers FIBERS
prs lp PROCESSES REACH
prs search MAX_PROCESSES MAX_RESOURCES
prs latex_tree TREE
prs latex_gen PROCESSES RESOURCES
prs latex_ps < PRIME_SCHEDULE
prs test

The command prs test runs all unit tests. prs search runs the exhaustive search as described in Section 4.2. prs gen generates the optimal respectively suboptimal schedules as defined in Chapter 4. The commands prs s and prs sp also generate those schedules, but have a less verbose output. Arbitrary binary-decomposable schedules can be analyzed with prs tree.

For example, prs gen 3 6 generates the optimal schedule for p=3,k=6, draws it in ASCII art, shows the tree structure (where e means ε) and shows the profiles (where -1@23 means -φ₂₃). Note that the ASCII art schedules are rotated by -90°.

 1  2  |\
 1  2  |.\
 1  2  |..\
 1  2  |...\
 1  3  |...|\
 1  3  |...|.\
 1  3  |...|..\
 1  4  |...|..|\
 1  4  |...|..|.\
 1  5  |...|..|.|\
 1  6  |...|..|.||\
 1  6  |...|..|.||.\
 2  6  |...|..|.|.\/
 3  6  |...|..|\.\/
 3  6  |...|\.|.\/
 3  6  |...||\.\/
 3  6  |\..||.\/
 3  6  ||\.|.\/
 3  6  |||\.\/
 2  5  |||.\/
 2  4  ||.\/
 2  3  |.\/
 2  2  .\/
 1  1  ./

 3  6  12

S     = (((((e,e),e),(e,e)),((e,e),e)),(((e,e),e),e))
procp = +1@0,+1@12,+1@13,-1@19,-1@23,-1@24
resp  = +2@0,+1@4,+1@7,+1@9,+1@10,-1@19,-1@20,-1@21,-1@22,-1@23,-1@24
reach = 12

Copyright

Copyright © 2015, Volker Diels-Grabsch

Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, provided that the above copyright notice and this permission notice appear in all copies.

THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

(ISC license)