Scheduling task graphs optimally with A* |
| |
Authors: | Ahmed Zaki Semar Shahul Oliver Sinnen |
| |
Affiliation: | 1.Department of Electrical and Computer Engineering,University of Auckland,Auckland,New Zealand |
| |
Abstract: | Scheduling tasks onto the processors of a parallel system is a crucial part of program parallelisation. Due to the NP-hard
nature of the task scheduling problem, scheduling algorithms are based on heuristics that try to produce good rather than
optimal schedules. Nevertheless, in certain situations it is desirable to have optimal schedules, for example for time-critical
systems or to evaluate scheduling heuristics. This paper investigates the task scheduling problem using the A* search algorithm
which is a best-first state space search. The adaptation of the A* search algorithm for the task scheduling problem is referred
to as the A* scheduling algorithm. The A* scheduling algorithm can produce optimal schedules in reasonable time for small
to medium sized task graphs with several tens of nodes. In comparison to a previous approach, the here presented A* scheduling
algorithm has a significantly reduced search space due to a much improved consistent and admissible cost function f(s) and additional pruning techniques. Experimental results show that the cost function and the various pruning techniques are
very effective for the workload. Last but not least, the results show that the proposed A* scheduling algorithm significantly
outperforms the previous approach. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|