SpringerLink - Journal Article

A dominant predecessor duplication scheduling algorithm for heterogeneous systems

Kuan-Chou Lai¹ and Chao-Tung Yang²

(1)	Department of Computer and Information Science, National Taichung University, Taichung, 40302, Taiwan

(2)	Department of Computer Science and Information Engineering, Tunghai University, Taichung, 40704, Taiwan

Received: 20 February 2007 Accepted: 13 August 2007 Published online: 29 September 2007

Abstract This paper proposes a new duplication-based task scheduling algorithm for distributed heterogeneous computing (DHC) systems. For such systems, many researchers have focused on solving the NP-complete problem of scheduling directed acyclic task graphs to minimize the makespan. However, the heterogeneity of computational resources and communication mechanisms poses some major obstacles to achieving high parallel efficiency. This paper proposes a heuristic strategy called the Dominant Predecessor Duplication (DPD) scheduling algorithm, which allows for system heterogeneities and communication bandwidth to exploit the potential of parallel processing. This algorithm can improve system utilization and avoid redundant resource consumption, resulting in better schedules. Experimental results show that the system heterogeneities and program structures of applications affect scheduling performance, and that our presented algorithm is better able to avoid these problems than those presented in previous literature. Here, we show that our algorithm can be applied to design efficient distributed systems to overcome performance bottlenecks caused by system heterogeneities.

Keywords Directed acyclic graph - Heterogeneity - Duplication - Task scheduling - Distributed computing

Kuan-Chou Lai (Corresponding author)
Email: kclai@mail.ntcu.edu.tw

Chao-Tung Yang
Email: ctyang@thu.edu.tw

Kuan-Chou Lai

MediaObjects/11227_2007_152_Figa_HTML.jpg

received his MS degree in computer science and information engineering from the National Cheng Kung University in 1991, and the PhD degree in computer science and information engineering from the National Chiao Tung University in 1996. Currently, he is an assistant professor in the Department of Computer and Information Science at the National Taichung University. His research interests include parallel processing, heterogeneous computing, system architecture, grid computing, and multimedia systems. He is a member of the IEEE and the IEEE Computer Society.

Chao-Tung Yang

MediaObjects/11227_2007_152_Figb_HTML.jpg

received a BS degree in computer science and information engineering from Tunghai University, Taichung, Taiwan in 1990, and the MS degree in computer and information science from National Chiao Tung University, Hsinchu, Taiwan in 1992. He received the PhD degree in computer and information science from National Chiao Tung University in July 1996. He won the 1996 Acer Dragon Award for outstanding PhD Dissertation. He has worked as an associate researcher for ground operations in the ROCSAT Ground System Section (RGS) of the National Space Program Office (NSPO) in Hsinchu Science-based Industrial Park since 1996. In August 2001, he joined the faculty of the Department of Computer Science and Information Engineering at Tunghai University, where he is currently an associate professor. His researches have been sponsored by Taiwan agencies National Science Council (NSC), National Center for High Performance Computing (NCHC), and Ministry of Education. His present research interests are in grid and cluster computing, parallel and high-performance computing, and internet-based applications. He is both member of the IEEE Computer Society and ACM.

A dominant predecessor duplication scheduling algorithm for heterogeneous systems

Fulltext Preview (Small, Large)