IntroductionTerminology and NotationThe NP-Completeness ProofsAn Online Competitive AlgorithmA Lower Bound on the Competitive RatioFinal CommentsAlgorithms for Temperature-Aware TaskScheduling in Microprocessor SystemsMarek Chrobak∗Christoph D¨urr†Mathilde Hurand†Julien Robert‡AbstractWe study scheduling problems motivated by recently developed techniques for micro-processor thermal management at the operating systems level. The general scenario canbe described as follows. The microprocessor’s temperature is controlled by the hardwarethermal management system that continuously monitors the chip temperature and au-tomatically reduces the processor’s speed as soon as the thermal threshold is exceeded.Some tasks are more CPU-intensive than other and thus generate more heat during ex-ecution. The cooling system operates non-stop, reducing (at an exponential rate) thedeviation of the processor’s temperature from the ambient temperature. As a result, theprocessor’s temperature, and thus the performance as well, depends on the order of thetask execution. Given a variety of possible underlying architectures, models for coolingand for hardware thermal management, as well as types of tasks, this scenario gives riseto a plethora of interesting and never studied scheduling problems.We focus on scheduling real-time jobs in a simplified model for cooling and thermalmanagement. A collection of unit-length jobs is given, each job specified by its releasetime, deadline and heat contribution. If, at some time step, the temperature of the systemis τ and the processor executes a job with heat contribution h, then the temperature atthe next step is (τ + h)/2. The temperature cannot exceed the given thermal thresholdT . The objective is to maximize the throughput, that is, the number of tasks that meettheir deadlines. We prove that, in the offline case, computing the optimum schedule isNP-hard, even if all jobs are released at the same time. In the online case, we show a2-competitive deterministic algorithm and a matching lower bound.1 IntroductionBackground. The problem of managing the temperature of processor systems is not new;in fact, the system builders had to deal with this challenge since the inception of computers.Since early 1990s, the introduction of battery-operated laptop computers and sensor systemshighlighted the related issue of controlling the energy consumption.Most of the initial work on these problems was hardware and systems oriented, andonly during the last decade substantial progress has been achieved on developing modelsand algorithmic techniques for microprocessor temperature and energy management. Thiswork proceeded in several directions. One direction is based on the fact that the energyconsumption is a fast growing function of the processor speed (or frequency). Thus we can save∗Department of Computer Science, University of California, Riverside, CA 92521, USA. Supported by NSFgrants OISE-0340752 and CCF-0729071.†CNRS, LIX UMR 7161, Ecole Polytechnique 91128 Palaiseau, France. Supported by ANR Alpage.‡Laboratoire de l’Informatique du Parall´elisme, Ecole Normale Sup´erieure de Lyon; ENS Lyon, France.1arXiv:0801.4238v1 [cs.DS] 28 Jan 2008energy by simply slowing down the processor. Here, algorithmic research focussed on speedscaling – namely dynamically adjusting the processor speed over time to optimize the energyconsumption while ensuring that the system meets the desired performance requirements.Another technique (applicable to the whole system, not just the microprocessor) involvespower-down strategies, where the system is powered-down or even completely turned off whensome of its components are idle. Since changing the power level of a system introduces someoverhead, scheduling the work to minimize the overall energy usage in this model becomes achallenging optimization problem.Models have also been developed for the processor’s thermal behavior. Here, the mainobjective is to ensure that the system’s temperature does not exceed the so-called thermalthreshold, above which the processor cannot operate correctly, or may even be damaged.In this direction, techniques and algorithms have been proposed for using speed-scaling tooptimize the system’s performance while maintaining the temperature below the threshold.We refer the reader to the survey by Irani and Pruhs [5], and references therein, for morein-depth information on the models and algorithms for thermal and energy management.Temperature-aware scheduling. The above models address energy and thermal man-agement at the micro-architecture level. In contrast, the problem we study in this paperaddresses the issue of thermal management at the operating systems level. Most of the previ-ous work in this direction focussed on multi-core systems, where one can move tasks betweenthe processors to minimize the maximum temperature [9, 1, 2, 6, 7, 8, 4, 10]. However, as ithas been recently discovered, even in single-core systems one can exploit variations in heatcontributions among different tasks to reduce the processor’s temperature through appro-priate task scheduling [1, 4, 6, 7, 11]. In this scenario, the microprocessor’s temperature iscontrolled by the hardware dynamic thermal management (DTM) system that continuouslymonitors the chip temperature and automatically reduces the processor’s speed as soon asthe thermal threshold (maximum safe operating temperature) is exceeded. Typically, thefrequency is reduced by half, although it can be further reduced to one fourth or even oneeighth, if needed. Running at a lower frequency, the CPU generates less heat. The coolingsystem operates non-stop, reducing (at an exponential rate) the deviation of the processor’stemperature from the ambient temperature. Once the chip cools down to below the threshold,the frequency is increased again.Different tasks use different microprocessor units in different ways; in particular, sometasks are more CPU-intensive than other. As a result, the processor’s thermal behavior –and thus the performance as well – depends on the order of the task execution. In particular,Yang et al. [11] point out that, based on the standard model for the microprocessor thermalbehavior, for any given two tasks, scheduling the “hotter” job before the “cooler” one, resultsin a lower final temperature than after the reverse order. They take advantage of this phe-nomenon to reduce the number of DTM invocations, thus