loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
First International Conference on Distributed Frameworks for Multimedia Applications (DFMA'05)
Levelized Scheduling of Directed A-Cyclic Precedence Constrained Task Graphs onto Heterogeneous Computing System
Besan?on, France
February 06-February 09
ISBN: 0-7695-2273-4
E. Illvarasan, Pondicherry Engineering College, India
P. Thambidurai, Pondicherry Engineering College, India
Efficient scheduling of processes onto processors of a heterogeneous computing system has always been an important and challenging area of research. The scheduling problem has been shown to be NP-Complete in general cases as well as in several restricted cases. Because of its key importance, this problem has been extensively studied in the recent years and many algorithms for homogenous system and a few algorithms for heterogeneous system have been proposed in the literature. In this paper, we propose a new duplication based task scheduling algorithm, namely, Levelized Heavily Communicating Node First (LHCNF) that statically schedules directed a-cyclic precedence constrained task graphs (DAGs) onto heterogeneous computing system to minimize the schedule length or overall completion time of the application. The performance of the algorithm has been observed by its application to some practical DAGs, and by comparing it with other existing scheduling algorithms such as HEFT, LDBS1 and LDBS2 in terms of the schedule length and speedup. The comparison studies shows that LHCNF significantly outperforms HEFT, LDBS1 and LDBS2 in schedule length, speedup.
Citation:
E. Illvarasan, P. Thambidurai, "Levelized Scheduling of Directed A-Cyclic Precedence Constrained Task Graphs onto Heterogeneous Computing System," dfma, pp.262-269, First International Conference on Distributed Frameworks for Multimedia Applications (DFMA'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.