Non-clairvoyant speed scaling for batched parallel jobs on multiprocessors
Hongyang Sun, Yangjie Cao, Wen-Jing Hsu · 2009
Energy consumption and heat dissipation have become key considerations for modern high performance computer systems. In this paper, we focus on non-clairvoyant speed scaling to minimize flow time plus energy for batched parallel jobs on multiprocessors. We consider a common scenario where the total power consumption cannot exceed a given budget and the power consumed on each processor is sα when running at speed s. Extending the EQUI processor allocation policy, we propose two algorithms: U-EQUI and N-EQUI, which use respectively a uniform-speed and a non-uniform speed scaling function for the allocated processors. Using competitive analysis, we show that U-EQUI is O(Pα-1)/α2)-competitive for flow time plus energy, and N-EQUI is O(α√lnP)-competitive for the same metric when given sufficient power, where P is the total number of processors. Our simulation results confirm that U-EQUI and N-EQUI achieve better performance than a straightforward fixed-speed EQUI strategy. Moreover, moderate power constraint does not significantly affect the performance of our algorithms.