DocumentCode
2062142
Title
A scheduling algorithm for an out-tree DAG
Author
Liu, Zhenying ; Fang, Binxing ; Zhang, Yi ; Tang, Jianqi
Author_Institution
Dept. of Comput. Sci. & Eng., Harbin Inst. of Technol., China
Volume
1
fYear
2000
fDate
14-17 May 2000
Firstpage
327
Abstract
An effective scheduling algorithm is key to achieving high performance. This paper presents an algorithm based on task duplication to schedule an out-tree task graph which represents a number of divide-and-conquer algorithms. The scheduling algorithm has the shortest possible scheduling length and economizes the processors with O(|e|/spl middot/|/spl nu/|/sup 2/) complexity. Moreover, it also outperforms the CPFD (critical-path fast duplication) and TDS (task duplication-based scheduling) algorithms.
Keywords
computational complexity; directed graphs; divide and conquer methods; parallel algorithms; processor scheduling; trees (mathematics); CPFD algorithm; NP-complete problem; TDS algorithm; complexity; critical-path fast duplication; divide-and-conquer algorithms; out-tree directed acyclic graph; out-tree task graph; performance; processor economy; scheduling algorithm; scheduling length; task duplication; task duplication-based scheduling;
fLanguage
English
Publisher
ieee
Conference_Titel
High Performance Computing in the Asia-Pacific Region, 2000. Proceedings. The Fourth International Conference/Exhibition on
Conference_Location
Beijing, China
Print_ISBN
0-7695-0589-2
Type
conf
DOI
10.1109/HPC.2000.846571
Filename
846571
Link To Document