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.
