Energy Efficieng Voltage Scheduling for RTOS.pdf

Energy Efﬁcient Voltage Scheduling

for Real-Time Operating Systems

Trevor Pering

Prof. Robert Brodersen

EECS Department

University of California, Berkeley

Berkeley, CA 94704

pering@eecs.berkeley.edu

rb@eecs.berkeley.edu

Abstract

This paper applies the concept of real-time process

scheduling to a Dynamic Voltage Scaling (DVS) micropro-

cessor. DVS allows a microprocessor to save energy by oper-

ating at the optimal voltage for the task at hand. Efﬁcient

operation requires a new class of algorithms which we term

voltage schedulers . The necessary foundation for these algo-

rithms is presented along with the foreseen implementation

difﬁculties.

1. Introduction

The microprocessor is a signiﬁcant power drain in many

portable systems. For CMOS design, the energy-per-opera-

tion of a microprocessor is given by the equation

quency does not impact functionality because the system

was originally 50% idle. Our model assumes the processor

consumes no energy when idle.

It is important to understand that merely changing a pro-

cessor’s clock frequency is not an effective technique for

reducing energy consumption. Reducing the clock frequency

will reduce the power consumed by a processor; however, it

does not reduce the energy required to perform a given task.

Lowering the voltage along with the clock actually alters the

energy-per-operation of the microprocessor, reducing the

energy required to perform a ﬁxed amount of work.

Dynamic Voltage Scaling (DVS) is a technique that

allows a voltage scheduler routine to alter a microprocessor’s

operating voltage at run-time. The voltage scheduler analy-

ses the state of the system and determines the optimal target

voltage. One possible technique for the voltage scheduler is

to use task deadlines, a concept common in real-time operat-

ing systems, to determine the extent to which a task can be

lengthened.

This paper applies the fundamentals of real-time dead-

line scheduling to the voltage scheduling problem. Tasks

considered are aperiodic and speciﬁed by { S i ,C i ,D i }

where S i indicates the task start time, C i the computational

resources required, and D i the task deadline. Start times and

deadlines are speciﬁed as absolute times; computational

resources required are speciﬁed as execution time with the

processor running at full speed.

2. Voltage Scheduling Graphs

This section describes Voltage Scheduling Graphs

which are used to depict the interaction between voltage

schedules and tasks.

On a voltage scheduling graph, shown in Figure 1, the

X-axis represents time and the Y-axis represents processor

speed. With these axes, the computation required by a task is

proportional to the ‘area under the curve’ for that task. Pro-

cessor speed is normalized to the range [0...1].

The height of a task (processor speed) and work per-

formed ( C i ) determine its energy consumed, E i . Figure 2

contains two tasks with identical computation requirements:

their areas are equivalent. Task T 1 executes at a higher pro-

cessor speed and voltage than Task T 2 , as a result it con-

sumes more energy.

CV 2

E op

where C is the switching capacitance and V is the operating

voltage. There are three ways to reduce the energy consumed

by a microprocessor: reduce the number of operations per-

formed, reduce the switched capacitance of each operation,

and reduce the operating voltage. This paper discusses the

framework for reducing energy by run-time optimization of

the operating voltage.

The maximum clock speed of a microprocessor is given

by the relation

–

f max

------------

where V is the operating voltage from the previous equation

and c is a constant. Combining these two equations, assum-

ing a constant capacitance, yields

E op

–

f max

----------------------

E op

This equation states that there is a trade-off between energy

and delay: we can decrease the energy consumed by slowing

the processor clock and reducing the operating voltage [1].

A simple example of the energy/delay trade-off starts

with a system that operates at 100 Mhz, 3.3V, and 50% pro-

cessor utilization. Reducing the operating voltage to 2.4V,

necessitating a clock reduction to 50 Mhz, would decrease

the energy consumption by 47%. This reduction in clock fre-

S 1

D 1

S x

D 1

D 2

D 3

C 1

C 2

C 3

time

Figure 1: The Voltage Scheduling Graph

Figure 3: Optimal coincident task scheduling

C 1 = C 2

E 1 > E 2

Extending this algorithm to the general case where

is non-trivial. A simple modiﬁcation of the

above algorithm, which considers a task only if and

re-evaluates at any time , has the drawback of ini-

tially under-estimating the resources required, as in Figure 4.

This greedy algorithm also has the potential to schedule

tasks such that they no longer meet their deadlines by ini-

tially running too slowly.

S i

S k

S i

C 1

C 2

time

Figure 2: Task energy vs. computation

For simplicity, we discuss voltage schedules in terms of

processor speed and not voltage settings. It is important to

remember, however, that a change in processor speed implies

a corresponding change in operating voltage.

Because relationships with respect to voltage are nonlin-

ear, E i is not simply C i multiplied by the processor speed. For

our purposes, fortunately, it is sufﬁcient to realize that a ﬂat

schedule, i.e. one where all tasks are scheduled at the same

