algorithm aLG-d: In an idle period first remain in the active state. After b/r time units, if the period has not ended yet, transition to the sleep state.

It is easy to prove that ALG-D is 2-competitive. We only need to consider two cases. If r T < b, then ALG-D consumes rT units of energy during the idle interval and this is in fact equal to the consumption of OPT. If r T ³ b, then ALG-D first consumes r . b/r = b energy units to remain in the active state. An additional power-up cost of b is incurred at the end of the idle interval. Hence, ALG-D’s total cost is 2b, while OPT incurs a cost of b for the power-up operation at the end of the idle period.

It is also easy to verify that no deterministic online algorithm can achieve a competitive ratio smaller than 2. If an algorithm transitions to the sleep state after exactly t time units, then in an idle period of length t it incurs a cost of tr + b while OPT pays min{rt, b} only.

We remark that power management in two-state systems corresponds to the famous ski-rental problem, a cornerstone problem in the theory of online algorithms, see, for example, Irani and Karlin. 26

Interestingly, it is possible to beat the competitiveness of 2 using ran-domization. A randomized algorithm transitions to the sleep state according to a probability density function p(t). The probability that the system powers down during the first t0 time units of an idle period is ò0t0p(t)dt. Karlin et al. 28 determined the best probability distribution. The density function is the exponential function ert/b, multiplied by the factor to ensure that p(t) integrated over the entire time horizon is 1, that is, the system is definitely powered down at some point.

algorithm aLG-r: Transition to the sleep state according to the probability density function

ALG-R achieves a considerably
improved competitiveness, as com-
pared to deterministic strategies.
Results by Karlin et al. 28 imply that
ALG-R attains a competitive ratio of
number. More precisely, in any idle
period the expected energy consump-
tion of ALG-R is not more than
times that of OPT. Again, is the best
competitive ratio a randomized strat-
egy can obtain. 28

 

Karlin et al. 28 proposed the following strategy that, given Q, simply uses the best algorithm ALGt. algorithm aLG-P: Given a fixed Q, let AQ be the deterministic algorithm ALGt that minimizes Equation 1.

Karlin et al. proved that for any Q, the expected energy consumption of

ALG-P is at most times the expected optimum consumption.

systems with multiple states

Many modern devices, beside the active state, have not only one but several low-power states. Specifications of such systems are given, for instance, in the Advanced Configuration and Power Management Interface (ACPI) that establishes industry-standard interfaces enabling power management and thermal management of mobile, desktop and server platforms. A description of the ACPI power management architecture built into Microsoft Windows operating systems can be found at http://www. microsoft.com/whdc/system/pnppwr/ powermgmt/ default.mspx. 1

Consider a system with l states s1, …, sl. Let ri be the power consumption rate of si. We number the states in order of decreasing rates, such as, r1 > … > rl. Hence s1 is the active state and sl represents the state with lowest energy consumption. Let bi be the energy required to transition the system from si to the active state s1. As transitions from lower-power states are more expensive we have b1 £ … £ bl. Moreover, obviously, b1 =

0. We assume again that transitions from higher-power to lower-power states incur 0 cost because the corresponding energy is usually negligible. The goal is to construct a state transition schedule minimizing the total energy consumption in an idle period.

Irani et al. 24 presented online and offline algorithms. They assume that the transition energies are additive, such as, transitioning from a lower-power state sj to a higher-power state si, where i < j, incurs a cost of bj − bi. An

figure 1. illustration of the optimum cost in a four-state system.

 

Energy State 2 State 1

State 3

State 4