Clock Scheduling Algorithms

In scheduling the voltage at which a system operates and the frequency at which it runs, a scheduler faces two tasks: to predict what the future system load will be (given past behavior) and to scale the voltage and clock frequency accordingly. These two tasks are referred to as prediction and speed-setting [6]. We consider one scheduler better than another if it meets the same deadlines (or has the same behavior) as another policy but reduces the clock speed for longer periods of time.

The schedulers we implemented are interval schedulers, so called because the prediction and scaling tasks are performed at fixed intervals as the system runs [7]. At each interval, the processor utilization for the interval is predicted, using the utilization of the processor over one or more preceding intervals. We consider two prediction algorithms originally proposed by Weiser et al. [7]: PAST and $\mbox{AVG}_{\mbox{\em N}}$. Under PAST, the current interval is predicted to be as busy as the immediately preceding interval, while under AVG, an exponential moving average with decay $N$ of the previous intervals is used. That is, at each interval, we compute a ``weighted utilization'' at time $t$, $W_t$, as a function of the utilization of the previous interval $U_{t-1}$ and the previous weighted utilization $W_{t-1}$. The $\mbox{AVG}_{\mbox{\em N}}$ policy sets $W_t = \frac{N \times W_{t-1} + U_{t-1}}{N+1}$. The PAST policy is simply the $\mbox{AVG}_{\mbox{\em0}}$ policy, and assumes the current interval will have the same resource demands as the previous interval.

The decision of whether to scale the clock and/or voltage is determined by a pair of boundary values used to provide hysteresis to the scheduling policy. If the utilization drops below the lower value, the clock is scaled down; similarly, if the utilization rises above the higher value, the clock is scaled up. Pering et al. [8] set these values at 50% and 70%. We used those values as a starting point but, as we discuss in Section 5.3, we found that the specific values are very sensitive to application behavior.

Deciding how much to scale the processor clock is separate from the decision of when to scale the clock up (or down). The SA-1100 processor used in the Itsy supports 11 different clock rates or ``clock steps''. Thus, our algorithms must select one of the discrete clock steps. We use three algorithms for scaling: one, double, and peg. The one policy increments (or decrements) the clock value by one step. The peg policy sets the clock to the highest (or lowest) value. The double policy tries to double (or halve) the clock step. Since the lowest clock step on the Itsy is zero, we increment the clock index value before doubling it. Separate policies may be used for scaling upwards and downwards.