DOC PREVIEW
Pitt CS 3150 - Speed Scaling for Weighted Flow Time

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Speed Scaling for Weighted Flow TimeNikhil Bansal∗Kirk Pruhs†Cliff Stein‡AbstractIntel’s SpeedStep and AMD’s PowerNOW technologies allow the Windows XP operating systemto dynamically change the speed of the processor to prolong battery life. In this setting, the operatingsystem must not only have a job selection policy to determine which job to run, but also a speed scalingpolicy to determine the speed at which the job will be run. We give an online speed scaling algorithmthat is O(1)-competitive for the objective of weighted flow time plus energy. This algorithm also allowsus to efficiently construct an O(1)-approximate schedule for minimizing weighted flow time subject toan energy constraint.1 IntroductionIn addition to the traditional goal of efficiently managing time and space, many computers now need toefficiently manage power usage. For example, Intel’s SpeedStep and AMD’s PowerNOW technologies allowthe Windows XP operating system to dynamically change the speed of the processor to prolong battery life.In this setting, the operating system must not only have a job selection policy to determine which job torun, but also a speed scaling policy to determine the speed at which the job will be run. These policiesmust be online since the operating system does not, in general, have knowledge of the future. In currentCMOS based processors, the speed satisfies the well known cube-root-rule, that the speed is approximatelythe cube root of the power [Mud01, BBS+00]. Thus, in this work, we make the standard generalization thatthe power used by a processor is equal to speed to some power α ≥ 1, where one should think of α as beingapproximately 3 [YDS95, BKP07]. Energy is power integrated over time. An operating system is facedwith a dual objective optimization problem as it both wants to conserve energy, and optimize some Qualityof Service (QoS) measure of the resulting schedule.By far the most commonly used QoS measure in the computer systems literature isaverageresponse/flowtime or more generally weighted response/flowtime. The flow time Fiof a job i is the time lag between whena job is released to the system and when the system completes that job. Pruhs, Uthaisombut, and Woeginger[PUW08] studied the problem of optimizing total flow time (PiFi) subject to the constraint that the totalenergy does not exceed some bound, say the energy in the battery, and showed how to efficiently construct∗IBM T.J. Watson Research, P.O. Box 218, Yorktown Heights, NY. [email protected].†Computer Science Department. University of Pittsburgh. [email protected]. Supported in part by NSF grants CNS-0325353,CCF-0448196, CCF-0514058 and IIS-0534531.‡Department of IEOR, Columbia University, New York, NY. Supported in part by NSF grant CCF-0728733 and an IBM facultyfellowship. [email protected] an optimal schedule for instances with unit work jobs. For unit work jobs, all job selection policiesthat favor a partially executed job in favor of an unexecuted job are equivalent. Thus the job selection policyis essentially irrelevant.If there is an upper bound on energy used, then there is no O(1)-competitive online speed scaling policyfor total flow time. To understand intuitively why this is the case, consider the situation when the firstjob arrives. The scheduler has to allocate a constant fraction of the total energy to this job; otherwise, thescheduler would not be O(1)-competitive in the case that no more jobs arrive. However, if many more jobsarrive in the future, then the scheduler has wasted a constant fraction of its energy on only one job. Byiterating this process, one obtains a bound of ω(1) on the competitive ratio with respect to total flow time.(See Section 6.)Albers and Fujiwara [AF07] proposed combining the dual objectives of energy and flow time into thesingle of objective of energy used plus total flow time. Optimizing a linear combination of energy and totalflow time has the followingnatural interpretation. Suppose that the user specifies how much improvement inflow time, call this amount ρ, is necessary to justifyspending one unit of energy. For example, the user mightspecify to the Windows XP operating system that he is willing to spend 1 erg of energy from the battery fora decrease of 3 micro-seconds in response time. Then the optimal schedule, from this user’s perspective, isthe schedule that optimizes ρ = 3 times the energy used plus the total flow time. By changing the units ofeither energy or time, one may assume without loss of generality that ρ = 1.[PUW08] observe that in any locally-optimal normal schedule, each job i is run at a power proportionalto the number of jobs that depend on i. Roughly speaking, normal means that no job completes exactlywhen another job is released. We say that a job j depends on a job i if delaying i would delay j. In theonline setting, an obvious lower bound to the number of jobs that depend on the selected job is the numberof active jobs, where an active job is one that has been released but has not yet completed. Thus Albers andFujiwara [AF07] propose the natural online speed scaling algorithm that always runs at a power equal to thenumber of active jobs. They again only consider the case of unit work jobs. They do not actually analyzethis natural algorithm, but rather analyze a batched variation, in which jobs that are released while thecurrent batch is running are ignored until the current batch finishes. They show that this batched algorithmis 8.3e(3+√52)α-competitive with respect to the objective of total flow time plus energy, and also give adynamic programming algorithm to compute the offline optimal schedule for unit work jobs.One reason that both [PUW08] and [AF07] consider only unit work jobs is that it seems that the optimalschedule for arbitrary work jobs is quite difficult to characterize.1.1 Our ResultsWe give significantly stronger results for the problem of minimizing the objective of (weighted) flow timeplus energy. We both improve the algorithm and analysis in the special case (unit jobs, no weights) consid-ered previously [AF07] and then we give algorithms for the more general problem with weights and arbitrarywork jobs.First, we show that the natural online speed scaling algorithm proposed in [AF07] is 4-competitive forunit work jobs. This guarantee is independent of α. In comparison, the competitive ratio 8.3e(3+√52)αobtained in [AF07] is a bit over 400 when the cube-root rule holds (α =


View Full Document

Pitt CS 3150 - Speed Scaling for Weighted Flow Time

Documents in this Course
JouleSort

JouleSort

12 pages

Load more
Download Speed Scaling for Weighted Flow Time
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 Speed Scaling for Weighted Flow Time 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 Speed Scaling for Weighted Flow Time 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?