Optimal Task Scheduling for Parallel Systems
Overview
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 instanced. The problem addressed is the problem of optimally scheduling Task Graphs with Communication Delays on Parallel Processors. It consists of several sub-projects as listed below.
This project is supported by the Marsden fund "Optimal Task Scheduling for Parallel Systems".
Most of the implementations and resources are provided for download.
Green Banana -- ILP based task scheduling solver
This research project supplies an optimal task scheduler for (homogeneous) multiprocessor systems with communication delays. A suite of Mixed Integer Linear Programming (MILP) formulations are supplied to solve the scheduling problem using the CPLEX Optimisation Solver.
In this project the optimal scheduling of task graphs is tackled with branch-and-bound state-space search algorithms such as A*.
This project is the creation of a data base of optimal schedules for a large set of small to medium sized task graphs. The schedules are produced for different numbers of processors. Our hope is that this database can be useful for researchers and practitioners, in particular to verify the quality of scheduling heuristics.
Developed as a plugin for Eclipse, this tool allows to visualise and manipulate task schedules and their corresponding task graphs. Features include the detailed examination of schedules, manual adjustments, duplication of tasks, export functions etc.