Optimal Task Scheduling · Kauri

Kauri — Search-Based Optimal Task Scheduling Framework

Kauri finds optimal solutions to task scheduling problems in parallel computing using state-space search. It supports several search algorithms — including A* and Depth-First Branch-and-Bound — applied to a number of task scheduling models, using the Allocation-Ordering state-space (or the older Exhaustive List Scheduling state-space) with various options.

In the α|β|γ notation of scheduling problems, Kauri can solve P|prec,c_ij|C_max (incl. P||C_max) and Q|prec,c_ij|C_max — scheduling tasks with computation costs and precedence constraints with communication delay on homogeneous or related heterogeneous processors, minimising the makespan.

Installation

Kauri is available for download in executable JAR format.

License

The executable JAR is free to use for research, teaching, personal, and other non-commercial purposes. Contact Oliver Sinnen (o.sinnen@auckland.ac.nz) for other licenses, collaboration, or queries.

Usage

Run from the command line:

java <java_options> -jar path/to/jar SCHEDULER STATE_SPACE TASK_GRAPH_FILE TARGET_SYSTEM [OPTIONS]

A useful Java option is -mx, which sets the JVM’s maximum heap size (e.g. -mx64G). Required parameters:

  • SCHEDULER — class name of the scheduler to use.
  • STATE_SPACE — class name of the state space to use.
  • TASK_GRAPH_FILE — the input task graph (GXL or DOT format).
  • TARGET_SYSTEM — the target system (an integer number of homogeneous processors, or a path to a DOT file).

A typical invocation:

java -mx96G -jar path/to/jar AStarScheduler AOStateSpace \
  inputExamples/graphs/Join_Nodes_10_CCR_0.1_WeightType_Random.gxl \
  inputExamples/targetSystems/Homogeneous-2.dot -o out.gxl -timeout 60000 -aoDefaults

State-spaces

  • AOStateSpace — Allocation-Ordering model, a duplicate-free state-space for scheduling with communication delays. Recommended. Allows homogeneous or related heterogeneous processors, and task duplication.
  • ELSStateSpace — Exhaustive List Scheduling, an older model. Allows homogeneous or related heterogeneous processors.

Schedulers

  • AStarScheduler — A* best-first search; can use a closed list for duplicate detection (very memory-hungry).
  • DFBnBScheduler — Depth-First Branch-and-Bound; low memory requirement.
  • parallel.DFSParallelScheduler — parallel DFBnB.
  • parallel.MultiQueueParallelScheduler — parallel A*.
  • RBFSScheduler — Recursive Best-First Search.

Options

Kauri accepts many optional parameters. The convenience flags -aoDefaults and -elsDefaults set sensible defaults for the AO and ELS state-spaces respectively:

-aoDefaults  = -nodeEquivalence -fixedOrder -bestSLOpt2 -reverseJoin
               -topoOrderedTasks -orderingEdges -loadWithAllIdle

-elsDefaults = -pi -norm -nodeEquivalence -pruneES -fixedOrder -bestSLOpt2
               -drt -useNewF -reverseJoin -topoOrderedTasks
               -sortreadylistIndex -partial -closed

Other options include -allowDuplication, -closed, -o VAL (output path), -threads N, -timeout N (default 600000 ms), -v N (verbosity 1–3), -workStealing, and many pruning and f-value flags. Run Kauri with no arguments to see the full list.

Main contributors

Michael Orr, Oliver Sinnen, Ahmed Zaki Semar Shahul.

References

  1. M. Orr and O. Sinnen. Integrating Task Duplication in Optimal Task Scheduling with Communication Delays. IEEE TPDS, 2020. 10.1109/TPDS.2020.2989767
  2. M. Orr and O. Sinnen. Optimal Task Scheduling Benefits From a Duplicate-Free State-Space. arXiv 1901.06899, 2019.
  3. M. Orr and O. Sinnen. Parallel and Memory-limited Algorithms for Optimal Task Scheduling Using a Duplicate-Free State-Space. arXiv 1905.05568, 2019.
  4. M. Orr and O. Sinnen. Further explorations in state-space search for optimal task scheduling. HiPC 2017, pp. 134–141. IEEE. 10.1109/HiPC.2017.00024
  5. S. Venugopalan and O. Sinnen. Memory Limited Algorithms for Optimal Task Scheduling on Parallel Systems. JPDC, 2016. 10.1016/j.jpdc.2016.03.003
  6. M. Orr and O. Sinnen. A duplicate-free state-space model for optimal task scheduling. Euro-Par 2015, LNCS 9233. Springer. 10.1007/978-3-662-48096-0_8
  7. O. Sinnen. Reducing the solution space of optimal task scheduling. Computers & OR 43: 201–214, 2014. 10.1016/j.cor.2013.09.004