1. Introduction2. System Model3. The HAGEES AlgorithmFavorite predecessor of task viLatest allowable completion time of task viLatest allowable start time of task vi10. ReferencesGo BackHAGEES: A High Availability Guaranteed Energy Efficient Scheduling Algorithm for Homogeneous Clusters Ziliang Zong, Mais Nijim, Mohammed Alghamdi, Xiao Qin* Department of Computer Science New Mexico Institute of Mining and Technology Socorro, New Mexico 87801 { zzong, mais, alghamdi, xqin} @ nmt.edu Abstract High performance clusters play a vital role nowadays both in the industry and research area. In the past decade, some scheduling schemes have been investigated to achieve high availability or energy efficiency in large-scale clusters. However, leveraging scheduling algorithms to ensure high availability and performance while conserving energy remains an open problem. To bridge this technology gap, in this paper, we propose a high availability guaranteed energy efficient scheduling strategy (HAGEES for short) that aims at comprehensively consider the most important three factors, namely, availability, energy conservation, and high performance. 1. Introduction With the development of VLSI technology and high-speed networks, cluster systems have been widely used for a diverse set of parallel applications like molecular design, weather modeling and complex image rendering. However, drawbacks like tremendous energy consumption, lower availability always attack people’s confidence in further applying cluster systems to modern industry and scientific research applications. Energy consumption problems of clusters have been extensively researched by previously studies [1] [2]. The availability issue of cluster system was first presented in [3] and then further studied in [4] [6]. Duplication based strategy [5] was provided to balance the execution time and energy cost for homogeneous clusters in our previous research paper [7]. Although most existing scheduling strategies are conducive to achieving high availability or energy efficiency in large-scale clusters, leveraging scheduling algorithms to ensure high availability and performance while conserving energy remains an open problem. To bridge this technology gap, in this paper we propose a high availability guaranteed energy efficient scheduling strategy (HAGEES for short) that aims at comprehensively addressing the most important three factors, namely, availability, energy conservation, and high performance. 2. System Model A cluster system in this study is based on the Beowulf cluster model which has a set P = {p1, p2,..., pm} of computational nodes connected by high-speed interconnects (Fig.1). Homogeneous Fig.1 Homogeneous Beowulf cluster model It is assumed that the computational nodes are homogeneous, meaning that all the computing nodes are identical in their capabilities. Similarly, the underlying interconnection is assumed to be homogeneous and, thus, communication overhead of a message with fixed data size is considered to be the same. Computation and communication can take place simultaneously. This assumption is reasonable becauseeach computational node in a modern cluster has a communication coprocessor that can be used to free the processor in the node from communication tasks. The energy consumption experienced by a cluster can be expressed as: ELENE += (1) where EN is the energy consumption of computing nodes, and EL is the energy consumption of sending information through links. The energy consumption EN of computing node in Eq. (1) can be written as (). 11||1∑∑∑====⋅==niiniiViitPNtPNenEN (2) where eni is the energy consumption caused by node i, PN is the power of the node, and ti is the total execution time of tasks running on node i. The energy consumed by the interconnections is expressed as ∑∑=≠==mamabbabELEL1,1(∑∑∑∑=≠==≠=⋅⋅⋅=ninijjmamabbijjbiacPLxx1,11,1. ) (3) where ELab is the energy consumption of the link between nodes pa and pb. PL in Eq. (2) is the power of the link. Element xia is “1” if the ith task is assigned to node pa and is “0”, otherwise. cij is the communication cost. The availability of a computational node is quantified as the probability that all tasks allocated to the node can be successfully completed even in the presence of the node’s hardware and software faults. Availability of different computing nodes in our research is based on the analysis data from actual cluster systems. The higher availability a node has, the higher precedence a node will have to be allocated tasks for executing. 3. The HAGEES Algorithm To allocate tasks to different computing nodes, HAGEES will consider three factors in the order of availability, execution time and energy cost. HAGEES will always try to allocate tasks to nodes with the highest availability precedence and try to duplicate as more tasks as possible as long as these duplicated tasks will reduce execution time and will not increase energy consumption tremendously. Basically, the HAGEES algorithm has three phases to generate the final scheduling list. Phase1: Generate a task sequence HAGEES will construct an ordered task sequence using the concept of level, which of each task is defined as the length in computation time of the longest path from the task to the exit task. All the tasks are placed in a queue in an increasing order of the levels. Eq. (4) shows how to calculate the level of task i. ()⎪⎩⎪⎨⎧+Φ==∈otherwisetkleveltvLiisucckii )(max i)successor( if ,)()(43421 (4) Phase2: Calculate important parameters In this phase, HAGEES will calculate some important parameters, which the algorithm rely on. The important notation and parameters are listed in Table 1. Table 1. Important Notation and Parameters EST(vi) Earliest start time of task viECT(vi) Earliest completion time of task viFP(vi) Favorite predecessor of task viLACT(vi) Latest allowable completion time of task viLAST(vi) Latest allowable start time of task vi The earliest start times of all the other tasks can be calculated in a top-down manner by recursively applying the second term on the right side as follows. ()⎪⎩⎪⎨⎧⎟⎠⎞⎜⎝⎛+Φ==≠∈∈otherwise ,)(),(maxmin r(i)predecesso if ,0)(,kikjvvEeEeicvECTvECTvESTjkkiji The earliest completion time of task vi is expressed as the summation of its earliest start time and execution