Speed Scaling for Energy and Performance with Instantaneous Parallelism

Abstract. We consider energy-performance tradeoff for scheduling par-allel jobs on multiprocessors using dynamic speed scaling. The objective is to minimize the sum of energy consumption and certain performance metric, including makespan and total flow time. We focus on designing algorithms that are aware of the jobs ’ instantaneous parallelism but not their characteristics in the future. For total flow time plus energy, it is known that any algorithm that does not rely on instantaneous paral-lelism is Ω(ln1/α P)-competitive, where P is the total number of proces-sors. In this paper, we demonstrate the benefits of knowing instantaneous parallelism by presenting an O(1)-competitive algorithm. In the case of makespan plus energy, which is considered in the literature for the first time, we present an O(ln1−1/α P)-competitive algorithm for batched jobs consisting of fully-parallel and sequential phases. We show that this al-gorithm is asymptotically optimal by providing a matching lower bound