DOC PREVIEW
Pitt CS 3150 - Nonclairvoyant Speed Scaling

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

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 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 11 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 11 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 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Nonclairvoyant Speed Scaling for Flow and EnergyHo-Leung Chan∗Jeff Edmonds†Tak-Wah Lam∗Lap-Kei Lee∗Alberto Marchetti-Spaccamela‡Kirk Pruhs§AbstractWe study online nonclairvoyant speed scaling to minimize total flow time plusenergy. We first consider the tradi tional model where the power function is P (s) = sα.We give a nonclair voyant algorithm that is shown to be O(α2log α)-competitive. Wethen show an Ω( α1/3−ǫ) lower bound on the competitive ratio of any nonclairvoyantalgorithm. We also show that there are power functions for which no nonclairvoya ntalgorithm can be O(1)-competitive.1 IntroductionEnergy consumption has become a key issue in the design of microprocessors. Major chipmanufacturers, such as Intel, AMD and IBM, now pro duce chips wi t h dynamically scalablespeeds, and produce associated software, such as Intel’s SpeedStep and AM D’s PowerNow,that enables an operati ng system to manage power by scaling proc essor speed. Thus theoperating system should have a speed scaling policy for setting t he speed of the processor,that ideally should work in tandem with a job selection policy f or determining which jobto run. The operating system has dual competing objectives, as it both wants to optimizesome schedule quality of service objective, as well as some power rel ated objective.In this paper, we will consider the objective of minimizing a linear combination of totalflow and total energy used. For a formal definitions of the problem that we consider, seesubsection 1.2. This objective of flow plus ene rgy has a natural interpretation: suppose thatthe user specifies how much i mprovement in flow, call this amount ρ, is necessary to justifyspending one unit of energy. For example, the user might specify that he is willing to spend1 erg of energy from the battery for a decrease of 5 micro-seconds in flow. Then the optimalschedule, from this user’s perspective, is the schedule that optimizes ρ = 5 times the energy∗The University of Hong Kong. {hlchan,twlam,lklee}@cs.hku.hk. This work of Ho-Leung Chan wasdone when he was a p ostdoc in University of Pittsburgh. Tak-Wah Lam is partially supported by HKUGrant 7176104.†York University. [email protected]. Supported in part by NSERC Canada.‡Dipartimento di Informatica e Sistemistica, Sapienza Universit`a di Rom a. [email protected] in part by MIUR FIRB grant RBIN047MH9 and by EU ICT-FET grant 215270 FRONTS.§University of Pittsburgh. [email protected]. Supported in part by an IBM faculty award, and by NSFgrants CNS-0325353, CCF-0514058, IIS-0534531, and CCF-0830558.1used plus the total flow. By changing the units of e ither energy or time, one may assumewithout loss of generality that ρ = 1.In order to be implementable in a real system, t he speed scaling and job selection poli-cies must be online since the system will not in general know about jobs arrivi ng in thefuture. Further, to be implementable in a generi c operating system, these pol icies must benonclairvoyant, since in general the operating system does not know the size/work of eachprocess when the process is re leased to the operating system. All of the previous speedscaling liter ature on this objective has considered either offline or online clairvoyant policies.In subsection 1.1, we survey the literature on nonclairvoyant scheduling polici es for flowobjectives on fixed speed processors, and the speed scaling li t erature for flow plus energyobjectives.Our goal in thi s paper is to study nonclairvoyant speed scaling policies using competitiveanalysis.We first analyze the nonclairvoyant algorithm whose job selection p ol icy is Latest ArrivalProcessor Sharing (LAPS) and whose speed scaling policy is to run at the spee d such thatthe power equals the number of active jobs. LAPS shares the processor eq ually among thelatest arriving constant fraction of the jobs. We adopt the traditional model that the powerfunction, whi ch gives the power as a function of the speed of the processor, is P (s) = sα,where α > 1 is some constant. Of particular interest is the case α = 3 since, according to thewell known cube-root rule, the dy namic power in CMOS based processors is approximatelythe cube of the speed. Using an amortized local competitiveness argument, we show insection 2 that this algorithm is O(α2log α)-competitive. The potential function that we use isan amalgamation of the potential function used in [8] for the fixed speed analysis of LAPS,and the potential functions used for analyzing clairvoyant speed scaling policies. This resultshows that it is possible for a noncl ai r voyant policy to b e O(1)-competitive if the cube-rootrule holds.It is known that for essentially every power function, there i s a 3-compe t itive clairvoy-ant speed scaling policy [3]. In contrast, we show that the competitiveness achievable bynonclairvoyant policies must depend on the power function. In the traditional model, weshow in section 3 an Ω(α1/3−ǫ) lower bound on the competitive ratio of any deterministicnonclairvoyant algorithm. Further, we show in section 3 that there exists a particular powe rfunction for which there i s no O(1)-competitive deterministic nonclairvoyant speed scalingalgorithm. The adversarial strategies f or these lower bounds are based on the adversarialstrategies in [12] for fixed speed processors. Perhaps these lowe r bound results are not sosurprising given the fact that it is known that without speed scaling, resource augmentationis required to achieve O(1)-competitiveness f or a nonclairvoyant polic y [9, 12]. Still a prioriit wasn’t completely clear that the lower b ounds in [12] would carry over. The reason is thatin t hese lower bound instances, the adversary forced the online algorithm into a situation inwhich t he online algorithm had a lot of jobs with a small amount of remaining work, whilethe adversary had one job left wi t h a lot of remaining work. In the fixed spe ed setting, theonline algorithm, without resource augmentation, can ne ver get a chance to get rid of thisbacklog in the face of a steady stream of jobs. However, in a speed scaling setting, one mightimagine an online algorithm that speeds up enough to remove the backlog, but not enoughto make its energy usage more than a constant times optimal. Our lowe r bound shows that2it is not possible for the online algorithm to accomplish this.1.1 Related resultsWe start with some results in the literature about scheduling with the


View Full Document

Pitt CS 3150 - Nonclairvoyant Speed Scaling

Documents in this Course
JouleSort

JouleSort

12 pages

Load more
Download Nonclairvoyant Speed Scaling
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 Nonclairvoyant Speed Scaling 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 Nonclairvoyant Speed Scaling 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?