Speed scaling to manage temperature

N. Bansal, K.R. Pruhs

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

    47 Citations (Scopus)


    We consider speed scaling algorithms to minimize device temperature subject to the constraint that every task finishes by its deadline. We assume that the device cools according to Fouriers law. We show that the optimal offline algorithm proposed in [18] for minimizing total energy (that we call YDS) is an O(1)-approximation with respect to temperature. Tangentially, we observe that the energy optimality of YDS is an elegant consequence of the well known KKT optimality conditions. Two online algorithms, AVR and Optimal Available, were proposed in [18] in the context of energy management. It was shown that these algorithms were O(1)-competitive with respect to energy in [18] and [2]. Here we show these algorithms are not O(1)-competitive with respect to temperature. This demonstratively illustrates the observation from practice that power management techniques that are effective for managing energy may not be effective for managing temperature. We show that the most intuitive temperature management algorithm, running at such a speed so that the temperature is constant, is surprisingly not O(1)-competitive with respect to temperature. In contrast, we show that the online algorithm BKP, proposed in [2], is O(1)-competitive with respect to temperature. This is the first O(1)-competitiveness analysis with respect to temperature for an online algorithm.
    Original languageEnglish
    Title of host publicationTheoretical Aspects of Computer Science (22nd Annual Symposium, STACS 2005, Stuttgart, Germany, February 24-26, 2005. Proceedings)
    EditorsV. Diekert, B. Durand
    Place of PublicationBerlin
    ISBN (Print)3-540-24998-2
    Publication statusPublished - 2005

    Publication series

    NameLecture Notes in Computer Science
    ISSN (Print)0302-9743


    Dive into the research topics of 'Speed scaling to manage temperature'. Together they form a unique fingerprint.

    Cite this