addition to the active state there can
be, for instance, standby, suspend,
sleep, and full-off states. These states
have individual power consumption
rates. The energy incurred in transitioning the system from a higher-power to a lower-power state is usually
negligible. However, a power-up operation consumes a significant amount
of energy. Over time, the device experiences an alternating sequence of
active and idle periods. During active
periods, the system must reside in the
active mode to perform the required
tasks. During idle periods, the system
may be moved to lower-power states.
An algorithm has to decide when to
perform the transitions and to which
states to move. The goal is to minimize
the total energy consumption. As the
energy consumption during the active
periods is fixed, assuming that prescribed tasks have to be performed, we
concentrate on energy minimization
in the idle intervals. In fact, we focus
on any idle period and optimize the
energy consumption in any such time
window.
This power management problem
is an online problem, that is, at any time
a device is not aware of future events.
More specifically, in an idle period,
the system has no information when
the period ends. Is it worthwhile to
move to a lower-power state and benefit from the reduced energy consumption, given that the system must finally
be powered up again at a cost to the
active mode?
Performance analysis: Despite the
handicap of not knowing the future,
an online strategy should achieve a
provably good performance. Here
the algorithms community resorts to
competitive analysis, where an online
algorithm ALG is compared to an optimal offline algorithm OPT. 38 OPT is an
omniscient strategy that knows the
entire future and can compute a state
transition schedule of minimum total
energy. Online algorithm ALG is called
c-competitive if for every input, such
as, for any idle period, the total energy
consumption of ALG is at most c times
that of OPT.
Competitive analysis provides a
strong worst-case performance guar-
antee. An online strategy must per-
form well on all inputs (idle periods)
that might even be generated by an
adversary. This adversarial scenario
may seem pessimistic but it is consis-
tent with classical algorithm analysis
that evaluates strategies in terms of
their worst-case resources, typically
running time or memory require-
ments. In this section, we will mostly
study algorithms using competitive
analysis but will also consider perfor-
mance on inputs that are generated
according to probability distributions.
systems with two states
Consider a two-state system that may
reside in an active state or in a sleep
state. Let r be the power consumption rate, measured in energy units
per time unit, in the active state. The
power consumption rate in the sleep
mode is assumed to be 0. The results
we present in the following generalize to an arbitrary consumption rate
in the sleep mode. Let b energy units,
where b > 0, be required to transition
the system from the sleep state to the
active state. We assume that the energy
of transitioning from the active to the
sleep state is 0. If this is not the case,
we can simply fold the corresponding energy into the cost b incurred in
the next power-up operation. The system experiences an idle period whose
length T is initially unknown.
An optimal offline algorithm OPT,
knowing T in advance, is simple to formulate. We compare the value of rT,
which is the total energy consumed
during the idle period when residing
in the active mode, to the power-up
cost of b. If r T < b, OPT remains in the
active state throughout the idle period
as transitioning between the active
and sleep modes costs more. If r T ³ b,
using the sleep mode is beneficial. In
this case OPT transitions to the sleep
state right at the beginning of the idle
period and powers up to the active
state at the end of the period.
The following deterministic online
algorithm mimics the behavior of OPT,
which uses the sleep mode on idle
periods of length at least b/r.