Energy-Efficient Duplication Strategies for Scheduling Precedence Constrained Parallel Tasks on Clusters

Ziliang Zong, Adam Manzanares, Brian Stinar, and Xiao Qin*

Department of Computer Science

New Mexico Institute of Mining and Technology

801 Leroy Place, Socorro, New Mexico 87801-4796

{zzong, amanzana, bstinar, xqin}@cs.nmt.edu

Optimizing energy consumption has become a major concern in designing economical clusters. Scheduling precedence-constrained parallel tasks on clusters is challenging because of high communication overhead. Although duplication-based strategies are applied to minimize communication overhead, most of them merely consider schedule lengths, completely ignoring energy consumption of clusters. In this regard, we propose two energy-aware duplication scheduling algorithms, called EADUS and TEBUS, to schedule precedence-constrained parallel tasks. Unlike existing duplication-based scheduling algorithms that replicate all possible predecessors of each task, the proposed algorithms judiciously replicate predecessors only if the duplication can help in conserving energy. Our energy-aware scheduling strategies are conducive to balancing the scheduling length and energy consumption of precedence-constrained parallel tasks. Extensive experimental results based on real-world applications demonstrate the effectiveness and practicality of the proposed scheduling strategies.

Proceedings of the 8th IEEE International Conference on Cluster Computing (Cluster 2006), Sept. 2006.

* Corresponding author.  http://www.cs.nmt.edu/~xqin

---