speed and voltage, will be more efﬁcient than one with vary-

ing speed settings. The concept is similar to a sum-of-

squares optimization with X i representing the scheduled pro-

cessor speed: given the constraint

S 1

S 2

S 3

D 1

D 2

D 3

C 2

C 3

C 1

time

Figure 4: Greedy algorithm under-estimation

Voltage scheduling speciﬁes the speed at which a pro-

cessor should run for a given interval, not necessarily which

task should run when. Vertical layering, shown in Figure 5,

is used when several tasks are potentially scheduleable dur-

ing the same time interval. One of the standard thread sched-

uling techniques, such as earliest-deadline-ﬁrst or time-

sliced, can then be used to schedule the tasks within that

interval. The vertical ordering of tasks is not signiﬁcant.

X i

, the quantity

X i 2

is minimized when

X 1

===

X 2

X n

3. Voltage Scheduling Basics

We deﬁne an optimal voltage schedule to be one for

which all tasks complete on or before deadline and the total

energy consumed is minimized. Multiple identical tasks,

where and with for all tasks,

are optimally scheduled by a constant processor speed

. This is an extreme case; real systems will rarely,

if ever, have tasks with identical start times and deadlines.

Figure 3 depicts three tasks with and differing

deadlines. For such a schedule, with ordered deadlines

, the optimal voltage schedule can be found

with the following algorithm, which runs in O( n ) time to

schedule n tasks. The intermediate workload, W i , determines

the optimal schedule for all tasks with deadlines at or before

D i . P i calculates the processor speed to use such that future

deadlines are not violated.

S 1

S 2

D 1

D 2

S i

D i

aC k

C 2

C 1

S i

time

D i

D k

Figure 5: Vertical Layering

4. Optimal Scheduling

We have developed a proof of optimality for voltage

schedules. A complete description of the proof is beyond the

scope of this paper; the important result, however, is summa-

rized by the following lemma:

For a region spanned by a given task speciﬁcation,

each point in time will either be scheduled at the

minimum speed spanned by that task or else the

task will not be scheduled to run at that point.

D i

• Let

W i

-----

C k

• Let

• For any time T , ﬁnd the minimum j s.t.

P i

MAX W k

(

)

TD j

; schedule

the processor at speed P j .

Figure 4 is therefore not an optimal schedule because tasks

T 1 and T 2 are not always scheduled at the minimum speed

spanned by their start and deadline times.

Algorithms are currently under development to opti-

mally schedule a given set of tasks. Our current working

algorithm incrementally adds a new task to an existing

schedule in O( n 2 ) time, resulting in an overall complexity of

O( n 3 ) to schedule a n tasks. This algorithm has not yet been

fully implemented and it is unclear if it will be a tractable

solution. Appendix A gives an example of this algorithm

being applied to a simple voltage schedule.

5. Task Speciﬁcation Variance

The work presented in the previous section assumes a

complete and accurate task speciﬁcation. In a real system,

however, these two assumptions may not be valid. First, prior

knowledge of a task’s start time may be unavailable. Second,

the computational resources requested by a task will only be

an estimate of the actual resources required.

Heuristic estimates can be applied to reserve computa-

tion for unspeciﬁed future tasks being introduced into a

schedule. For the greedy algorithm, the intermediate work-

load, W i , could be increased by an estimate based on the

expected processing needs of blocked tasks. Our optimal

algorithm can be augmented by inserting predicted place-

holder tasks. Both these techniques will unavoidably pro-

duce sub-optimal schedules due to the variance of task spec-

iﬁcation estimation.

The computational resources requested by a task, C i , are

only an estimate of the actual resources required. Variance

can be introduced, for example, by cache behavior, code

behavior, and interaction with other threads. In a system

without DVS, such variance is not always a crucial consider-

ation: functionality is not affected as long as the processor is

fast enough. Typical real-time systems specify C i as a worst-

case computation time. A DVS system using worst-case

speciﬁcations, however, will typically schedule tasks at

higher than necessary speeds, increasing their energy con-

sumption.

Specifying C i as the average computation time for soft

real-time systems is desirable to minimize energy. Some-

times, then, a task will miss its deadline. In such situations it

is necessary to determine the fate of the task: does it continue

execution, and if so, at what speed? A method for communi-

cating the desired behavior is needed as the ‘correct’ behav-

ior is application dependent.

For hard real-time systems missed deadlines are unac-

ceptable. In this case, the worst-case computation time can

be used, resulting in a schedule that meets timing constraints

but is not always energy-optimal.

6. Related Work

[5] ﬁrst presented the idea of voltage scaling within the

context of general-purpose microprocessor systems. Their

algorithms use interval based scheduling: each ﬁx-sized time

interval runs at a constant processor speed. The processor

speed used is based on the activity of previous intervals. This

technique has the advantage of an easy implementation, but

the disadvantage of sub-optimal results.

In [4], we apply cycle-level simulations of the algo-

