Theory of Computing
-------------------
Title : Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule
Authors : Nikhil Bansal, Ho-Leung Chan, Dmitriy Katz, and Kirk Pruhs
Volume : 8
Number : 9
Pages : 209-229
URL : http://www.theoryofcomputing.org/articles/v008a009
Abstract
--------
Speed scaling is a power management technology that involves
dynamically changing the speed of a processor. This technology
gives rise to dual-objective scheduling problems, where the
operating system both wants to conserve energy and optimize some
Quality of Service (QoS) measure of the resulting schedule. In the
most investigated speed scaling problem in the literature, the QoS
constraint is deadline feasibility, and the objective is to
minimize the energy used. The standard assumption is that the
processor power is of the form s^alpha where s is the processor
speed, and alpha > 1 is some constant; alpha \approx 3 for CMOS
based processors.
In this paper we introduce and analyze a natural class of speed
scaling algorithms, that we call qOA. The algorithm qOA sets the
speed of the processor to be q times the speed that the optimal
offline algorithm would run the jobs in the current state. When
alpha=3, we show that qOA is 6.7-competitive, improving upon the
previous best guarantee of 27 achieved by the algorithm Optimal
Available (OA). We also give almost matching upper and lower
bounds for qOA for general alpha. Finally, we give the first
non-trivial lower bound, namely e^{alpha-1}/alpha, on the
competitive ratio of a general deterministic online algorithm for
this problem.