U. Hönig and W. Schiffmann (Germany)
Task Graph Scheduling, Optimal Schedules, Test Bench
Computational problems can usually be divided into a number of (sub)tasks. The data dependencies between these tasks can be described by a so called task graph. Since the task graph scheduling problem is known to be NP-hard, researchers devised an innumerable number of heuristic algorithms to solve this problem best. Up to now, these heuristics were analyzed by using a set of task graph problems, which were rarely revealed to the public. A com parison of different scheduling algorithms presupposes the availability of their implementations. Our contribution con sists of a test bench with 36000 task graph problems and their optimal solutions with respect to homogeneous target architectures. These test cases are structured according to several task graph properties and target architectures' sizes and enable researchers to analyze the overall quality of their heuristics' results, to detect strengths and weaknesses of their algorithms and to compare them with those of other researchers. We used the current intermediary version of this test bench to compare some well known scheduling al gorithms, namely DLS [1], ETF [2], HLFET [3] and MCP [4]. Surprisingly, the heuristics show a very similar behav ior regarding the quality of the obtained results, exhibiting the same strengths and weaknesses, differing only by few percent.
Important Links:
Go Back
