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
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;
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
DOI :
10.1109/HPC.2000.846571