rithms of [5] to several deadline-based applications, such as

MPEG and audio stream processing. Our results indicate that

interval-based voltage scheduling is effective, realizing up to

a 70% reduction in system energy. However, some applica-

tions fall signiﬁcantly short of optimal. Additionally, the efﬁ-

ciency realized is extremely dependent on the interval

length, making it difﬁcult to choose one interval such that all

applications are scheduled effectively.

[3] presents the design of a processor core which uses

voltage scaling to run at the minimum voltage necessary for

operation at a given input clock frequency. Their design

demonstrates the feasibility of voltage scaling, but does not

allow direct software control over the processor speed.

Our research group is currently under development of a

DVS microprocessor with silicon expected September 1998.

We estimate our processor will consume 1.8mW at 8MHz/

1.1V and 220mW at 100MHz/3.3V in a 0.6

m process. We

implement the ARM8 instruction set with a 16kB uniﬁed on-

chip cache.

In our system, a voltage scheduler can set the target

clock frequency through the co-processor at a resolution of

1 MHz. The operating voltage is then set by a feedback loop

which compares the current and target frequencies. Expected

transition time is ~10

s, worst-case.

7. Summary

This paper presents a foundation for energy-efﬁcient

Dynamic Voltage Scaling (DVS) microprocessors using con-

cepts found in real-time operating systems. Several algo-

rithms, both sub-optimal and optimal, are discussed for the

voltage scheduling problem. We plan to implement these

algorithms on a DVS microprocessor that is currently under

design.

Implementation details, such as the variance in task

computation times, are discussed. Voltage scheduling intro-

duces additional variance into the completion time of a task

which impacts the performance of soft and hard real-time

systems.

Acknowledgments

This work was funded by DARPA and made possible by

cooperation with Advanced RISC Machines Ltd (ARM). The

authors would like to thank Eric Anderson for his help on,

and proof of, the optimal scheduling algorithm.

References

[1]

T. Burd and R. Brodersen, “Energy Efﬁcient CMOS

Microprocessor Design,” Proc. 28th Hawaii Int’l Conf.

on System Sciences, Vol. 1, Jan. 1995.

[2] A. Burns and A. Wellings, Real-Time Systems and Pro-

gramming Languages, second edition, Addison-Wesley,

1997.

[3] T. Kuroda, et. al., “Variable Supply-Voltage Scheme for

Low-Power High-Speed CMOS Digital Design,” IEEE

Journal of Solid-State Circuits , Vol. 33, No. 3, March

1998.

[4] T. Pering, T. Burd, and R. W. Brodersen, “The Simula-

tion and Evaluation of Dynamic Voltage Scaling Algo-

rithms,” Int’l Symp. on Low Power Electronics and

Design , August 1998.

[5] M. Weiser, “Some computer science issues in ubiqui-

tous computing,” Communications of the ACM , Vol. 36,

pp. 74-83, July 1993.

Appendix A: Voltage Scheduling Example

This section gives an example of our current algorithm

for creating an optimal voltage schedule. It is based on the

discussion in Section 4. The task block placed below the

time axis represents the new task, or portion thereof, that has

yet to be scheduled. Complexity analysis:

• n tasks to schedule

•O( n ) speed settings to consider for each task

•O( n ) linked tasks requiring adjustment for each setting

• Total complexity: O( n 3 )

S 1

S 3

D 1

S 2

D 3

D 2

C 3

C 2

C 1

time

Remaining to add:

C 3

Step 2: Increase the speed of linked tasks ( T 2 , T 3 )

to the minimum speed of adjacent task T 1 .

Link T 1 to T 3 because it is spanned by T 3

and scheduled at an equal speed.

S 1

S 3

D 1

S 2

D 3

D 2

C 3

C 1

C 2

time

Remaining to add:

C 3

Step 3: Increase the speed of linked tasks ( T 1 , T 2 ,

T 3 ) until T 2 is completely pushed-out of the

range spanned by T 3 . T 2 is no longer consid-

ered ‘linked’ to T 1 .

S 1

S 3

D 1

S 2

D 3

D 2

C 1

C 2

time

S 1

S 3

D 1

S 2

D 3

D 2

New task to add:

C 3

C 1

C 3

C 2

Step 0: Initial schedule and new task ( T 3 ) to add.

time

Remaining to add:

Step 4: Increase the speed of linked tasks ( T 1 , T 3 )

until T 1 is completely pushed-out of the

range spanned by T 3 . T 3 is then no longer

linked to any other task.

S 1

S 3

D 1

S 2

D 3

D 2

C 1

C 3

C 2

time

S 1

S 3

D 1

S 2

D 3

D 2

Remaining to add:

C 3

C 1

C 2

Step 1: Fill in idle time spanned by T 3 . Link T 2 to

T 3 because T 2 intersects T 3 and they are

scheduled at the same speed setting.

time

Step 5: Add remaining computation to schedule.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: