Dynamic Voltage ScalingDynamic Voltage SchedulingBackground Work in DVSInterval Scheduling (adjust clock based on past window, no process reordering involved)Implementation of Interval Scheduling AlgorithmsResultsEarliest Deadline FirstIntuitionSlide 11EDF-based DVS AlgorithmRelationshipsDynamic Voltage ScalingCPU can run at different clock frequencies/voltage:•Voltage scalable processors•StrongARM SA-2 (500mW at 600MHz; 40mW at 150MHz)•Intel Xscale •AMD Mobile K6 Plus•Transmeta•Power is proportional to V2 x F•Energy will be affected (+) by lower power, (-) by increased timeDynamic Voltage SchedulingQuestions addressed by the scheduler:•Which process to run•When to run it•How long to run it for•How fast to run the CPU while it runsIntuitive goal - fill “soft idle” times with slow computationBackground Work in DVS•Interval scheduling•Based on observed processor utilization•“general purpose” -- no deadlines assumed by the system•Predicting patterns of behavior to squeeze out idle times.•Worst-case real-time schedulers (Earliest Deadline First)•Stretch the work to smoothly fill the period without missing deadlines (without inordinate transitioning).Interval Scheduling(adjust clock based on past window,no process reordering involved)Weiser et. al.• Algorithms (when):•Past•AVGN• Stepping (how much)•One•Double•Peg – min or max• Based on unfinished work during previous intervaltimeCPU loadClock speedImplementation of Interval Scheduling AlgorithmsIssues:•Capturing utilization measure•Start with no a priori information about applications and need to dynamically infer / predict behavior (patterns / “deadlines” / constraints?)•Idle process or “real” process – usually each quantum is either 100% idle or busy•AVGN: weighted utilization at time tWt = (NWt-1 + Ut-1) / (N+1)•Inelastic performance constraints – don’t want to allow user to see any performance degradationResults•It is hard to find any discernible patterns in “real” applications•Better at larger time scales (corresponding to larger windows in AVGN ) but then systems becomes unresponsive•Poor coupling between adaptive decisions of applications themselves and system decision-making (example: MPEG player that can either block or spin)•NEED application-supplied information•Simple averaging shows asymmetric behavior – clock rate drops faster than ramps up•AVGN may not stabilize on the “right” clock speed - OscillationsEarliest Deadline FirstDynamic algorithmPriorities are assigned to tasks according to the deadlines of their current requestWith EDF there is no idle time prior to an overflowFor a given set of m tasks, EDF is feasible iffC1/T1 + C2/T2 + … + Cm/Tm 1If a set of tasks can be scheduled by any algorithm, it can be scheduled by EDFIntuitiontime12TiTiT2C1 = 1C2 = 1time12TiTiT2C1 = 1C2 = 1IntuitionEDF-based DVS AlgorithmSort in EDF orderInvoked when thread added or removed or deadline reachedIncludes non-runnable in scheduling decisionspeed = MAX workjdeadlinei-currenttimej<=ii<=nExponential moving averageRelationshipsPower (watts) = Voltage (volts) * Current (amps) Power (watts) = Energy (Joules) / Time (sec) Energy (Joules) = Power (watts) * Time (sec)Energy (Joules) = Voltage (volts) * Charge (coulombs)Current (amps) = Voltage (volts) / Resistance
View Full Document
Unlocking...