loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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
Sanjeev Baskiyar, Auburn University, AL
Prashanth C. SaiRanga, Auburn University, AL
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
Usage of this product signifies your acceptance of the Terms of Use.