TY - GEN

T1 - Speed scaling to manage temperature

AU - Bansal, N.

AU - Pruhs, K.R.

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-540-31856-9_38

DO - 10.1007/978-3-540-31856-9_38

M3 - Conference contribution

SN - 3-540-24998-2

T3 - Lecture Notes in Computer Science

SP - 460

EP - 471

BT - Theoretical Aspects of Computer Science (22nd Annual Symposium, STACS 2005, Stuttgart, Germany, February 24-26, 2005. Proceedings)

A2 - Diekert, V.

A2 - Durand, B.

PB - Springer

CY - Berlin

ER -