Kauri - Search-Based Optimal Task Scheduling Framework

Kauri is a tool for finding optimal solutions to task scheduling problems in parallel computing using state-space search. It supports various search algorithms, including A* and Depth-first Branch-and-Bound. These algorithms can be applied to a number of task scheduling models - using the Allocation-Ordering state-space (or older Exhaustive List Scheduling state-space) with various options.

In terms of the alpha|beta|gamma notation of scheduling problems, Kauri can solve P|prec,c_ij|C_max (inc. P||C_max) and Q|prec,c_ij|C_max, which means scheduling of tasks with computation costs and precedence constraints with communication delay on homogeneous processors or related heterogeneous processors, while minimising the makespan.

Installation

Kauri is available for download here in executable JAR format.

License

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

Usage

Kauri should be run from the command line using the following format:

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 for a 64 GB heap.

The required parameters are as follows:

  • SCHEDULER: class name of scheduler to use.
  • STATE_SPACE: class name of state space to use.
  • TASK_GRAPH_FILE: Name of the input task graph (gxl or dot format).
  • TARGET_SYSTEM: target system on which to schedule the input graph (INTEGER number of homogeneous processors or STRING path to dot format file).

A typical invocation looks like this:

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

The available options for the STATE_SPACE parameter are:

  • AOStateSpace: Allocation-Ordering (AO) Model - A duplicate-free state-space model for task scheduling with communication delays. Recommended.
    • Allows homogeneous or related heterogeneous processors.
    • Allows task duplication.
  • ELSStateSpace: Exhaustive List Scheduling (ELS) Model - Older state-space model for task scheduling with communication delays.
    • Allows homogeneous or related heterogeneous processors.

Schedulers

The available options for the SCHEDULER parameter are:

  • AStarScheduler: A* - Best-first search, allows the use of a closed list for duplicate detection. (Very memory hungry -- allocate large heap.)
  • DFBnBScheduler: DFBnB - Depth-First Branch-and-Bound, low memory requirement.
  • parallel.DFSParallelScheduler: PDFS - Parallel DFBnB
  • parallel.MultiQueueParallelScheduler: PA* - Parallel A*
  • RBFSScheduler: RBFS - Recursive Best-First Search

Options

Kauri can be run with the following optional parameters:

 -allowDuplication   : allow tasks to be duplicated in AO (default: false)
 -aoDefaults         : Set default options for running with AO
 -bestSLOpt          : heuristic schedule pruning. DEPRECATED (default: false)
 -bestSLOpt2         : updated heuristic schedule pruning (default: false)
 -closed             : use closed list (if scheduler permits) (default: false)
 -critPathWithLoad   : use crit path with load bound for alloc (AO) (default: false)
 -debug              : debug mode (default: false)
 -drt                : DRT f-value (ELS) (default: false)
 -elsDefaults        : Set default options for running with ELS
 -est                : EST f-value (ELS) (default: false)
 -estPartial         : EST partial f-value (ELS) (default: false)
 -fValueHistory      : Log when new f-values are reached (default: false)
 -fixedOrder         : fixed order pruning (default: false)
 -improveSchedule    : attempt to improve a given schedule (default: false)
 -loadWithAllIdle    : use proc load with all idle times for alloc (AO) (default: false)
 -loadWithBothLevels : use proc load with top and bottom levels for alloc (AO) (default: false)
 -logStealing        : log work stealing events (default: false)
 -ls                 : use list schedule heuristic. DEPRECATED (default: false)
 -nodeEqualProc      : prune equivalent tasks processors (default: false)
 -nodeEquivalence    : prune equivalent tasks (default: false)
 -norm               : normalise processors (ELS) - homogeneous processors only (default: false)
 -normHighProc       : prune normalise highest processor (default: false)
 -o VAL              : Desired path to write schedule output file.
 -orderingEdges      : use ordering edges in AO (default: false)
 -paperF             : paper f-value (ELS) (default: false)
 -partial            : use partial expansion (if statespace permits) (default: false)
 -pi                 : prune isomorphic processors (ELS) - homogeneous processors only (default: false)
 -pruneES            : prune equivalent schedules (default: false)
 -reverseJoin        : reverse join and in-tree graphs (default: false)
 -sortreadylist      : sort ready list (default: false)
 -sortreadylistIndex : sorted ready list index (default: false)
 -threads N          : number of threads for parallel scheduler (default: 1)
 -timeout N          : time limit for solver (default: 600000)
 -topoOrderedTasks   : topologically order task indices (default: false)
 -useHeuristicSuite  : use full suite of heuristics to find upper bound - not compatible with
                       duplication or heterogeneous processors (default: false)
 -useNewF            : new f-value (ELS) (default: false)
 -v N                : output verbosity level: 1-3 (default: 0)
 -workStealing       : use work stealing (if scheduler permits) (default: false)

The -aoDefaults option is equivalent to:

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

The -elsDefaults option is equivalent to:

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

Main Contributors

  • Michael Orr
  • Oliver Sinnen
  • Ahmed Zaki Semar Shahul

Reference

  1. M. Orr and O. Sinnen, "Integrating Task Duplication in Optimal Task Scheduling with Communication Delays," in IEEE Transactions on Parallel and Distributed Systems, 2020. 10.1109/TPDS.2020.2989767
  2. Michael Orr and Oliver Sinnen. Optimal Task Scheduling Benefits From a Duplicate-Free State-Space. arXiv e-prints, arXiv:1901.06899 , 2019.
  3. Michael Orr and Oliver Sinnen. Parallel and Memory-limited Algorithms for Optimal Task Scheduling Using a Duplicate-Free State-Space. arXiv e-prints, arXiv:1905.05568, 2019.
  4. Michael Orr and Oliver Sinnen. Further explorations in state-space search for optimal task scheduling. In 2017 IEEE 24th International Conference on High Performance Computing (HiPC), pages 134141. IEEE, 2017. 10.1109/HiPC.2017.00024
  5. Sarad Venugopalan and Oliver Sinnen. Memory Limited Algorithms for Optimal Task Scheduling on Parallel Systems. Journal of Parallel and Distributed Computing, 2016. 10.1016/j.jpdc.2016.03.003
  6. M. Orr and O. Sinnen. A duplicate-free state-space model for optimal task cheduling. In Proc. of 21st Int. European Conference on Parallel and Distributed omputing (Euro-Par 2015), volume 9233 of Lecture Notes in Computer Science, Vienna, Austria, 2015. Springer. 10.1007/978-3-662-48096-0_8
  7. Oliver Sinnen, Reducing the solution space of optimal task scheduling.Computers & OR 43: 201-214 (2014). 10.1016/j.cor.2013.09.004