Task clustering and scheduling to multiprocessors with duplication

Author

Guodong, Li ; Daoxu, Chen ; Wang Daming ; Defu, Zhang

Author_Institution

Dept. of Comput. Sci., Nanjing Univ., China

fYear

2003

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 O(v³logv), where v is the number of nodes, which is able to generate an optimal schedule for some specific DAG. For arbitrary DAG, the schedule generated is at most two times as the optimal one. Simulation results show that the performance of TCSD is superb compared to those of four renowned algorithms: PY TDS, TCS and CPFD.

Keywords

computational complexity; directed graphs; distributed memory systems; parallel programming; performance evaluation; processor scheduling; DAG; NP-hard problem; clustering algorithm; directed acyclic graph; homogenous distributed memory processors; multiprocessor scheduling; optimal schedule; optimal task-duplication; performance; task clustering; time complexity; Clustering algorithms; Computational efficiency; Computer science; Costs; Heuristic algorithms; NP-hard problem; Optimal scheduling; Processor scheduling; Scheduling algorithm; Search methods;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Processing Symposium, 2003. Proceedings. International

ISSN

1530-2075

Print_ISBN

0-7695-1926-1

Type

conf

DOI

10.1109/IPDPS.2003.1213079

Filename

1213079