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 Fourier’s law. We show that the energy optimal schedule YDS is O(1)-competitive 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 in 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.

By:* Nikhil Bansal, Kirk Pruhs*

Published in: Lecture Notes in Computer Science, volume 3404, (no ), pages 460-71 in 2005

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .