Scheduling for reduced CPU energy

Mark WeiserBrent WelchAlan DemersScott Shenker

article1994OSDI1,330 citations

Demonstrates through trace-driven operating system simulations that dynamically scaling CPU clock speed and voltage during low-demand periods substantially reduces processor energy consumption with minimal impact on performance.

Listen

Managing energy consumption is increasingly critical for battery-powered computing devices. While conventional energy-saving techniques focus on powering down components such as displays and disks when idle, the central processing unit (CPU) still accounts for substantial power use. Simply stopping a processor during idle periods wastes energy because alternating between maximum speed and complete idleness is inefficient. Because circuit power scales quadratically with voltage, lowering processing speed alongside voltage reduces the energy required per instruction.

The article evaluates whether an operating system can dynamically adjust CPU clock speed and voltage at fine intervals to save energy without degrading interactive performance. The authors assess these strategies using trace-driven simulations of UNIX engineering workstations running real-world workloads, including software development, document editing, and system simulations across 32 trace runs.

The findings show that dynamic speed adjustment yields substantial energy savings, typically reducing CPU power use by 25% to 65%, and reaching up to 70% in aggressive voltage scaling configurations. An operating system scheduling policy that predicts upcoming load based on recent past activity (using adjustment intervals of 20 to 30 milliseconds) provides an optimal balance, capturing most potential energy savings while keeping latency penalties minimal. Furthermore, setting the lowest allowable voltage too aggressively (such as 1.0 volt) often harms overall efficiency and increases processing delay because the processor frequently falls behind and must ramp up to maximum speed to catch up; a moderate baseline of 2.2 volts delivers comparable power savings with far fewer performance penalties.

These results demonstrate that operating systems can improve battery life significantly through dynamic power scaling rather than relying solely on idle-state hardware shutdowns. The analysis confirms that executing tasks at a steady, moderate pace is far more energy-efficient than bursting at full speed and idling. Stakeholders developing portable hardware and operating systems should implement dynamic clock and voltage scaling within task schedulers, standardizing on adjustment windows around 20 to 30 milliseconds and establishing moderate minimum voltage floors.

The conclusions are drawn from simulations that assume instantaneous voltage switching, quadratic energy reduction, and preserved process order. Consequently, physical hardware implementations may experience minor transition overheads. Further validation requires deploying and testing dynamic voltage scheduling on physical prototypes under diverse user workloads.

Palo Alto Research Center clock signal cpu energy performance CPU energy reduction scheduling algorithms CPU clock speed

Weiser et al (1994).pdf

No sufficiently relevant recommendations were found.

Paper: Real-time dynamic voltage scaling for low-power embedded operating systems, Padmanabhan Pillai et al. (2001). Extends OS-level dynamic voltage scaling into real-time embedded systems by integrating deadline guarantees into rate-monotonic and earliest-deadline-first schedulers.
Paper: Managing energy and server resources in hosting centers, Jeffrey S. Chase et al. (2001). Scales energy-aware OS resource scheduling concepts up to internet hosting centers by dynamically balancing server allocations and power management under fluctuating workloads.
Paper: Power provisioning for a warehouse-sized computer, Xiaobo Fan et al. (2007). Applies system-level power-management principles to warehouse-scale data centers by leveraging aggregate CPU utilization profiles to optimize facility power provisioning.
Paper: Dark silicon and the end of multicore scaling, Hadi Esmaeilzadeh et al. (2011). Analyzes the fundamental physical limits of dynamic voltage scaling in modern processors, demonstrating how the breakdown of Dennard scaling leads to unpowered chip area.

Cover for Scheduling for reduced CPU energy

Abstract

The energy usage of computer systems is becoming more important, especially for battery operated systems. Displays, disks, and cpus, in that order, use the most energy. Reducing the energy used by displays and disks has been studied elsewhere; this paper considers a new method for reducing the energy used by the cpu. We introduce a new metric for cpu energy performance, millions-of-instructions-per-joule (MIPJ). We examine a class of methods to reduce MIPJ that are characterized by dynamic control of system clock speed by the operating system scheduler. Reducing clock speed alone does not reduce MIPJ, since to do the same work the system must run longer. However, a number of methods are available for reducing energy with reduced clock-speed, such as reducing the voltage [Chandrakasan et al 1992][Horowitz 1993] or using reversible [Younis and Knight 1993] or adiabatic logic [Athas et al 1994]. What are the right scheduling algorithms for taking advantage of reduced clock-speed, especially in the presence of applications demanding ever more instructions-per-second? We consider several methods for varying the clock speed dynamically under control of the operating system, and examine the performance of these methods against workstation traces. The primary result is that by adjusting the clock speed at a fine grain, substantial CPU energy can be saved with a limited impact on performance.

Topics

clock signal cpu energy performance reference clock energy use central processing unit processing core energy conservation

Keywords

CPU energy reduction scheduling algorithms CPU clock speed voltage reduction adiabatic switching Frequency Excess Cycles soft idle time periodic tasks background tasks

1 Introduction
2 An Energy Metric for CPUs
3 Approach of This Paper
4 Trace Data
7 Evaluating the Algorithms
8 Discussion and Future Work
9 Conclusions
Acknowledgments
Appendix I. Description of Trace Data
References

Knowls

Knowl 1 — Quadratic Energy Scaling Model for Variable-Speed Processors
model/method
The energy efficiency of a processor is characterized by millions of instructions per joule (MIPJ), defined as:

$\text{MIPJ} = \frac{\text{MIPS}}{\text{Watts}} = \frac{\text{Instructions}}{\text{Joule}}$

Reducing CPU clock frequency alone does not increase MIPJ because reducing the clock speed by a factor $n$ reduces power consumption linearly while proportionally increasing execution time, canceling out energy savings. However, gate switching energy per clock cycle depends quadratically on the supply voltage $V$ :

$\frac{E}{\text{clock}} \propto V^2$

Because gate settling times increase at lower voltages, reducing operating voltage requires lowering the clock rate. Assuming supply voltage can be reduced linearly with clock speed $n$ (where $n \in [n_{\min}, 1.0]$ represents speed relative to full speed $1.0$ ), the energy consumed per instruction scales as $n^2$ :

$E_{\text{instruction}}(n) \propto n^2$

Under this relationship, executing a computation over a longer duration at reduced speed and voltage consumes less total energy than executing at maximum speed and entering an idle state (even if the idle state consumes zero active power). Consequently, CPU idle time in fixed-deadline intervals represents wasted energy.
Knowl 2 — Bounded-Delay Limited-Past (PAST) Dynamic Speed Setting Algorithm
algorithm
The Bounded-Delay Limited-Past (PAST) algorithm dynamically adjusts the processor clock speed at periodic scheduling intervals. It infers future workload from the most recent interval and accounts for execution cycles carried over when the previous interval was run at too low a speed.
Input: run_cycles (non-idle execution time presented in the last interval)
Input: hard_idle (idle time spent waiting on external devices)
Input: soft_idle (idle time spent waiting on user or network events)
Input: excess_cycles (unserviced execution cycles carried over from previous interval)
Input: speed (current relative CPU speed, $speed \in [min\_speed, 1.0]$ )
Input: min_speed (lower bound on allowable relative CPU speed)
Output: newspeed (updated relative CPU speed for the next interval)
Output: next_excess (excess cycles carried over to subsequent interval)
Output: energy (energy consumed during the interval)
idle_cycles = hard_idle + soft_idle
run_cycles = run_cycles + excess_cycles
run_percent = run_cycles / (idle_cycles + run_cycles)
next_excess = run_cycles - speed * (run_cycles + soft_idle)
if excess_cycles < 0.0 then
    excess_cycles = 0.0
energy = (run_cycles - excess_cycles) * speed * speed
if excess_cycles > idle_cycles then
    newspeed = 1.0
else if run_percent > 0.7 then
    newspeed = speed + 0.2
else if run_percent < 0.5 then
    newspeed = speed - (0.6 - run_percent)
else
    newspeed = speed
if newspeed > 1.0 then
    newspeed = 1.0
if newspeed < min_speed then
    newspeed = min_speed
return newspeed, next_excess, energy
The algorithm calculates run_percent by adding unserviced excess cycles to the interval's actual workload. If excess cycles exceed total idle time, the speed is immediately ramped up to $1.0$ . If load exceeds $70\%$ , speed is incremented by $+0.2$ ; if load falls below $50\%$ , speed is reduced by $(0.6 - \text{run\_percent})$ . Adjustments are clamped to $[\text{min\_speed}, 1.0]$ .
Knowl 3 — Hard versus Soft Idle Time Classification for CPU Slowdown
definition
To accurately model opportunities for dynamic speed scaling, operating system idle time is divided into two distinct categories based on the program counter and sleep reason at the time of context switching:
1. Hard Idle Time: Idle periods caused by explicit waits on external hardware devices (for example, synchronous disk operations in kernel routines such as biowait()). Hard idle time cannot be eliminated or compressed by slowing the CPU clock, as the duration is constrained by physical device latency.
2. Soft Idle Time: Idle periods resulting from waits on asynchronous or human-paced events (such as select() waiting for user keystrokes, GUI interactions, or network requests). Soft idle time can be legitimately eliminated or squeezed out by stretching process runtimes at a lower clock speed to complete just before the next event.
Knowl 4 — Theoretical Reference Schedulers: OPT and FUTURE
model/method
To evaluate the performance of online speed-scaling algorithms, two theoretical offline reference schedulers are defined:
- Unbounded-Delay Perfect-Future (OPT): Stretches all non-idle execution times across an entire trace duration (excluding extended off-periods) to eliminate all soft idle time. OPT achieves the theoretical maximum power savings, bounded only by the processor's minimum operating speed $\text{min\_speed}$ . It requires complete future workload knowledge and imposes unbounded latency on individual interactive tasks.
- Bounded-Delay Limited-Future (FUTURE): Looks ahead over a sliding time window $\Delta t$ (ranging from $1\text{ ms}$ to $400\text{ s}$ ). It optimizes energy consumption over that window by selecting a uniform clock speed that eliminates soft idle time without deferring any work past the end of the window. While FUTURE relies on non-causal lookahead, no task response is delayed longer than the chosen window length $\Delta t$ .
Knowl 5 — Simulation Framework and Assumptions for CPU Dynamic Speed Scaling
experimental setup
The evaluation framework simulates dynamic clock speed and voltage adjustment using microsecond-resolution UNIX kernel event traces (recording SCHED, IDLE_ON, IDLE_OFF, FORK, EXEC, EXIT, SLEEP, and WAKEUP events with $1.5\%$ – $7\%$ tracing overhead) under the following operating assumptions:
- Energy Model: Running at relative speed $n \in [n_{\min}, 1.0]$ consumes energy proportional to $n^2$ per instruction. Idle cycles consume zero energy. The baseline comparisons ( $1.0$ relative energy) assume full speed execution ( $n = 1.0$ ) with the CPU powered off during idle intervals.
- Speed Switching Overhead: Transitions between clock speeds and voltages are modeled as taking zero time.
- Automatic Power-Down Filter: Any trace period exhibiting $\ge 90\%$ idle time over a continuous $30$ -second window is classified as an "off period" (modeling hardware standby/power-down). Simulation is suspended until the next period with $< 90\%$ idle time, and off-periods are excluded from energy savings calculations.
- Voltage and Speed Floors: On a nominal $5.0\text{ V}$ full-speed ( $n=1.0$ ) system, minimum relative clock speeds are bounded by minimum voltage limits: $n_{\min} = 0.66$ ( $3.3\text{ V}$ ), $n_{\min} = 0.44$ ( $2.2\text{ V}$ ), and $n_{\min} = 0.20$ ( $1.0\text{ V}$ ).
Knowl 6 — Energy Savings and Interval Length Trade-Offs in PAST Scheduling
empirical result
Across 32 workstation workloads, dynamic clock adjustment with the PAST algorithm achieves total CPU energy savings ranging between $5\%$ and $75\%$ , with most workloads exhibiting $25\%$ to $65\%$ energy reduction relative to a system running at full speed and stopping the CPU when idle.

The choice of speed adjustment interval $\Delta t$ creates an inherent trade-off between energy reduction and interactive responsiveness:
- Fine Intervals ( $1\text{ ms}$ – $10\text{ ms}$ ): Frequent adjustments closely match instantaneous CPU bursts, minimizing excess cycles (accumulated delay), but achieve lower energy savings because the clock frequently ramps up to full speed during brief bursts.
- Coarse Intervals ( $50\text{ ms}$ – $400\text{ ms}$ ): Longer averaging intervals smooth out burstiness, enabling lower average speeds and achieving energy savings approaching the theoretical OPT limit ( $50\%$ savings at $3.3\text{ V}$ minimum; up to $70\%$ at $2.2\text{ V}$ minimum), but create large backlogs of excess cycles that impair interactive response.
- Optimal Operating Range: An adjustment interval of $20\text{ ms}$ to $30\text{ ms}$ balances significant energy savings with imperceptible interactive delay penalty.
Knowl 7 — Performance Penalty and Inefficiency of Excessively Low Voltage Floors
empirical result
In dynamic speed-scaling scheduling using the PAST algorithm, setting an aggressive minimum voltage floor of $1.0\text{ V}$ (relative speed $n_{\min} = 0.20$ ) frequently yields equal or worse total energy efficiency compared to a moderate floor of $2.2\text{ V}$ ( $n_{\min} = 0.44$ ), while substantially increasing latency penalties.

When the minimum speed is set too low ( $n=0.20$ ), the scheduler frequently falls behind during unexpected workload bursts, accumulating large quantities of unserviced excess cycles. The heuristic policy responds by repeatedly ramping the clock to full speed ( $n=1.0$ ) to clear the backlog. Because power consumption scales quadratically ( $n^2$ ), oscillating between $n=0.20$ and $n=1.0$ consumes more energy than running steadily at an intermediate speed ( $n=0.44$ ). Additionally, the frequency and magnitude of excess cycle delays increase significantly at $1.0\text{ V}$ relative to $2.2\text{ V}$ and $3.3\text{ V}$ .

Knowl 8 — Workstation Trace Workload Dataset Characteristics

data/table

The simulation dataset comprises 32 distinct execution traces collected from UNIX workstations during active engineering use (software development, compilation, simulation, document editing, and e-mail) as well as dedicated interactive sub-tasks (typing and scrolling in text editors mx, emacs, and fm).

Index	Trace Name	Runtime (s)	Idle Time (s)	Elapsed Time	Offtime (s)
0	feb28klono	0.906	29.094	9H 24M 20S	33828.9
1	idle1	1.509	28.653	39S	9.05
2	heur1	7.043	3.103	10S	0.0
3	emacs2	7.585	31.719	40S	0.0
4	emacs1	8.060	32.273	40S	0.0
5	mx2	8.362	30.916	39S	0.0
6	mx1	9.508	30.871	41S	0.0
7	fm1	9.544	10.594	20S	0.0
8	em3	11.669	27.580	40S	0.0
9	fm2	16.679	23.770	41S	0.0
10	mx3	20.738	18.642	39S	0.0
11	feb28dekanore	30.548	541.045	9H 24M 40S	33307.8
12	fm3	30.626	9.942	41S	0.0
13	mar1klono	41.822	1011.251	9H 55M 46S	34690.6
14	feb28mezzo	61.940	449.717	9H 24M 20S	33346.1
15	mar1cleonie	214.656	1321.591	9H 50S	30913.0
16	feb28kestrel	510.259	3362.222	1H 4M 33S	0.0
17	feb28corvina	524.248	768.857	9H 24M 41S	32588.0
18	mar1mezzo	686.340	673.204	9H 55M 36S	34375.7
19	mar1egeus	695.409	4774.911	9H 55M 35S	30263.6
20	feb28ptarmigan	1497.908	2207.005	1H 1M 41S	0.0
21	feb28fandango	1703.037	3489.760	9H 24M 17S	28665.0
22	feb28zwilnik	4414.429	29448.058	9H 24M 21S	0.0
23	mar1zwilnik	4914.787	30823.917	9H 55M 38S	0.0
24	mar1kestrel	5135.297	30599.364	9H 55M 34S	0.0
25	feb28siria	6714.109	27146.678	9H 24M 20S	0.0
26	mar1siria	8873.114	26868.738	9H 55M 37S	0.0
27	feb28egeus	9065.477	13500.028	6H 16M 6S	0.0
28	mar1corvina	10898.545	24648.883	9H 55M 57S	210.202
29	mar1ptarmigan	12416.924	23319.178	9H 55M 34S	0.0
30	mar1fandango	20101.182	15638.594	9H 55M 38S	0.0
31	mar1dekanore	25614.651	14168.562	9H 55M 58S	7191.81

The traces span from short interactive editor sessions lasting $10$ – $41\text{ s}$ to long multi-hour daily workloads lasting up to $9.9\text{ hours}$ . Total runtime varies across four orders of magnitude (from under $1\text{ s}$ to over $25{,}600\text{ s}$ ).

Coverage note — Future work proposals regarding process-class-aware scheduling (background, periodic, and foreground task classification) and abstract load generation with reordering were omitted as they are speculative directions rather than concrete evaluated contributions.

References

1.William C. Athas, Jeffrey G. Koller, and Lars “J.” Svensson. “An Energy-Efficient CMOS Line Driver Using Adiabatic Switching”, 1994 IEEE Fourth Great Lakes Symposium on VLSI, pp. 196-199, March 1994.
2.A. P. Chandrakasan and S. Sheng and R. W. Brodersen. “Low-Power CMOS Digital Design”. JSSC, V27, N4, April 1992, pp 473--484.
3.Michael Culbert, “Low Power Hardware for a High Performance PDA”, to appear Proc. of the 1994 Computer Conference, San Francisco.
4.Fred Douglis, P. Krishnan, Brian Marsh, “Thwarting the Power-Hungry Disk”, Proc. of Winter 1994 USENIX Conference, January 1994, pp 293-306
5.Mark A. Horowitz. “Self-Clocked Structures for Low Power Systems”. ARPA semi-annual report, December 1993. Computer Systems Laboratory, Stanford University.
6.Kester Li, Roger Kumpf, Paul Horton, Thomas Anderson, “A Quantitative Analysis of Disk Drive Power Management in Portable Computers”, Proc. of Winter 1994 USENIX Conference, January 1994, pp 279-292.
7.S. Younis and T. Knight. “Practical Implementation of Charge Recovering Asymptotically Zero Power CMOS.” 1993 Symposium on Integrated Systems (C. Ebeling and G. Borriello, eds.), Univ. of Washington, 1993.
8.Wilkes, John “Idleness is not Sloth”, to appear, proc. of the 1995 Winter USENIX Conf .

Citation

MLA

Weiser, M., et al. “Scheduling for Reduced CPU Energy”. The Kluwer International Series in Engineering and Computer Science, Springer US, 2007, pp. 449–71, https://doi.org/10.1007/978-0-585-29603-6_17.

APA

Weiser, M., Welch, B., Demers, A., & Shenker, S. (2007). Scheduling for Reduced CPU Energy. In The Kluwer International Series in Engineering and Computer Science (pp. 449–471). Springer US. https://doi.org/10.1007/978-0-585-29603-6_17

Chicago

Weiser, M., B. Welch, A. Demers, and S. Shenker. 2007. “Scheduling for Reduced CPU Energy”. In The Kluwer International Series in Engineering and Computer Science. Springer US. https://doi.org/10.1007/978-0-585-29603-6_17.

Harvard

Weiser, M. et al. (2007) “Scheduling for Reduced CPU Energy”, The Kluwer International Series in Engineering and Computer Science. Springer US, pp. 449–471. Available at: https://doi.org/10.1007/978-0-585-29603-6_17.

Vancouver

1. Weiser M, Welch B, Demers A, Shenker S (2007) Scheduling for Reduced CPU Energy. In: The Kluwer International Series in Engineering and Computer Science. Springer US, pp 449–471

BibTeX

@inbook{Weiser, title={Scheduling for Reduced CPU Energy}, ISBN={9780792396970}, url={http://dx.doi.org/10.1007/978-0-585-29603-6_17}, DOI={10.1007/978-0-585-29603-6_17}, booktitle={Mobile Computing}, publisher={Springer US}, author={Weiser, Mark and Welch, Brent and Demers, Alan and Shenker, Scott}, pages={449–471} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Scheduling for reduced CPU energy

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Quadratic Energy Scaling Model for Variable-Speed Processors

Knowl 2 — Bounded-Delay Limited-Past (PAST) Dynamic Speed Setting Algorithm

Knowl 3 — Hard versus Soft Idle Time Classification for CPU Slowdown

Knowl 4 — Theoretical Reference Schedulers: OPT and FUTURE

Knowl 5 — Simulation Framework and Assumptions for CPU Dynamic Speed Scaling

Knowl 6 — Energy Savings and Interval Length Trade-Offs in PAST Scheduling

Knowl 7 — Performance Penalty and Inefficiency of Excessively Low Voltage Floors

Knowl 8 — Workstation Trace Workload Dataset Characteristics

References

Citation

BibTeX

Access the Paper