Pruhs, Woeginger, Uthaisombut 2004Slide 2Warm up Exercise: n unit jobs released at time 0Slide 4Convex Program with Release TimesKKT Optimality Conditions(2)KKT Optimality ConditionsOffline AlgorithmSlide 9Algorithmic EvolutionIntuitionSlide 12What Goes Wrong With Arbitrary Work JobsSlide 14Energy/Flow Trade-Off Problem Definition [AF06]One job exampleNatural PoliciesSlide 18Bansal, Chan, Pruhs, SODA 2009Our ResultsEquation for Amortized Local Competitiveness ArgumentDerivation of Potential Function for Unit Work JobsChan, Edmonds, Pruhs 2009Outline of the TalkSpeed-up CurvesSlide 26Slide 27Slide 28Slide 29Slide 30Analysis of Equipartition and LAPSSlide 32Slide 33Slide 34Slide 35Slide 36Problem we address in SPAA 2009 paperWarm-up ProblemSlide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Algorithm Analysis1Pruhs, Woeginger, Uthaisombut 2004Qos Objective: Minimize total flow timeFlow time fi of a job i is completion time Ci – riPower Objective: constraint that at most E energy is usedWe make the simplifying assumptions that all jobs have the same (unit) amount of workOptimal job selection policy?2Pruhs, Woeginger, Uthaisombut 2004Qos Objective: Minimize total flow timeFlow time fi of a job i is completion time Ci – riPower Objective: constraint that at most E energy is usedWe make the simplifying assumptions that all jobs have the same (unit) amount of workIn this case the optimal job selection policy is First Come First Served.We thus focus on speed setting policy.wlog assume, r1 ≤ r2 ≤ … ≤ rnWarm up Exercise: n unit jobs released at time 0How much energy to devote to each job?3Warm up Exercise: n unit jobs released at time 0How much energy to devote to each job?Min Σ_i (n-i+1)/s_iSubject to Σ_i s_i^2 <= EEither by Lagrange multipliers or intuitive reasoning, s_i ≈ (n_i+1)^(1/3)4Convex Program with Release Times Min Σ_i (C_i – r_i)Subject toΣ_i (C_i – max(r_{i}, C_{i-1})^2 <= EC_i > C_{i-1}56KKT Optimality Conditions(2)Consider a strictly-feasible convex differentiable program A sufficient condition for a solution x to be optimal is theexistence of Lagrange multipliers λi such that7KKT Optimality ConditionsTotal energy of E is usedCi < ri+1 implies ρi = ρn Ci > ri+1 implies ρi = ρi+1 + ρn Ci = ri+1 implies ρn ≤ ρi ≤ ρi+1 + ρn Example:Pn = p72pn3pnpnpnp2P2 + pnr3r2r6r7Offline Algorithm89KKT Optimality ConditionsAlgorithmic Difficulties: This doesn’t tell us the value of ρn Solution: Binary searchDon’t know the value of pi when Ci = ri+1Solution: Can calculate since you know interval when job runs Don’t know if Ci < ri+1, Ci = ri+1, or Ci > ri+1Easy for high energy E, Ci < ri+1Solution: Trace out optimal schedules as E decreasesp2p2 + pnr3r210Algorithmic Evolution< <= < > => >High EnergyLow Energy> <r2r3Configurations11IntuitionIntuitively as you lose energy, should jobs run faster or slower?12IntuitionIntuitively as you lose energy, jobs should run slower, but this intuition is falseExample:Higher energy: p1=2p3 and p2 = p3Lower energy: p1 = 3p3 and p2 = 2 p3p1/p2 decreases and job 2 speeds up as we lose energy13What Goes Wrong With Arbitrary Work Jobs≤ ≤= ≤≥ ≤Arbitrary lengthOpen Question: What is thecomplexity of finding optimalflow time schedules whenjobs have arbitrary work?Optimal scheuduleis not a continuousfunction of energy E14Theorem: There is no O(1)-competitive online algorithm for the bounded energy problemProof Idea: How much energy do you give the first job that arrives?If it is not an Ω(E) then you are not O(1)-competitive15Energy/Flow Trade-Off Problem Definition [AF06]Job i has release date ri and work yiOptimize total flow + ρ * energy usedNatural interpretation: User specifies an energy amount ρ that he is willing to spend to get a unit improvement in responsee.g. If the user is willing to spend 1 ergs of energy for a 3 microsecond improvement in response, then ρ=3.wlog, ρ=1.One job example16Natural PoliciesJob Selection?Speed Scaling?17Natural PoliciesJob Selection: SRPTSpeed Scaling: Power = Number of unfinished jobsIncrease in energy objective = increase in flow objective1819Bansal, Chan, Pruhs, SODA 2009We consider allowing an arbitrary power function P(s)Only require something like P is piece-wise smooth, e.g.PowerP(s)Speed s20Our ResultsMain Theorem: SRPT + variation of natural speed scaling algorithm is 3-competitive for the objective of flow+energy for an arbitrary power function P(s) and for arbitrary work jobs Later improved to 2-competitive by Lachlan L. H. Andrew, Adam Wierman and Ao Tang.Second Theorem: HDF + variation of natural speed scaling algorithm is 2-competitive for the objective of fractional weighted flow+energy for essentially any power function P(s) and for arbitrary work and weight jobsProbably not possible to get such a result for integral weighted flow since to be competitive for weighted flow requires resource/speed augmentation [BC09]Equation for Amortized Local Competitiveness ArgumentPon(t) + Non(t) + dΦ(t)/dt ≤ c [ Popt(t) + Nopt(t) ]P(t) is the power at time tN(t) is the unfinished jobs at time ton is the online algorithmopt is the adversary/optimalΦ(t) is the potential functionc is the competitive ratio21Initial Equation: Pon + Non + dΦ/dt ≤ 2 [ Popt + Nopt ]Since Pon = Non, 2Pon + dΦ/dt ≤ 2 [ Popt + Nopt ]Guess potential Φ is a function of N = Non – Nopt so job arrivals do not affect potential functionWorst case is when Nopt = 0, or equivalently when N = Non By the chain rule dΦ/dt=dΦ/dN dN/dt. Note dN/dt=(sopt – son), 2Pon + dΦ/dN * (sopt – son) ≤ 2 * PoptSolving for Φ gives dΦ/dN ≤ 2 [ Popt – Pon] /(sopt – son)The term [ Popt – Pon] /(sopt – son) looks like the slope of P(s) around the point s=son.So set dΦ/dN = 2 dP(son)/ds = 2 dP(P-1(N))/ds  Or equivalently, Φ = 2∫0N dP(P-1(N))/ds dy Derivation of Potential Function for Unit Work Jobs22PowerPSpeed sChan, Edmonds, Pruhs 2009231. Nonclairvoyant scheduling of jobs with arbitrary speed-up curves on a multiprocessor2. Speed scaling on a uniprocessorSPAA 2009: Speed scaling and nonclairvoyant scheduling of jobs with arbitrary speed-up curves on a multiprocessorWe define and address one