# ICS 269, Winter 2004: Theory Seminar

## 27 Feb 2004:

A Scheduling Model for
Reduced CPU Energy

John Augustine

The energy usage of computer systems is becoming an important
consideration, especially for battery operated systems. Various
methods
for reducing energy consumption have been investigated, both at the
circuit level and at the operating systems level. In this paper, we
propose a simple model of job scheduling aimed at capturing some key
aspects of energy minimization. In this model, each job is to be
executed between its arrival time and deadline by a single processor
with variable speed, under the assumption that energy usage per unit
time, *P*, is a convex function of the processor speed *s*.
We give an
off-line algorithm that computes, for any set of jobs, a minimum-energy
schedule. We then consider some on-line algorithms and their
competitive
performance for the power function
*P*(*s*) = *s *^{p}, where *p* is
greater than or equal to 2. It is
shown that one natural heuristic, called the Average Rate Heuristic,
uses at most a constant times the minimum energy required. The
analysis
involves bounding the largest eigenvalue in matrices of a special
type.

From:
Frances Yao, Alan J. Demers, Scott Shenker: A Scheduling Model for
Reduced CPU Energy. FOCS 1995 : 374-382.