Dynamic speed scaling to manage energy and temperature

N. Bansal, T. Kimbrel, K.R. Pruhs

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    133 Citations (SciVal)


    We first consider online speed scaling algorithms to minimize the energy used subject to the constraint that every job finishes by its deadline. We assume that the power required to run at speed s is P(s) = s^a. We provide a tight a^a bound on the competitive ratio of the previously proposed Optimal Available algorithm. This improves the best known competitive ratio by a factor of 2^a. We then introduce competitive ratio is at most 2({\alpha \mathord{\left/ {\vphantom {\alpha {(\alpha - 1)^\alpha }}} \right. \kern-\nulldelimiterspace} {(\alpha - 1)^\alpha }}\varepsilon ^\alpha. This competitive ratio is significantly better and is approximately 2\varepsilon ^{\alpha + 1} for large a. Our result is essentially tight for large a. In particular, as a approaches infinity, we show that any algorithm must have competitive ratio \varepsilon ^\alpha (up to lower order terms). We then turn to the problem of dynamic speed scaling to minimize the maximum temperature that the device ever reaches, again subject to the constraint that all jobs finish by their deadlines. We assume that the device cools according to Fourier?s law. We show how to solve this problem in polynomial time, within any error bound, using the Ellipsoid algorithm.
    Original languageEnglish
    Title of host publicationProceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004, Rome, Italy, October 17-19, 2004)
    PublisherIEEE Computer Society
    ISBN (Print)0-7695-2228-9
    Publication statusPublished - 2004


    Dive into the research topics of 'Dynamic speed scaling to manage energy and temperature'. Together they form a unique fingerprint.

    Cite this