Project
Optimal Task Scheduling for Parallel Systems
Optimal solutions to NP-hard scheduling of task graphs with communication delays on parallel processors. Supported by the Marsden Fund.
For the performance and efficiency of a parallel program running on a parallel system, the scheduling of its (sub)tasks is crucial. Unfortunately, scheduling is a fundamental unsolved problem — an NP-hard optimisation problem — as the time needed to solve it optimally grows exponentially with the number of tasks.
This overarching project is dedicated to the optimal solution of these NP-hard scheduling problems for small to medium-sized instances. The problem addressed is optimally scheduling task graphs with communication delays on parallel processors. It consists of several sub-projects, listed below.
This project is supported by the Marsden Fund “Optimal Task Scheduling for Parallel Systems.” Most implementations and resources are available for download.
Green Banana — ILP-based task scheduling solver
Supplies an optimal task scheduler for (homogeneous) multiprocessor systems with communication delays. A suite of Mixed Integer Linear Programming (MILP) formulations solves the scheduling problem using the CPLEX Optimisation Solver.
Kauri — Search-based Optimal Scheduling Library
Tackles the optimal scheduling of task graphs with branch-and-bound state-space search algorithms such as A*.
Optimal Schedules Database
A database of optimal schedules for a large set of small to medium-sized task graphs, produced for different numbers of processors. Intended to help researchers and practitioners verify the quality of scheduling heuristics.
Task Scheduling Eclipse Plugin
An Eclipse plugin to visualise and manipulate task schedules and their corresponding task graphs. Features include detailed examination of schedules, manual adjustments, duplication of tasks, and export functions.
About · Download · Screenshots