O. Sinnen, A.V. Kozlov, and A.Z.S. Shahul (New Zealand)
Scheduling, task graphs, optimal schedules, A*
Scheduling tasks onto the processors of a parallel system is a crucial part of program parallelisation. Due to the NP hardness of the task scheduling problem, scheduling al gorithms are based on heuristics that try to produce good rather than optimal schedules. Nevertheless, in certain situ ations it is desirable to have optimal schedules, for example for time critical systems or to evaluate scheduling heuris tics. This paper proposes a scheduling algorithm based on A* that can produce optimal schedules in reasonable time for small task graphs. A* is a best-first state space search algorithm. In comparison to a previous approach, the here presented scheduling algorithm has a significantly reduced search space due to a much improved cost function f(s) and additional pruning techniques. Experimental results re veal the relation between the runtime of the algorithm and the structure of the task graphs. Further, it is shown that the proposed algorithm significantly outperforms the previous approach.
Important Links:
Go Back
