Improved bounds for speed scaling in devices obeying the cube-root rule

N. Bansal, H.L. Chan, K.R. Pruhs, D. Katz

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    30 Citaten (Scopus)


    Speed scaling is a power management technique that involves dynamically changing the speed of a processor. This 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 power consumption is the speed to some constant power a. We give the first non-trivial lower bound, namely e^(a-1)/a, on the competitive ratio for this problem. This comes close to the best upper bound which is about 2e^(a+1). We analyze a natural class of algorithms called qOA, where at any time, the processor works at q¿=¿1 times the minimum speed required to ensure feasibility assuming no new jobs arrive. For CMOS based processors, and many other types of devices, a=¿3, that is, they satisfy the cube-root rule. When a=¿3, we show that qOA is 6.7-competitive, improving upon the previous best guarantee of 27 achieved by the algorithm Optimal Available (OA). So when the cube-root rule holds, our results reduce the range for the optimal competitive ratio from [1.2, 27] to [2.4, 6.7]. We also analyze qOA for general a and give almost matching upper and lower bounds.
    Originele taal-2Engels
    TitelAutomata, Languages and Programming (36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009. Proceedings, Part I)
    RedacteurenS. Albers, A. Marchetti-Spaccamela, Y. Matias, S. Nikoletseas, W. Thomas
    Plaats van productieBerlin
    ISBN van geprinte versie978-3-642-02926-4
    StatusGepubliceerd - 2009

    Publicatie series

    NaamLecture Notes in Computer Science
    ISSN van geprinte versie0302-9743

    Vingerafdruk Duik in de onderzoeksthema's van 'Improved bounds for speed scaling in devices obeying the cube-root rule'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit