System-Level Power Management And An Overview:Predictive Shutdown Approaches

Predictive Shutdown Approaches

Applications such as display servers, user-interface functions, and communication interfaces are “event- driven” in nature with intermittent computational activity triggered by external events and separated by periods of inactivity. An obvious way to reduce average power consumption in such applications is to shut the system down during periods of inactivity. This can be accomplished by shutting off the system clock or in certain cases by shutting off the power supply (cf. Figure 15.2).

An event-driven application will alternate between a blocked state where it stalls the CPU waiting for external events and a running state where it executes instructions. Let Tblocked and Trunning denote the average time spent in the blocked and the running states, respectively. One can improve the energy efficiency by as much as a factor of 1 + Tblocked /Trunning provided that the system is shut down whenever it is in the blocked state.

There are two key questions: (1) how to shut down, and (2) when to shut down. The first question is addressed by developing mechanisms for stopping and restarting the clock or for turning off and on the power supply. The second question is addressed by devising policies such as “shut the system down if the user has been idle for five minutes.” Although these two issues are not really independent because the decision about when to shut down depends on the overhead of shutting down the system, the predictive shutdown approaches focus primarily on the question of deciding when to shut down while being aware of the available shutdown mechanisms. Simple shutdown techniques, for example, shutting down after a few seconds of no keyboard or mouse activity, are typically used to reduce power consumption in current notebook computers. However, the event-driven nature of modern applications, together with efficient hardware shutdown mech- anisms provided by PMCs, suggests the possibility of a more aggressive shutdown strategy where parts of the system may be shut down for much smaller intervals of time while waiting for events.

In this section we explore a shutdown mechanism where we try to predict the length of idle time based on the computation history, and then shut the processor down if the predicted length of the idle time justifies the cost in terms of both energy and performance overheads of shutting down. The key idea behind the predictive approach can be summarized as follows: “Use history to predict whether Tblocked will be long enough to justify a shutdown.” Unfortunately, this is a difficult and error-prone task. One therefore has to resort to heuristics to predict Tblocked for the near future. Ref. [7,8] present approaches where based on the recent history, a prediction is made as to whether or not the next idle time will be long enough to at least break even with the shutdown overhead. Results demonstrate that for reasonable values of the shutdown overhead, the predictive approaches tend to result in sizeable energy savings compared to the greedy shutdown approach, while the performance degradation remains negligible.

Restricting the analysis to a simple event-driven model of an application program running on the SA-1100 processor and considering internally controlled transfer between RUN and STDBY states and externally controlled transfer between STDBY and SLEEP states of the processor, the system can be modeled by a partially self-power-managed PSM with only two states (cf. Figure 15.3): ON and OFF. The ON state is a macro-state representing the RUN and STDBY states of the processor and the local policy used by the processor itself to move between RUN and STNDBY states depending on the workload. The OFF macro- state is the same as the SLEEP state. The power consumption associated with the ON state is the expected power consumption in this macro-state and is calculated as a function of standby time, local transition probabilities, and energy overhead of the transitions. Transitions between ON and OFF macro-states correspond to transitions between RUN and SLEEP states and their overheads are set accordingly.

The processor starts in the ON state, and makes transitions from ON to OFF back to ON state. Let TON[i] and TOFF[i] denote the time spent by the application in the ith visit to the ON and the OFF states, respectively. Furthermore, we define TON as the average of TON[i] over all i, and similarly TOFF as the average of TOFF[i] over all i. Let TON-OFF and EON-OFF denote the time and energy dissipation overhead associated with the transfer to OFF state. TOFF-ON and EOFF-ON are similarly defined (cf. Figure 15.4). In predictive shutdown approaches the PM predicts the upcoming duration of time for which the system will be idle, TOFF[i], based on the information from the current active period, TON[i] and previous active and idle periods TON[j] and TOFF[j] for j = i – 1, i – 2, …, 1. The policy then is to transfer the processor from ON to OFF state if TOFF[i] ≥ TBE, where TBE is the duration of break-even time. The processor is then turned on (it moves from OFF to ON state) as soon as a new request for data processing comes in.

In Ref. [7], the authors proposed two different approaches for predicting TOFF[i]. The first approach uses regression analysis on application traces and calculates TOFF[i] in terms of TOFF[i − 1] and TON[i].

Notice that TOFF[i − 1] denotes the actual (and not the initially predicted) duration of the OFF time on the (i – 1)th visit to the OFF state. For their second approach, the authors simplify the analysis based on the observation that long OFF periods are often followed by short ON periods. Therefore, a simple rule is constructed whereby, based on the duration of the current ON period, TON[i], the PM predicts the duration of the next OFF period, TOFF[i], to be larger or smaller than the break-even time, TBE, and therefore, decides whether it should maintain or change the current power state of the processor.

Ref. [8] improves this approach by using an exponential average of the previous OFF periods as the predicted value for the upcoming idle period duration. More precisely,

history in the prediction. If a = 0, then TOFF[i] = TOFF[i − m], i.e., the recent history has no effect on the estimation. In contrast, if a = 1, then TOFF[i] = TOFF[i − 1], i.e., only the immediate past matters in setting the duration of the next idle period. In general, however, this equation favors near-past historical data.

For example, for a = 12 TOFF[i − 1] has a weight of 12 whereas TOFF[i − 3] has a weight of 18.

As mentioned before, when the PMC resumes the ON state from the OFF state (i.e., on system wake-up),

the PMC suffers a delay penalty of TOFF-ON having to restore the original system state. This delay penalty can have a large negative impact on the PMC’s performance. Ref. [8] circumvents this problem by proposing a prewakeup approach before the arrival time of the next event. In this approach, the system starts the activation process immediately after the predicted time interval for the current idle period. Let us consider the case where the predicted idle period is overestimated, i.e., TOff [i] = TOff [i] + d for d > 0. Two subcases are possible. (1.1) d ≤ TOFF-ON: the system wakes up after TOFF-ON and the delay penalty is (TOFF-ON – d); (1.2) d ≤ TOFF-ON: the system is awakened after TOFF-ON time units. Next, consider the case where the predicted idle period is underestimated, i.e., TOff i T i d d . Again we consider two subcases. (2.1) d ≤ TOFF-ON: thesystem will wake up after TOFF-ON and immediately starts executing the arrived computational task. There is no energy waste and the delay penalty is (TOFF-ON – d). (2.2) d > TOFF-ON: the system will wake up after TOFF-ON and remain ON for a period of (d – TOFF-ON) time units ahead of the next required computation. Energy waste is (d – TOFF-ON)PON. There is no delay penalty. In summary, the prewakeup policy results in shorter delay penalty in subcases (1.1), (2.1), and (2.2), but it results in energy waste in subcase (2.2).

To alleviate the chances for underestimation of the idle period, Ref. [8] proposes a timeout scheme which periodically examines the PMC to determine whether it is idle but not shut down. If that is the case, then it increases T est [i]. The chance of overprediction is reduced by imposing a saturation condition Several other adaptive predictive techniques have been proposed to deal with nonstationary workloads.

In the work by Krishnan et al. [16], a set of prediction values for the length of idle period is maintained. In addition, each prediction value is annotated with an indicator to show how successful it would have been if it had been used in the past. The policy then chooses for the length of next idle period the prediction which has the highest indicator value among the set of available ones. Another policy, presented by Helmbold et al. [17], also keeps a list of candidate predictions and assigns a weight to each timeout value based on how well it would have performed for past requests relative to an optimum offline strategy. The actual prediction is then obtained as a weighted average of all candidate predictions. Another approach, introduced by Douglis et al. [18], keeps only one prediction value but adaptively changes the value. In particular, it increases (decreases) the prediction value when this value causes too many (few) shutdowns. The accuracy of workload prediction can be increased by customizing predictors to a particular class of workloads. This kind of customization restricts its scope of applicability, but also reduces the difficulties of predicting completely general workloads. A recently proposed adaptive technique [19], which is specifically tailored toward hard-disk power management, is based on the observation that disk accesses are clustered in sessions. Sessions are periods of relatively high disk activity separated by long periods of inactivity. Under the assumption that disk accesses are clustered in sessions, adaptation is only used to predict the session length. Prediction of a single parameter is easily accomplished and the reported accuracy is high.

As mentioned earlier, there are periods of unknown duration during which there are no tasks to run and the device can be powered down. These idle periods end with the arrival of a service request. The decision that the online DPM algorithm has to make is when to transition to a lower power state, and which state to transition to. The power-down states are denoted by s0, …, sk, with associated decreasing power consumptions of P0, …, Pk. At the end of the idle period, the device must return to the highest power state, s0. There is an associated transition energy eij and transition time tij to move from state si to sj . The goal is to minimize the energy dissipation consumed during the idle periods. Online power-down techniques can be evaluated according to a competitive ratio (a ratio of 1 corresponds to the optimal solution). There is a deterministic 2-competitive algorithm for two-state systems, which keeps the service provider in the active state until the total energy consumed is equal to the transition energy. It is recognized that this algorithm is optimally competitive. Furthermore, if the idle period is generated by a known probability distribution, then there is an optimally competitive probability-based algorithm which is (e/(e − 1))-competitive [20]. For some systems, the energy needed and time spent to go from a higher power state to a lower power state is negligible. Irani et al. show in Ref. [14] that for such systems, the two-state deterministic and probability- based algorithms can be generalized to systems with multiple sleep states so that the same competitive ratios can be achieved. The probability-based algorithm requires information about a probability distribution, which generates the length of the idle period. In Ref. [15], Irani et al. give an efficient heuristic for learning the probability distribution based on recent history.