Using Voltage and Frequency Adjustments toManage Dynamic Power - Computer Architecture Techniques for Power-Efficiency - page 27

the processor in power consumption). In this situation, the scheduling algorithms described
here may not be applicable.
The scheduling algorithms studied by Wiser et al. are meant to minimize the time spent
in the system's idle loop for short bursts of idle activity. Instead of actually implementing
these algorithms in a real system, Wiser et al. collected traces and used them to model the
effects on the total power consumption of the processor. The traces contain timestamps of
context switches, entering and exiting the system idle loop, process creation and destruction,
and waiting or waking up on events. They come from workstations running a variety of different
workloads, such as software development and other typical engineering tasks. To prevent whole
system shut-down (processor, display, disk), any period of 30s or longer with a load below 10%
was excluded from consideration.
All three scheduling algorithms are interval-based. Traces are divided into fixed-length
intervals, and the proportion of time that the CPU is active within each interval is computed
individually. At the end of each interval, the speed of the processor for the upcoming interval is
decided. The goal is to minimize—eliminate if possible—idle time. If, however, the quantum
deadline is missed, i.e., the processor cannot finish its assigned work within the quantum limits,
any unfinished work spills over to the next quantum. From the three scheduling algorithms,
the first two are impractical since they can look into the future of the trace data, while the third
is a plausible candidate for implementation.
OPT, FUTURE, and PAST : OPT is a simplified Oracle algorithm that perfectly elimi-
nates idle time in every quantum by stretching the run times in a trace. It can look arbitrarily far
into the future. It provides a reference point for scheduling all work in a power-optimal way.
However, it makes several over-simplifications. First, it does not make a distinction between
“soft” and “hard” idle time. The hard idle time is necessary waiting (e.g., for I/O) that should
not be stretched or compressed. In addition, it does not care on how long a job is delayed, as
long as it finishes by the end of the trace. This may result in very slow response times especially
for the interactive jobs.
FUTURE is a simple modification of OPT that can only look into the subsequent interval.
The repercussion of this choice is that no work is delayed past the end of the next interval. For
large intervals, FUTURE approaches OPT in terms of energy savings, while for smaller ones
it falls behind. Like OPT, FUTURE is also unrealistic for an on-line implementation, since it
still peeks into the future.
The PAST algorithm, which is the only one of the three suitable for an on-line imple-
mentation, looks into the past in order to predict the future. As with the previous algorithms,
its interval size can be adjusted for different results. PAST works under the assumption that
the next interval is similar to the current one. Although this may seem naive, PAST stands up
quite well even compared to newer, more sophisticated, scheduling algorithms [ 89 ].