We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A dominant predecessor duplication scheduling algorithm for heterogeneous systems.
- Authors
Lai, Kuan-Chou; Yang, Chao-Tung
- 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.
- Subjects
ALGORITHMS; NP-complete problems; HETEROGENEOUS computing; HIGH performance computing; DISTRIBUTED computing; DATA transmission systems; HETEROGENEITY; EXPERIMENTAL mathematics; HETEROGENEOUS distributed computing
- Publication
Journal of Supercomputing, 2008, Vol 44, Issue 2, p126
- ISSN
0920-8542
- Publication type
Article
- DOI
10.1007/s11227-007-0152-2