2003 International Conference on Parallel Processing Workshops (ICPPW'03)
Scheduling Directed A-cyclic Task Graphs on Heterogeneous Network of Workstations to Minimize Schedule Length
Kaohsiung, Taiwan
October 06-October 09
ISBN: 0-7695-2018-9
We evaluate the performance of a non-preemptive heuristic algorithm called Heterogeneous Critical Node First (HCNF) that statically schedules directed a-cyclic task graphs on heterogeneous multiprocessor systems to minimize the makespan. Using simulations on real applications and benchmark graphs we show that HCNF outperforms HEFT significantly in schedule length ratio, speedup and efficiency. Schedule length ratio is the ratio of the parallel time to the sum of weights of the critical path tasks on the fastest processor. Speedup is the ratio of the sequential execution time to the parallel execution time. Efficiency is the ratio of the Speedup to the no. of processors.
Index Terms:
DAG, scheduling, task graph, heterogeneous computing, makespan
Citation:
Sanjeev Baskiyar, Prashanth C. SaiRanga, "Scheduling Directed A-cyclic Task Graphs on Heterogeneous Network of Workstations to Minimize Schedule Length," icppw, pp.97, 2003 International Conference on Parallel Processing Workshops (ICPPW'03), 2003