An Energy-Efficient Load Balancing Scheme in Heterogeneous Clusters by Linear Programming

The growing power consumption of heterogeneous clusters has attracted great interests from both academia and industry. Although there have been extensive studies on energy-efficient task scheduling algorithms to address this problem, most of them are task-centric. However, as a task is fine-grained enough, the scheduling algorithm can put more efforts on utilizing different power characteristics of heterogeneous servers, which has not been fully explored. This paper presents a Linear Programming-based Energy-efficient Load Balancing (LP-ELB) scheme for heteroge-neous clusters. The power model of each sever in the cluster is obtained in advance, and the overall optimization problem is formulated as a mixed integer linear programming problem. LP-ELB tackles this problem through a two-phase heuristic: a server selection phase for choosing a minimal set of servers, and a load partition phase for calculating load distribution. An optimal solution to the relaxed problem in the second phase can be provided finally. Experiments on both simulated and real-world testbeds validate the effectiveness of the proposed method, and reveal that LP-ELB is superior to competitor algorithms, such as Round-Robin and power-aware Weighted Round-Robin.