loading...
Performance Effective Task Scheduling Algorithm for Heterogeneous Computing System
Universit? of Lille 1, France July 04-July 06
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPDC.2005.39The 4th International Symposium on Pa ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
E. Ilavarasan, Pondicherry Engineering College, India
P. Thambidurai, Pondicherry Engineering College, India
R. Mahilmannan, Pondicherry Engineering College, India
Finding an optimal solution to the problem of scheduling an application modeled by a Directed Acyclic Graph (DAG) onto a distributed system is known to be NP-complete. The complexity of the problem increases when task scheduling is to be done in a heterogeneous computing system, where the processors in the network may not be identical and take different amounts of time to execute the same task. This paper introduces a Performance Effective Task Scheduling (PETS) Algorithm for Network of Heterogeneous system, with complexity O (v+e) (p+ log v), which provides optimal results for applications represented by DAGs. The performance of the algorithm is illustrated by comparing the schedule length, speedup, efficiency and the scheduling time with existing algorithms such as, Heterogeneous Earliest Finish Time (HEFT) and Critical-Path On a processor (CPOP) and Levelized Min Time (LMT) reported in this paper. The comparison study based on both randomly generated graphs and graphs of some real applications shows that PETS algorithm substantially outperforms existing algorithms.
Citation:
E. Ilavarasan, P. Thambidurai, R. Mahilmannan, "Performance Effective Task Scheduling Algorithm for Heterogeneous Computing System," ispdc, pp.28-38, The 4th International Symposium on Parallel and Distributed Computing (ISPDC'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.