Algorithmic Problems in Power ManagementSandy IraniSchool of Information and Computer ScienceUniversity of California, IrvineKirk R. Pruhs∗Computer Science DepartmentUniversity of Pittsburgh1 IntroductionWe survey recent research that has appeared in the theoretical computer science literature on algorithmicproblems related to power management. We will try to highlight some open problems that we feel areinteresting. This survey places more concentration on lines of research of the authors: managing powerusing the techniques of speed scaling and power-down which are also currently the dominant techniques inpractice.1.1 MotivationThe power consumption rate of computing devices has been increasing exponentially. Since the early 1970s,the power densities in microprocessors have doubled every three years [34]. This increased power usageposes two types of difficulties:• Energy Consumption: As energy is power integrated over time, supplying the required energy maybecome prohibitively expensive, or even technologically infeasible. This is a particular difficulty indevices that rely heavily on batteries for energy, and will will become even more critical as batterycapacities are increasing at a much slower rate than power consumption. Anyone using a laptop on along flight is familiar with this problem.• Temperature: The energy used in computing devices is in large part converted into heat. Forhigh-performance processors, cooling solutions are rising at $1 to $3 per watt of heat dissipated,meaning that cooling costs are rising exponentially and threaten the computer industry’s abilityto deploy new systems [34]. In May 2004 Intel publicly acknowledged that it had hit a “ther-mal wall” on its microprocessor line. Intel scrapped the development of its Tejas and Jayhawkchips in order to rush to the marketplace a more efficient chip technology. Designers said thatthe escalating heat problems were so severe that they threatened to cause its chips to fracture [27].For a striking example of the grievous effect of removing the fan from a modern processor, seehttp : //www.cs.pitt.edu/ ∼ kirk/cool.avi.(You will need a DivX codec installed.)These two factors have resulted in power becoming a first-class design constraint for modern computingdevices [28].There is an extensive literature on power management in computing devices. Overviews can be foundin [11, 28, 36]. All of these techniques that have been investigated are similar in that they reduce or elim-inate power to some or all components of the device. Sensor networks have emerged as an important new∗Supported in part by NSF grants CCR-0098752, ANI-0123705, CNS-0325353, and CCF-0448196.1paradigm in which power-aware computation is absolutely critical. The explosive interest in sensor net-works is the result of the development of low-cost, low-power mutifunctional sensor devices, such as theSmart Dust Mote [1, 22], that are small in size and communicate untethered at short distance.There is an inherent conflict between power reduction and performance; in general, the more powerthat is available, the better the performance that can be achieved. As a result, it is generally proposedthat power reduction techniques be preferentially applied during times when performance is less critical.However, this requires a policy to determine how essential performance is at any given time and how toapply a particular power reduction technique. Current tools and mechanisms for power management areinadequate and require more research [14]. Furthermore, there is a growing consensus that these policiesmust incorporate information provided by applications and high levels of the operating system in order toachieve necessary advances [14].We advocate formalizing power management problems as optimization problems, and then developingalgorithms that are optimal by these criteria. The goal is to develop effective algorithms for specific problemswithin the domain of power management as well as to build a toolkit of widely applicable algorithmicmethods for problems that arise in energy-bounded and temperature-bounded computation.2 Speed Scaling2.1 Formulation as a Scheduling ProblemSpeed scaling involves dynamically changing the voltage and/or frequency/speed of the processor. A pro-cessor consumes less power when it is run at a lower speed. Both in academic research and practice,dynamic voltage/frequency/speed scaling is the dominant technique to reduce switching loss, which is cur-rently the dominant form of energy consumption in microprocessors [11, 28, 36]. Current microprocessorsfrom AMD, Intel and Transmeta allow the speed of the microprocessor to be set dynamically. Informally,speed scaling problems involve determining the speed of the processor at each point in time.Theoretical investigations of speed scaling algorithms were initiated by Yao, Demers, and Shankar [37].Yao et al. [37] propose formulating speed scaling problems as scheduling problems. The setting is a collec-tion of tasks, where each task i has a release time riwhen it arrives into the system, and an amount of workwithat must be performed to complete the task. A schedule specifies which task to run at each time, and atwhat speed that task should be run.In particular, Yao et al. [37] consider the case that there is also a deadline diassociated with each taskthat specifies the time by which the task should be completed. In some settings, for example, the playingof a video or other multimedia presentation, there may be natural deadlines for the various tasks imposedby the application. In other settings, the system may impose deadlines to better manage tasks or insure acertain quality of service to each task [12]. Yao et al. [37] assume that the system’s performance measure isdeadline feasibility; that is, each task must finish by its deadline.They study the problem of minimizing the total energy used subject to the deadline feasibility con-straints. Bansal, Kimbrel and Pruhs [7, 8] study the problem of minimizing the maximum temperatureattained subject to the deadline feasibility constraints.2.2 Energy and TemperatureBefore proceeding further, we need to explain how speed, power, energy, and temperature are modeled,and how they are related. Yao et al. [37] assume a continuous function P (s) such that if the device runsat speed s, then it consumes power at a rate of P(s). For example, the well known cube-root rule forCMOS based devices states that the speed s is roughly proportional to