Pitt CS 3150 - A Scheduling Model for Reduced CPU Energy

Unformatted text preview:

A Scheduling Model for Reduced CPU Energy Frances Yao Alan Demers Scott Shenker Xerox Palo Alto Research Center 3333 Coyote Hill Road Palo Alto, CA 94304 {yao, demers, shenker}@parc.xerox.com (extended abstract) Abstract The energy usage of computer systems is becom- ing an important consideration, especially for battery- operated systems. Various methods for reducing en- ergy consumption have been investigated, both at the circuit level and at the operating systems level. In this paper, we propose a simple model of job scheduling aimed at capturing some key aspects of energy min- imization. In this model, each job is to be executed between its arrival time and deadline by a single pro- cessor with variable speed, under the assumption that energy usage per unit time, P, is a convex function of the processor speed s. We give an off-line algorithm that computes, for any set of jobs, a minimum-energy schedule. We then consider some on-line algorithms and their competitive performance for the power func- tion P(s) = sp where p 3 2. It is shown that one natural heuristic, called the Average Rate heuristic, uses at most a constant times the minimum energy required. The analysis involves bounding the largest eigenvalue in matrices of a special type. 1 Introduction Computers are rapidly becoming more widespread and more portable. For portable computers running on batteries, energy conservation is critically impor- tant. In a typical laptop computer, energy use is domi- nated by the backlit display and the disk. It is difficult to modulate the power consumption of these devices while they are operating, so energy saving techniques primarily involve turning them off after a period of no use. The new generation of very small portable comput- ers (PDAs) often have no disk at all, and lack the backlight that consumes much of the display-related power. For such devices, the power consumption of the CPU itself becomes significant. This fact is important because there are energy conservation techniques for CPUs that do considerably better than simply turn- ing off the device during its “idle loop”. In particular, CPU circuitry can be designed so that slower clock speeds use lower supply voltage, thus resulting in lower energy consumption per instruction (see [1,2,4,7] for various approaches). Such variable speed processors can operate reliably over a range of clock speeds. The power (i.e., energy per unit time) consumed by such a processor is a convex function of its execution speed, with the exact form dependent on the details of the technology. On a computer with a variable speed processor, the operating system can reduce the energy consumption by scheduling jobs appropriately. Scheduling to reduce power consumption was first discussed in [7], which described several scheduling heuristics and measured the energy savings on typical work loads. This work was later extended in [3]. In this paper, we provide a more formal analysis of the minimum-energy scheduling problem. We pro- pose a simple model in which each job is to be exe- cuted between its arrival time and deadline by a single variable-speed processor as described above. A precise definition of the model is given in Section 2. In Sec- tion 3, we give an off-line algorithm that computes a minimum-energy schedule for any set of jobs, with no restriction on the power consumption function ex- cept convexity. We then consider on-line heuristics in Section 4, with special focus on what we call the Aver- age Rate heuristic (AVR). In Section 5, we prove that AVR has a constant competitive ratio, i.e., it uses at most a constant times the minimum energy required, 374 0272-5428/95 $04.00 0 1995 IEEE Authorized licensed use limited to: University of Pittsburgh. Downloaded on January 3, 2010 at 10:42 from IEEE Xplore. Restrictions apply.assuming a quadratic power function P(s) = s2. Our analysis shows that the ratio lies between 4 and 8. In Section 6, we sketch a constant-ratio proof for the gen- eral case P(s) = sp where p 2 2. There, the ratio is shown to be between pP and 2P-lpP. Finally, we close with a discussion of some simulation results and open problems. 2 The Model Let [to,tl] be a fixed time interval. An instance of the scheduling problem is a set J of jobs to be executed during [to,tl]. Associated with each job j E J are the following parameters: 0 aj its arrival time, 0 bj its deadline (bj > aj), and 0 Rj its required number of CPU cycles. We refer to [ai, bj] as the interval of job j. A sched- ule is a pair S = (s,job) of functions defined over [to,t11: 0 s(t) 2 0 is the processor speed at time t; 0 job(t) defines the job being executed at time t (or idle if s(t) = 0). We require that s(t) and job(t) be piecewise constant with finitely many discontinuities. A feasible schedule for an instance J is a schedule S that satisfies for all j E J (where S(z,y) is 1 if x = y and 0 oth- erwise). In other words, S must give each job j the required number of cyles between its arrival time and deadline (with perhaps intermittent execution). We assume that the power P, or energy consumed per unit time, is a convex function of the processor speed. The total energy consumed by a schedule S is’ E(S) = P(s(t))dt. The goal of the scheduling problem is to find, for any given problem instance, a feasible schedule that mini- mizes E(S). ‘In the remainder of this paper, unless otherwise specified, all integrals are taken with respect to t, with to and tl as lower and upper limits. We will use abbreviated notations whenever possible. 3 The Minimum Energy Scheduler In this section, we consider the off-line version of the scheduling problem. We first give a charaterization of an energy-optimal schedule for any set of n jobs, which then leads naturally to an O(nlog2 n) time algorithm for computing such schedules. The characterization will be based on the notion of a critical interval for J, which is an interval in which a group of jobs must be scheduled at maximum, con- stant speed in any optimal schedule for J. The algo- rithm proceeds by identifying such a critical interval for J, scheduling those ‘critical’ jobs, then construct- ing a subproblem for the remaining jobs and solving it recursively. The optimal s(t) is in fact unique, whereas job(t) is not always so. The details are given below.


View Full Document

Pitt CS 3150 - A Scheduling Model for Reduced CPU Energy

Documents in this Course
JouleSort

JouleSort

12 pages

Load more
Download A Scheduling Model for Reduced CPU Energy
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view A Scheduling Model for Reduced CPU Energy and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view A Scheduling Model for Reduced CPU Energy 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?