Optimal Power-down Strategies

Optimal Power-down Strategies

Optimal Power-Down Strategies Chaitanya Swamy Caltech John Augustine Sandy Irani University of California, Irvine Dynamic Power Management Request i Idle period Request i+1 Machine/server serving jobs/requests in active state with high power consumption rate

Idle period between requests length is apriori unknown During idle period can transition to low power state incur power-down cost Idle power management: Determine when to transition so as to minimize total power consumed Active state s0 =1 Sleep state s1 =0 Transition cost down from s0 to s1 Idle period length : power consumption rate

: power consumption rate = d0,1 = cost to power- = t (not known in advance) A(t), OPT(t): total power Power Decide when to transition from active state to sleep consumed when idle period consume state. A length is t d 2d0,1 Competitive ratio (c.r.) of A Simply a continuous version of the ski-rental = maxt A(t)/OPT(t) = 2 problem.

OPT Suppose t is generated by a d0,1 probability distribution. Expected power ratio (e.p.r.) of t A d0,1 = Et [A(t)] / Et [OPT(t)] DPM with multiple sleep states Set of states S = (s0, s1,, sk) s0 : active state, rest are sleep states ri : power consumption rate of si r0 > r1 > > rk di,j : cost of transitioning from si to sj Power-down strategy is a tuple (S,T) S : sequence of states of S starting at s0

T : transition time sequence for S starting at t = 0 Power consume d s 0 s 1 s 2 d0,3 s 3

d0,2 d0,1 t = idle period length Power consume d s 0 Follow-OPT Strategy d2,3 s

d1,2 1 s 2 s d0,3 3 d0,1 OPT is lower envelop of lines d0,2

d0,1 t = idle period length Two Types of Bounds Global bound: what is the smallest c.r. (e.p.r.) * such that every DPM instance has a powerdown strategy of c.r. (or e.p.r.) at most * ? Instance-wise bound: Given a DPM instance I, what is the best c.r. (or e.p.r.) (I) for that instance? Clearly * = maxinstances I (I) Would like an algorithm that given instance I, computes strategy with c.r. (or e.p.r.) = (I). Related Work 2-state DPM ski-rental problem Karlin, Manasse, Rudolph & Slater: global bound of 2 for c.r.

Karlin, Manasse, McGeoch & Owicki: global bound of e/(e-1) for expected power ratio. easy to give instance-wise optimal strategies. Multi-state DPM Irani, Gupta & Shukla: global bounds for additive transition costs, di,k = di,j + dj,k for all i>j>k called DPM-A (additive). Show that Follow-OPT has c.r. = 2, give strategy with expected power ratio = e/(e-1). Other extensions capital investment problem (Azar et al.) Our Results Give the first bounds for (general) multi-state DPM. Global bounds: give a simple algorithm that

computes strategy with competitive ratio * 5.83. Instance-wise bounds: Given instance I find strategy with c.r. (I)+ in time O(k2log k.log(1/ )). Use this to show a lower bound of * 2.45. find strategy with optimal expected power ratio for the instance. Finding the Optimal Strategy DPM instance I is given. Want to find strategy with optimal competitive ratio for I. Decision procedure: given , find a strategy with c.r. or say that none exists. Need to determine a) state sequence, and b) transition times.

Claim: For any strategy A, c.r.(A) = maxt=transition time of A A(t)/OPT(t). Power consume d A OPT t = idle period length Suppose A=(S,T) has c.r. , and transitions to sS at time t1T s.t. A(t) < .OPT(t). Then, can find new transition times T' such that

Power a) A' = (S,T') has c.r. , b) A' transitions to s at time .OPT consume t' < t1. d A OPT t1 t = idle period length tA(s) = transition time of s in strategy A

Strat(s) = set of (partial) strategies A ending at s such that c.r.(A) in [0,tA(s)] E(s) = minA' Strat(s) tA' (s) = early transition time of s Power . OPT Let A = strategy attaining above minimum. Properties

of A: A a) A(E(s)) = .OPT(E(s)) OPT tA(s) = E(s) b) All transitions before s are at early transition times states q before s, tA(q) = E(q) t = idle period length Dynamic Programming Compute E(s) values using dynamic programming. Suppose we know E(s') for all states s' < s.

Then, E(s) = mins' before s (time when s' transitions to s). To calculate quantity in brackets, use that: Transition to s' was at t' = E(s') with A(t') = .OPT(t'), Transition to s must be at time t s.t. A(t) = .OPT(t). Finally, if E(s) is finite for state s with power consumption rate rS .rk, then we have a strategy ending at s with c.r. . Global Bound May assume that there are no power-up costs and di,j d0,j. s Scaling to ensure that d0,i / d0,i+1 Follow-OPT c where c < 1. Power

0 d1,2 d0,3 d2,3 s 1 Strategy s 2 s 3 OPT

d0,1 d0,2 d0,1 Theorem: Get a 5.83 competitive ratio. t = idle period Open Questions Randomized strategies: global or instance-wise bounds for randomized strategies. Better lower bounds. Thank You.

Recently Viewed Presentations

  • Continuous Descent Operations (CDO) ICAO Doc 9931

    Continuous Descent Operations (CDO) ICAO Doc 9931

    Benefit-to-cost ratio of up to 9/1. Quick return of investment for all partners - 2 years. ... ATC will see the smallest quantifiable . benefit, but will see major qualitative. improvements in work processes. Summary of Costs. ICAO SIP 2012...
  • 50:50 Welcome to Who Wants to be a

    50:50 Welcome to Who Wants to be a

    A 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 $1 Million $500,000 $250,000 $125,000 $64,000 $32,000 $16,000 $8,000 $4,000 $2,000 $1,000 $500 $300 $200 $100 A: Roe v. Wade C: Gibbons v. Ogden...
  • Embedded Programming and Robotics

    Embedded Programming and Robotics

    The resistor shown can be any value from 15K to 20K. You'll get readings on A0 that range from 10 in near-darkness to 900 in bright light. Light Sensors. Light-Dependent Resistors. You must use one of the analog pins. ......
  • Matthias Blumrich, Ted Jiang, and Larry Dennison November 13 ...

    Matthias Blumrich, Ted Jiang, and Larry Dennison November 13 ...

    The further to the right a curve goes, the worse the latency and the higher a curve is, the more packets experience high latencies. So the best case is a tall skinny curve. That's what you see for the yellow...
  • Engaging Students Who Are At Risk Through Instruction To ...

    Engaging Students Who Are At Risk Through Instruction To ...

    Engaging Students Who are At Risk Through Addressing Gaps in Academic Skill and Accelerate Learning Practice 3 looks at understanding and addressing any academic weakness and skill gaps that system-involved youth may have and going beyond simple remediation by providing...
  • Things I Learned Writing FindMyPhone

    Things I Learned Writing FindMyPhone

    Overview. The goal of the Hawaii Project is to enable you to build applications that incorporate cloud services in order to enhance the end-user experience on mobile devices.
  • Local Competition - Miss Missouri

    Local Competition - Miss Missouri

    Former candidates and their family members, whether from a local, state, or national Miss America Competition or a competition similar in nature to the Miss America Competition, and regardless if they won one of said competitions, cannot judge until a...
  • Growth Networks Inc - An Overview

    Growth Networks Inc - An Overview

    Outline What is NOT covered in these slides JST's original slides Schedule Model Traffic Types IP Addressing Components Switch MetaLink Loopback Block LC Substrate Link Types Packet Formats LC Rx/Tx Design Implementation Common Router Framework (CRF) Functional Blocks for implementing...