Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule

Speed scaling is a power management technique that involves dynamically changing the speed of a processor. This gives rise to dualobjective 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 power consumption is the speed to some constant power α. We give the first non-trivial lower bound, namely eα−1/α, on the competitive ratio for this problem.

For CMOS based processors, and many other types of devices, α = 3, that is, they satisfy the cube-root rule. Thus the most interesting case is when α = 3.When α = 3, the algorithm with the best known competitive ratio is Optimal Available (OA), which is 27-competitive.We introduce a new algorithm qOA, and show that qOA is 6.7-competitive when α = 3. So when the cube-root rule holds, our results reduce the range for the optimal competitive ratio from [1.8, 27] to [2.4, 6.7].We also analyze qOA for general α and give almost matching upper and lower bounds.

By: Nikhil Bansal; Ho-Leung Chan; Kirk Pruhs; Dmitriy Rogozhnikov-Katz

Published in: RC24461 in 2008


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .