Kauri Library

Kauri is an extensible framework for optimal task scheduling with branch-and-bound state-space search. It allows optimal scheduling with a number of state-space models, using a number of search algorithms.

State-Space Models

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

Search Algorithms

  • A*
  • DFBnB - Depth-First Branch-and-Bound
  • IDA* - Iterative Deepening A*
  • RBFS - Recursive Best-First Search
  • PA* - Parallel A*
  • PDFS - Parallel DFBnB

Reference

  1. 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.
  2. 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.
  3. Michael Orr and Oliver Sinnen. Optimal Task Scheduling Benefits From a Duplicate-Free State-Space. arXiv e-prints, page arXiv:1901.06899, 2019.
  4. Michael Orr and Oliver Sinnen. Parallel and Memory-limited Algorithms for Optimal Task Scheduling Using a Duplicate-Free State-Space. arXiv e-prints, page arXiv:1905.05568, 2019.
  5. Sarad Venugopalan and Oliver Sinnen. Memory Limited Algorithms for Optimal Task Scheduling on Parallel Systems. Submitted to Journal of Parallel and Distributed Computing.
  6. Oliver Sinnen, Reducing the solution space of optimal task scheduling.Computers & OR 43: 201-214 (2014).