A Compile-time Task Scheduling Algorithm

T. Hagras and J. Janeček (Czech Republic)


list scheduling, compile time scheduling, task graph scheduling, homogeneous computing.


Task scheduling in homogeneous computing environments is the key issue for high performance. A large number of scheduling heuristics have been presented in the literature. List scheduling heuristics are generally more practical and provide better performance results at a lower scheduling time than the other classes of scheduling heuristics. This paper presents a compile-time list-scheduling algorithm. The algorithm consists of two phases: listing phase which is a simple listing heuristic, Critical Parent Trees (CPT), that has a performance comparable or even better than the other higher complexity heuristics using non-duplication machine selection, and machine assigning phase which is a low complexity duplication mechanism, Fast Duplicator (FD), that outperforms the other scheduling algorithms.

Important Links:

Go Back