Machine Learning for Adaptive Power Management.pdf

Volume 10

Issue 04

Published, November 9, 2006

ISSN 1535-864X

DOI: 10.1535/itj.1004.05

Intel ®

Technology

Journal

Autonomic Computing

Machine Learning for

Adaptive Power Management

More information, including current and past issues of Intel Technology Journal, can be found at:

http://developer.intel.com/technology/itj/index.htm

Machine Learning for Adaptive Power Management

Georgios Theocharous, Corporate Technology Group, Intel Corporation

Shie Mannor, Department of Electrical and Computer Engineering, McGill University

Nilesh Shah, Corporate Technology Group, Intel Corporation

Prashant Gandhi, Corporate Technology Group, Intel Corporation

Branislav Kveton, Department of Computer Science, University of Pittsburgh

Sajid Siddiqi, School of Computer Science, Carnegie Mellon University

Chih-Han Yu, Department of Computer Science, Harvard University

Index words: power management, machine learning

ABSTRACT

Adaptive Power Management (APM) systems for laptops

decide when to place a component into various power-

saving states given the user activity. The long-term goal of

an APM system is to maximize the battery life while

minimizing the annoyance to the user. The state-of-the-art

in commercial solutions is timeout policies. These policies

switch components into their low power states based on

thresholds of periods of inactivity. Unfortunately, such

methods not only waste power during the periods of

inactivity, but also needlessly annoy the user when they

turn off components at inappropriate times. Research in

APM, on the other hand, has focused more on modeling

system dynamics and not on usage patterns. We propose a

system that learns when to turn off components based on

different user patterns. We describe the challenges of

building such a system and progressively explore a range

of solutions. We experiment with a direct approach that

predicts when to turn off a component given usage

features (e.g., historical keyboard and mouse activity,

active application, history of network traffic, and history

of CPU utilization). To improve performance of the direct

approach we partition data based on the context and train

the learning algorithms separately for each context.

Context could be past idleness or any partitioning of the

data that improves performance. We then propose a

model-based approach that captures the temporal dynamic

of system and user state, the cost of power and user

annoyance, as well as the effect of power-saving actions

on the user and system. Our direct approach is validated

on a large data corpus collected from multiple real users

where results show a considerable improvement over

traditional timeout methods.

INTRODUCTION

Adaptive Power Management (APM) attempts to increase

the perceived battery life of a laptop by turning off certain

components when their services are not going to be

needed. Of course, it is not known in advance which

services will be needed and when. Moreover, the

perceived impact of having certain services not available

is much greater than the perceived impact of others. The

goal of APM is to extend the battery life as much as

possible with an acceptable perceived loss of

performance. APM, as opposed to non-adaptive power

management, attempts to make better decisions with time

and to adapt to individual users.

APM is an example of an autonomic system. The

autonomics concept is derived from the human body’s

autonomic nervous system that regulates individual organ

function, and for the most part is not subject to voluntary

control. An autonomic computing system controls the

functioning of computer applications or systems without

explicit user input. The goal of autonomic computing is to

create systems that are self-managing, self-healing, and

self-protecting. Autonomic computing promises to reduce

expenditures associated with operations, maintenance, and

support, and to significantly improve the end user’s

experience.

Autonomic systems ensure smooth and uninterrupted

operation by monitoring the system state, diagnosing

problems, identifying user context, and executing actions

to fix the problems. For example, an APM system

monitors the user and laptop state, diagnoses the user

mood or context, and changes power states such that the

user is not noticeably impacted. Autonomic systems need

to naturally reason about uncertainty in both perception

299

Machine Learning for Adaptive Power Management

Intel Technology Journal, Volume 10, Issue 4, 2006

and action. In an APM system, perception uncertainty

arises from the fact that the user context cannot be directly

observed from sensors, such as keyboard and mouse

activity, or the currently active application. Actions that

turn off components also generate uncertainty. They create

uncertainty in terms of the time it takes to turn a

component on and off and in terms of the effect it would

have on the user’s context. For example, placing the

machine on standby does not always take the same amount

of time and sometimes the Operating System (OS) does

not even allow it. If the user context is for example a

measure of idleness, then going to standby, could either

increase idleness if it succeeds or decrease it if it fails,

hence the uncertainty. If the user context is a measure of

the users’ mode of operation (e.g., working, browsing for

fun) then going to standby could again change the context

in an unpredictable manner.

Figure 1: A classic sequential decision-making task

under uncertainty. The doctor performs treatments

and diagnostic tests on the patient, which change in a

stochastic manner the internal state of the patient. The

doctor then observes symptoms. The optimal policy is

one where in the long run the patient is made well.

Modeling real-world phenomena as stochastic processes

and sequential decision-making under uncertainty (see

Figure 1) are widely used paradigms in artificial

intelligence. The process of estimating these stochastic

process models and the computation of optimal policies

fall into the category of machine learning. Machine

learning refers to the problem of constructing computer

programs that automatically improve with experience. The

simplest class of machine learning algorithms are

classifiers, which are functions that learn (from examples)

to map input patterns to output classes. For the APM

domain, our algorithms learn to map laptop usage patterns

(at the OS level) into power management actions as shown

in Figure 2.

Senses user

activity and

annoyance

User-OS

Interaction

Actions for PM

In this paper, we first summarize past approaches to the

APM problem and then describe a machine-learning

approach that maps user patterns to power-saving

sections. Our approach outperforms current commercial

solutions such as timeout policies. We then propose a

more general model-based approach that relies on

building stochastic process models. We finally discuss the

potential application of such models to other domains.

Senses OS

activity

APM

Actions for

OS-HW

Interaction

Senses hardware activity

and power consumption

Figure 2: APM takes as input user and system activity

and issues power management actions to the OS and to

the hardware

Machine Learning for Adaptive Power Management

300

Intel Technology Journal, Volume 10, Issue 4, 2006

and their state space is mostly an active/not active

indication. State transitions are estimated from data and

the optimization is done off-line. A somewhat more

complex stochastic optimization model is presented in

[12]. The model used in this work is a non-stationary

process where there are several modes. For each mode,

the process is a Markov decision process. In general, these

models are not realistic because they assume that the state

variables can be directly observed from sensors. Our work

differs from this line of work in that we explicitly take into

consideration the user activity (usually not directly

observable) and also consider the perceived performance.

ADAPTIVE POWER MANAGEMENT

An APM system maps the computer system (OS and

hardware) activity and the user activity into power

management actions as shown in Figure 2. The goal of

such a system is to maximize battery life while minimizing

the impact on the user. In this section, we describe the

state-of-the-art in APM solutions and our proposition for

explicit consideration of the user’s context and perception.

Past Approaches

Currently used power management techniques are based

on timeout policies . These policies shut down a

component after it is not used for some predefined time.

The aggressiveness of the scheme is reflected by the

length of the timeout before a specific component is shut

down. For example, Windows* OS has several built-in

power management schemes that allow the user to choose

between different levels of aggressiveness. The user is

expected to switch manually between these schemes.

Timeout policies are fairly simple and robust. They are,

however, non-adaptive and may be too fast or too slow to

react.

User-Based APM

The papers mentioned above attempt to use dynamic

models estimated from data. To the best of our

knowledge, they are all based on relatively small and

simulated amounts of data. Most importantly, these works

do not model user state in their decision making, which we

believe to be essential.

Monitoring user activity (i.e., context) from sensor

observations is a well-studied problem, e.g., see [6].

However, there are relatively few instances where activity

monitoring is linked to decision making, which is the goal

of APM. In this paper, we focus on making the actual

decision: which component to turn off and when. With

this goal in mind, we introduce a novel representation of

context, namely the idleness duration variable, to describe

the state of the user. Though simple, this is an effective

way to characterize context for this decision problem in

the power management domain. We also address the issue

of how the user perceives the performance degradation (a

measure we call annoyance ).

Applying machine-learning techniques to the APM

problem is in its infancy. In [16] a simple predictive

approach for deciding if to turn a component on or off was

investigated. The authors attempt to predict the length of

the idle period and claim that typically a short idle time is

followed by a long active time and vice-versa (i.e., the

prediction is based on the recent history). The decision

rule eventually recommended that the component be shut

down if it was used for less than some threshold value.

They explored two approaches: a threshold value that is

determined using regression and a threshold value that is

manually obtained from data. In both approaches, the

threshold parameters were obtained based on data in a

non-adaptive manner. The approach of [7] is to predict the

future delay as an exponentially weighted sum of recent

delays. Our work uses learning techniques that focus more

on the adaptive and dynamic aspects of power

management.

Reducing the power consumption to the bare minimum

can be easily done by moving to standby mode on every

occasion. This, however, is not very useful since a power

management system applying such a policy will not be

very usable. It is clear that a “good” policy should

minimize power consumption. Therefore, one has to

consider the tradeoff between the power savings and the

perceived performance degradation, i.e., the annoyance. In

order to examine this tradeoff, we look at tradeoff-type

plots, where one axis shows the power saving and the

other shows the level of annoyance. With no power

savings, all the components are on all the time and the

annoyance is assumed to equal zero. As the annoyance

increases, the power savings may increase. Still, the power

savings will never be more than the minimal power

consumption level needed to perform the required

operations. Figure 3 demonstrates a power-saving

annoyance curve. Different users may choose different

points on the power-saving annoyance curve according to

their desired tradeoff.

Several papers considered policy optimization in the

context of power management ([1], [14], [15]). According

to this approach, a single Markov Decision Process

(MDP) or a Semi-Markov Decision Process (SMDP) is

constructed and solved using linear programming. An

MDP is a stochastic process model of the state of the

world and costs of actions (see Figure 6). An SMDP is an

MDP where the next state does not only depend on the

current state but also on how long the current state has

been active. The Markov property, which states that the

current state is sufficient for predicting the next state, is

violated, hence the semi-Markov terminology. The

Markov models used in these works are extremely simple

Machine Learning for Adaptive Power Management

301

Intel Technology Journal, Volume 10, Issue 4, 2006

THE DIRECT APPROACH

In our direct policy approach, we trained a separate

classifier for each action. The input is the sensor

measurements and features, and the output is whether to

turn the component on or off.

The sensors that were sampled every second were active

application, keyboard and mouse activity, CPU load, and

network traffic. Out of these sensors we constructed

various features, such as sums, decayed sums, averages,

and gradients of sensor readings over different past

windows.

The labels for the classification problems were generated

by heuristic laws after going through the trace of sensor

readings. We used several ad-hoc rules to determine the

labels, such as, if turning WLAN off and packets are sent

within 30 seconds, determines the action to turn WLAN

off to be a mistake. This labeling scheme gives a “target”

policy that is guaranteed not to annoy the user because it

will never turn off components when needed in the next

fixed look-ahead.

Figure 3: A tradeoff curve for power savings versus

annoyance. The power savings cannot pass a certain

threshold as shown with the converging curve to be

approximately 80%. This curve was produced from a

real trace, where the points on the curve represent

various timeout policies. The furthest top right point

represents a timeout parameter of 1 second and the

furthest lower left, a timeout parameter of 600

seconds.

As a yardstick for a learning algorithm, we used logistic

regression, k-nearest-neighbors and the C4.5 decision tree.

These algorithms are simple to use and produced more or

less similar results. Since these algorithms are standard,

we do not describe them here. We refer the reader to [5].

Many classifiers (such as logistic regression) have some

threshold function. For example, if the outcome is

probabilistic between the two classes, then the threshold is

the minimum probability for deciding the first class. By

varying the threshold, we can make the resulting classifier

more or less aggressive leading to different points on the

annoyance-power-saving curve.

Quantifying the power savings is straightforward and it

can be done in Watts per second, or the proportion of time

a component is off. In our experiments, we considered

four components: turning off the LCD, turning off the

WLAN, running the CPU in low frequency, and placing

the laptop in standby mode. When the laptop is turned on

or in standby mode, it consumes 18.5 and 0.7 Watts per

second, respectively. Turning off the LCD, or the WLAN,

or switching the CPU into its low-frequency mode, results

in the consumption of 14, 17.5, and 15 Watts per second,

respectively.

Quantifying the annoyance is trickier. Essentially, the

problem is that annoyance is a subjective measure and

different users may feel a different level of annoyance for

the same sequence of actions. Based on interviews with

users, we decided to measure the annoyance as follows. If

the system decided by mistake to turn off the CPU,

WLAN, and LCD, it leads to annoyance of 1, 3, and 7,

respectively. Moving to a standby mode by mistake leads

to annoyance of 10. We know if turning off a component

was a mistake since we can detect if this component is

needed or not after it was turned off. For example, if we

turn the LCD off and after a few seconds the user opens a

new application and clicks the mouse we can safely

assume that turning the LCD off was a mistake. The

different annoyance coefficients represent a collective and

subjective estimate of how much more annoying is turning

off one component compared to turning off another.

The second yardstick we used is timeout-based policies.

The decision to turn off a component in such a policy is

according to the time passed since it was last used–we turn

it off if it was not used for more than some predefined

threshold. We can control the level of annoyance by

varying the threshold (the larger the threshold the less

aggressive the timeout policy and the less annoyance we

will observe).

Context-Based Policy Learning

For context-based policy learning, we explicitly take into

consideration the user context variable. The idea is to

separate the data for each value of the context variable

and then train a separate classifier for each data partition.

We then choose the decision threshold for each classifier

such that the overall power savings are maximized. As we

show in our experiments, this approach performs better

than naïve classifiers trained on all data.

Machine Learning for Adaptive Power Management

302

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: