Average Rate Speed ScalingNikhil Bansal∗David P. Bunde†Ho-Leung Chan‡Kirk Pruhs§May 12, 2008AbstractSpeed scaling is a power management technique that involves dynamically changing the speed of aprocessor. This gives rise to dual-objective scheduling problems, where the operating system both wantsto conserve energy and optimize some Quality of Service (QoS) measure of the resulting schedule. Yao,Demers, and Shenker [4] considered the problem where the QoS constraint is deadline feasibility andthe objective is to minimize the energy used. They proposed an online speed scaling algorithm AverageRate (AVR) that runs each job at a constant speed between its release and its deadline. They showed thatthe competitive ratio of AVR is at most (2α)α/2 if a processor running at speed s uses power sα. Weshow the competitive ratio of AVR is at least ((2 − δ)α)α/2, where δ is a function of α that approacheszero as α approaches infinity. This shows that the competitive analysis of AVR by Yao, Demers, andShenker is essentially tight, at least for large α. We also give an alternative proof that the competitiveratio of AVR is at most (2α)α/2 using a potential function argument. We believe that this analysis issignificantly simpler and more elementary than the original analysis of AVR in [4].1 IntroductionCurrent processors produced by Intel and AMD allow the speed of the processor to be changed dynami-cally. Intel’s SpeedStep and AMD’s PowerNOW technologies allow the Windows XP operating system todynamically change the speed of such a processor to conserve energy. In this setting, the operating systemmust not only have a job selection policy to determine which job to run, but also a speed scaling policy todetermine the speed at which the job will be run. In current CMOS based processors, the speed satisfies thewell-known cube-root-rule, that the speed is approximately the cube root of the power. Energy consumptionis power integrated over time. The operating system is faced with a dual objective optimization problemas it both wants to conserve energy, and optimize some Quality of Service (QoS) measure of the resultingschedule.The first theoretical worst-case study of speed scaling algorithms was in the seminal paper [4] by Yao,Demers, and Shenker. Their QoS objective was deadline feasibility and the objective was to minimizethe energy used. More precisely, each job i has a release time riwhen it arrives in the system, a workrequirement wi, and a deadline diby which the job must be finished. If job i runs at constant speed s, then∗IBM T. J. Watson Research Center, [email protected]†Computer Science Department, Knox College, [email protected]. Supported in part by Howard Hughes Medical Institutegrant 52005130.‡Computer Science Department, University of Pittsburgh, [email protected].§Computer Science Department, University of Pittsburgh, [email protected]. Supported in part by NSF grants CNS-0325353,CCF-0514058 and IIS-0534531.1it completes in wi/s units of time. In this setting, an optimal job selection policy is Earliest Deadline First(EDF). They assumed a speed to power function P(s) = sα, where α > 1 is some constant. If the cube-rootrule holds, then α = 3. Yao, Demers, and Shenker [4] showed that the optimal energy feasible schedule isfound by a simple greedy algorithm that we call YDS.Yao, Demers, and Shenker [4] also proposed an online speed scaling algorithm, Average Rate (AVR).Conceptually, AVR runs each job i at speed wi/(di− ri) throughout interval [ri, di], independent of otherjobs. This spreads the work of each job as evenly over time as possible. By the convexity of the speed topower function, this even spreading is energy optimal if the instance consists of only one job. The speedof the processor at any time t is then just the sum of the speeds of the jobs active at that time, that isPi:t∈[ri,di]widi−ri. AVR is an appealing speed scaling algorithm because in some sense it is perfectly fair toall jobs, and each job runs as if it were the only job in the instance.Yao, Demers, and Shenker [4] showed that the competitive ratio, with respect to energy, of AVR is atleast αα. They also showed that the competitive ratio of AVR, with respect to energy, is at most (2α)α/2.We now outline this upper bound competitive analysis of AVR. A job is defined to be of type A if theoptimal schedule is always ahead of AVR on this job. A job is defined to be of type B if AVR is alwaysahead of the optimal schedule on this job. A schedule is bitonic if every job is of type A or type B. [4]observes that there is a worst-case instance that is bitonic, and that the competitive ratio of AVR is at most2α−1times the competitive ratio of AVR on instances of jobs of just one type (A or B). [4] then considersinstances consisting only of type-A jobs. [4] then introduces an auxiliary objective function that is relatedto, but is not exactly, the energy used. In a somewhat involved reduction, [4] shows that with respect tothis auxiliary objective, there is a worst-case instance where the optimal schedule is non-preemptive, eachjob starts when it is released, and the spans of the jobs are nested (where the span of job i is the interval[ri, di]). When α = 2, [4] then shows that for such instances, optimizing the auxiliary objective function canbe represented in terms of the eigenvalues of a particular tree-induced matrix, and shows how to bound thelargest eigenvalue for such tree-induced matrices. [4] states that this argument can be readily generalized toan arbitrary α, and using H¨older’s inequality, give a bound on the ℓpnorm of a certain tree-induced matrixthat would replace the eigenvalue argument used in the α = 2 case.So the natural question left open is, “What is the exact competitive ratio of AVR?” Based on simulationresults, [4] conjectured that the competitive ratio of AVR is exactly αα. That is, that the lower bound in [4]is correct, and intuitively, that AVR can not simultaneouslybe losing badly on both type-A and type-B jobs.In the case that the cube-root rule holds, αα= 33= 27 is the best known competitive ratio for any onlinealgorithm. If the conjecture from [4] was true, this would be evidence in favor of adopting the AVR speedscaling policy. Not only would AVR have the best known competitive ratio in the case that the cube-rootrule holds, but AVR is appealingly fair to all jobs.Unfortunately,in section 4, we show that the upper bound on the