Efficient Critical Task Scheduling Parallel Programs on a Bounded Number of Processors

M. Hakem and F. Butelle (France)


scheduling, clustering, distributed computing, precedence task graphs, directed acyclic graphs DAGs, parallel scheduling.


In this paper, we present an efficient algorithm for compile time scheduling of parallel programs on a bounded num ber of processors system with distributed memory. Our algorithm (CTS Critical Task Scheduling) is a greedy list scheduling heuristics based on attribute priority called Task Criticalness wich provides a good measure of the task im portance. CTS has a time complexity of O(ep + v log v) which is better than all the others scheduling algorithms to our knowledge. Experimental results also demonstrate the superiority of CTS over the other algorithms in terms of speed and solution quality.

Important Links:

Go Back