|
Published Articles >> Table of Contents >> Abstract
International Parallel and Distributed Processing Symposium (IPDPS'03)
p. 6b
Task Clustering and Scheduling to Multiprocessors with Duplication
Li Guodong, Nanjing University
Chen Daoxu, Nanjing University
Wang Daming, Nanjing University
Zhang Defu, Nanjing University
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IPDPS.2003.1213079
Send link to a friend
| Abstract |
|
Optimal task-duplication-based scheduling of tasks represented by a directed acyclic graph (DAG) onto a set of homogenous distributed memory processors, is a strong NP-hard problem. In this paper we present a clustering and scheduling algorithm with time complexity 0(v3logv), where v is the number of nodes, which is able to generate optimal schedule for some specific DAGs. For arbitrary DAGs, the schedule generated is at most two times as the optimal one. Simulation results show that the performance of TCSD is superb to those of four renowned algorithms: PY, TDS, TCS and CPFD.
|
 Additional Information
|
Citation:
Li Guodong, Chen Daoxu, Wang Daming, Zhang Defu,
"Task Clustering and Scheduling to Multiprocessors with Duplication,"
ipdps,
p. 6b,
International Parallel and Distributed Processing Symposium (IPDPS'03),
2003
|
|
