Dynamic and Aggressive Scheduling Techniques for Power Aware RTS.pdf

Dynamic and Aggressive Scheduling Techniques

for Power-Aware Real-Time Systems

Hakan Aydin

, Rami Melhem

, Daniel Mosse

, Pedro Mejıa-Alvarez

Abstract

(hence the CPU speed), has recently become a major research

area for power-aware computer systems. For real-time sys-

tems, the proposed VVS schemes focus on minimizing en-

ergy consumption in the system, while still meeting the dead-

lines. Yao et al.[23] provided a static off-line scheduling al-

gorithm, assuming aperiodic tasks and worst-case execution

times. Heuristics for on-line scheduling of aperiodic tasks

while not hurting the feasibility of periodic requests are pro-

posed in [9]. Non-preemptive power aware scheduling is in-

vestigated in [8]. Concentrating on periodic tasks with identi-

cal periods, the effects of having an upper bound on the volt-

age change rate are examined in [10], along with a heuristic

to solve the problem. Slowing down the processor whenever

there is a single task eligible for execution was explored in

[21]. Lorch and Smith addressed the variable voltage schedul-

ing of tasks with soft deadlines in [14]. The static solution for

the general periodic model where tasks have potentially differ-

ent power consumption characteristics is provided in [2].

However, most of the scheduling schemes presented in these

studies, while using exclusively worst-case execution time

(WCET) to guarantee the timeliness of the system, lack the

ability to dynamically take advantage of unused computation

time. In fact, real-time applications usually exhibit a large vari-

ation in actual execution times; for example [5] reports that the

ratio of the worst-case execution time to the best-case execu-

tion time can be as high as 10 in typical applications.

Consequently, dynamically monitoring and reclaiming the

‘unused’ computation time can be (and, as we show later in

this paper, is in fact) a powerful approach to obtain consider-

able power savings and to minimize the effects of designing

the system with WCET information, which is usually a very

conservative prediction of the actual execution time. Addi-

tional improvements are possible thanks to the statistical work-

load information; in this paper, we investigate also aggressive

schemes where we anticipate the early completions of future

executions and speculatively reduce the CPU speed. This ap-

proach immediately raises two intertwined questions, namely,

(a) the level of aggressiveness under a given probability dis-

tribution of actual workload; and (b) the issue of guaranteeing

the timing constraints even in aggressive modes. It is obvi-

ous that the solutions to these problems should be simultane-

ously practical and efcient, in order to be applicable on-line.

In this paper, we address power-aware scheduling of peri-

odic hard real-time tasks using dynamic voltage scaling. Our

solution includes three parts: (a) a static (off-line) solution to

compute the optimal speed, assuming worst-case workload for

each arrival, (b) an on-line speed reduction mechanism to re-

claim energy by adapting to the actual workload, and (c) an on-

line, adaptive and speculative speed adjustment mechanism to

anticipate early completions of future executions by using the

average-case workload information. All these solutions still

guarantee that all deadlines are met. Our simulation results

show that the reclaiming algorithm saves a striking 50% of

the energy over the static algorithm. Further, our speculative

techniques allow for an additional approximately 20% savings

over the reclaiming algorithm. In this study, we also establish

that solving an instance of the static power-aware scheduling

problem is equivalent to solving an instance of the reward-

based scheduling problem [1, 4] with concave reward func-

tions.

1 Introduction

In the last decade, the research community has ad-

dressed the low power system design problems with a multi-

dimensional effort [7, 18]. Such on-going research has im-

portant implications for real-time systems design, simply be-

cause most of the applications running on power-limited sys-

tems inherently impose temporal constraints on the response

time (such as real-time communication in satellites).

The variable voltage scheduling (VVS) framework, which

involves dynamically adjusting the voltage and frequency

This work has been supported by the Defense Advanced Research Projects

Agency through the PARTS project (Contract F33615-00-C-1736).

Computer Science Department, George Mason University, Fairfax VA

22030.

E-mail: aydin@cs.gmu.edu.

Work done while the author was with

the University of Pittsburgh.

Computer Science Department, University of Pittsburgh, Pittsburgh PA

15260. E-mail: melhem@cs.pitt.edu.

Computer Science Department, University of Pittsburgh, Pittsburgh PA

15260. E-mail: mosse@cs.pitt.edu.

CINVESTAV-IPN. Seccion de Computacion, Av. I.P.N. 2508, Zacatenco,

Mexico, DF 07300.

E-mail:

pmejia@computacion.cs.cinvestav.mx.

Work

done while the author was visiting the University of Pittsburgh.

It goes without saying that dynamic reclaiming and/or aggres-

sive techniques should preserve the feasibility of the task sys-

tem (i.e., no deadline should be missed), even under a worst-

case scenario that may take place after any speed adjustment

decision.

We must note that a recent study [11] addressed dynamic

energy reclaiming issues (without speculation) in power-aware

scheduling for cyclic and periodic task models, in the context

of systems with two (discrete) voltage levels. However, sys-

tems which are able to operate on a (more or less) continuous

voltage spectrum are rapidly becoming a reality thanks to ad-

vances in power-supply electronics and CPU design [6, 17].

For example, the Crusoe processor is able to dynamically ad-

just clock frequency in 33 MHz steps [22]. To the best of

our knowledge, the concept of “speculative speed reduction”

was rst introduced by the authors in [16]; however, only tasks

sharing a common deadline were considered.

the worst-case number of processor cycles required by #%$ , will

be denoted by +,$ . Note that, under a constant speed - (given

in cycles per second), the execution time of the task # $ is . $0/

1 2

. A schedule of real-time tasks is said to be feasible if each

task # $ receives at least 45+ $ CPU cycles before its deadline,

where 46+ $87 + $ is the actual number of CPU cycles (actual

workload) of # $ .

We assume that the CPU speed can be changed between

a minimum speed - 9 $;: (minimum supply voltage necessary

to keep the system functional) and a maximum speed - 9 <>= ,

; that is, we normalize the

speed values with respect to - 9 <>= . In our framework, the volt-

and that ? 7

age/speed changes take place only at context switch time and

while state saving instructions execute. Pouwelse et al. report

in [19] that the voltage/speed change can be performed in less

than 140 D s in Strong ARM SA-1100 processor. If not negli-

$;: 7

gible, the ’voltage change overhead’ can be incorporated into

the worst-case workload of each task.

We assume that the process descriptor of the task #%$ has

two extra elds related to speed settings, in addition to other

conventional elds. The rst one, - $ , denotes the current CPU

In this paper, we identify and address three dimensions of

power-aware scheduling for real-time systems and develop ef-

cient algorithms for the periodic task model. Effectiveness

in reducing the energy consumption can be improved only by

a simultaneous consideration of these three dimensions, since

they complement each other. Thus, we present:

speed at which # $ is executing. The other eld - $ denotes the

nominal speed of # $ , which is the indicator of the “default”

speed of # $ . For each task that is dispatched, the operating

system sets - $ / -E$ , prior to any dynamic speed adjustment.

The power consumption of the processor under the speed -

is given by F GH-JI , which is assumed to be a strictly increasing

1. A static (off-line) solution to compute the optimal speed

at the task level, assuming worst-case workload for each

arrival " (Section 3). In the same section, we also show

convex function, represented by a polynomial of at least sec-

ond degree [10]. If the task #%$ occupies the processor during

the time interval K . "AL .NMPO , then the energy consumed during this

that solving an instance of the the static power-aware real-

time scheduling problem is equivalent to solving an in-

stance of the reward-based scheduling problem [1].

2. An on-line speed adjustment mechanism to dynamically

reclaim energy not used by tasks that complete without

consuming their worst-case workload (Section 4).

3. An on-line, adaptive and speculative speed adjustment

mechanism to anticipate and compensate probable early

completions of future executions (Section 5).

interval is QRG;. ">L .NMSI /

In our detailed analysis of periodic power-aware scheduling,

we will consider a set Y /[Z #

of ‘ periodic real-

time tasks. The period of # $ is denoted by ab$ , which is also

equal to the deadline of the current invocation. We refer to the

Ted invocation of task #%$ as # $Xfg . All tasks are assumed to be

independent and ready at . / ? . Hence, the ready time of # $Xfg

is & $ fg / G cih

, and its deadline is ()$Xfg /

as the total utilization of the task set under

maximum speed - 9@<A= /pB , that is, m

We dene m

. Note

that the schedulability theorems for periodic real-time tasks

[12] imply that m

We emphasize once again that, in the context of real-time

systems, all these components should be designed not to cause

any deadlines to be missed even under the worst-case scenario:

the aim is to meet the timing constraints while simulta-

neously and dynamically reducing power consumption as

much as possible .

is a necessary condition to have at

least one feasible schedule; hence, throughout the paper, we

will assume that m

Optimal Static Solution

System Model and Notation

The ready time and deadline of each real-time task #%$ will

z { |} ~ €ƒ‚„… ‡†ˆ J ! ‰ { ! Š R!k~ ‹ E

be denoted by &’$ and ()$ , respectively. The indicator of the

†Œ ~ ‹Š‰ { J Ž

Before analyzing the periodic model in depth, we cor-

relate the reward-based scheduling [1, 3] framework to the

power-aware scheduling of real-time tasks. The reward-

based scheduling framework encompasses real-time schedul-

ing models such as Imprecise Computation [13] and Increased-

worst-case workload in variable voltage/speed settings, that is,

Due to the nature of VVS, the actual execution time is dependent on the

CPU speed, and therefore the worst-case number of required CPU cycles is a

more appropriate measure of the worst-case workload (see Section 2).

Reward-with-Increased-Service [4] that exploit the timeliness

and precision trade-off. We underline that the correlation that

we prove is preserved regardless of the task model (aperi-

odic/periodic or preemptive/nonpreemptive), as long as our

aim is to reach a solution for a given (worst-case) workload.

In the reward-based scheduling framework, each real-time

task # $ comprises a mandatory part ‘ $ and an optional part

’

Before relating two scheduling problems, we observe that

the convexity of speed/power function allows us to deduce the

following (a formal proof can be found in [3]).

Proposition 1 One can safely commit to a constant CPU

speed during the execution of a task # $ requiring + $ CPU cy-

cles, without increasing the energy consumption.

are de-

noted by “ $ and ” $ , respectively. The mandatory part runs

The worst-case execution times of ‘ $ and

Note that the determination of - $ in the RT-PAS problem is

now effectively equivalent to determining the CPU time allo-

cation to #%$ , which will be denoted by —b$ G;— $ /

rst, producing an output of acceptable quality, which is sub-

sequently enhanced by the optional part within the limits of

available computational capacity. To quantify the quality im-

provement, a non-decreasing reward function • b$oGV.q$NI is associ-

. We are

now ready the establish the connection between RT-PAS and

Reward-Based Scheduling problems.

Proposition 2 Solving an instance of RT-PAS problem is

equivalent to solving an instance of Reward-Based Scheduling

problem with concave reward functions.

1 2

ated with each optional execution where .q$ 7

denotes the

service time

receives. Most of the realistic applications are

best represented by concave reward functions [1, 3, 4, 20]. In

any feasible reward-based schedule, each mandatory part must

be fully executed by the task deadline (’$ , however, the optional

Proof: To prove the statement, we will rst formulate the

computation of optimal speed values as an optimization prob-

lem. The total energy consumption, thanks to the constant

speed assumption per task, can now be expressed as Q

parts may remain partially executed by the deadlines. Now we

can formally dene the reward-based scheduling problem.

Reward-Based Scheduling Problem : Consider the

uniprocessor scheduling of a reward-based real-time task set

. Further, observe that the

minimum and maximum speed bounds impose natural lower

and upper bounds on CPU allocation of # $ .

In other words,

. Given a time point ˜š™ , determine the op-

the inequality

should be satised. Hence,

the computation of optimal CPU allocation assignments can be

formalized as an optimization problem:

minimize

timal schedule in the interval K ? L ˜ ™ O , where each mandatory

part ‘ $ complete in a timely fashion before the task deadline

/ — Z #

, and each optional part receives service for . $@7 ” $ units of

time so as to maximize the total system reward

The determination of the optimal schedule clearly involves

the computation of optimal optional service times. Noting that

the reward accrued by each optional part

(4)

subject to

(5)

œ … × N Ø Ÿ Ù

does not increase

beyond the upperbound ” $ , this computation can be expressed

(6)

Now,

consider

the

variable

transformation “Ý $

as an optimization problem where the objective is to nd . $

values M

so as to:

This transformation can be interpreted as follows: First, #%$

maximize

(1)

G;. $ Æ

units of CPU time (“manda-

tory” execution). Any allocation exceeding this minimum

amount will be considered as “optional” execution, while the

total CPU allocation ( “æ $ Æ .q$ ) can not exceed the upper bound

1 2

must be assigned at least

subject to

(2)

(3)

Finally, the more we allocate CPU time to #%$ by in-

On the other hand, the real-time power-aware scheduling

problem can be stated as follows.

Real-Time Power-Aware Scheduling (RT-PAS) Problem :

Consider a CPU with variable voltage/speed -¨GX- 9 $;: 7 - 7

creasing .q$ , the more we increase the energy savings thanks

to the speed/power relation. It is not difcult to see that,

by using the above transformation and by re-writing the op-

timization problem given by (4), (5) and (6), one reaches once

again the formulation of the general reward-based schedul-

ing problem dened by Equations (1), (2) and (3). Further,

the reward function • $ GV. $ I above is clearly concave, since

facility, where the power consumption is given by a

strictly increasing convex function F GX-JI , which is a polyno-

mial of at least second degree. Given a set

of real-time tasks, in which each task # $ is subject to a worst-

) is convex. To see this, we can use the

result from [15] stating that if ç and Ł are both convex func-

case workload of + $ expressed in the number of required CPU

/ — Z #

# : _

" L>]^]>]^L

cycles, and a time point ˜ ™ , determine the schedule and the

processor speed -JGV.PI so as to minimize the total energy con-

tions and if ç is increasing, then ç GXŁ^GV—–INI is also convex. Thus,

sumption QRG É ? L ˜š™ I /

in the interval K ? L ˜š™ O .

by setting ØbG;.q$qI /

, and observing that the multipli-

cation by GV.q$ Æ

does not affect the convexity, we justify

the concavity of • k$qG;.q$qI /

When considering the periodic task model, the execution time of each task

instance ( ˛ œ ‚ˇ ) should be considered as a separate unknown.

optimal speed for the static version is ð - / - 9@<A= / Š B ] ?l? (from

Proposition 3). If every task presents its worst-case workload

at every instance and we use EDF, then the schedule in Figure

1 ( ß ü < : ) would be obtained. Now, suppose that # completes

‰ì‰Š ! Ž J l !% ‡í o! ˆ E !– J ‰ z … l îï …

In this section, we present the static optimal solution to

the variable voltage scheduling problem for the periodic task

model, assuming that each task presents its worst-case work-

load to the processor at every instance . We underline that one

can use the equivalence obtained in Section 3.1 and the results

from [1] to justify the proposition (as formally done in [3]);

however, one can also reach the same conclusion by using the

rst principles as outlined below.

T 1

Proposition 3 The optimal speed to minimize the total energy

consumption while meeting all the deadlines is constant and

equal to ð - / “ˆç ^— Z - 9 $;: L m

T 2

. Moreover, when used along

with this speed ð

, any periodic hard real-time policy which can

fully utilize the processor (e.g., Earliest Deadline First, Least

Laxity First) can be used to obtain a feasible schedule.

T 3

Proof: First, observe that the convex nature of the power-speed

function suggests that we should try to maintain a uniform

speed while fully utilizing the CPU to the extent it is possible.

If m

Figure 1. The static optimal schedule, ß ü < :

early at . / B ? , leaving an unused computation time of 4 units

leads clearly to

a schedule which is fully utilized (i.e., no idle time), through

stretching out each task in equal proportions (in other words,

in this case, we are achieving a total effective task utilization

, then using the speed ð - / m

before its deadline. If these 4 units of CPU time are used by

(recall that # $Xfg is the c Ted instance of task ), # M fM will

miss its deadline, if both #

and # M fM require their worst-case

, then

we should use the minimum CPU speed available, to stretch

out task executions as much as possible. In any case, using the

speed ð - / “ œ ç ^— Z - 9 $;:

). However, if m

workload.

As we can see, computing and managing earliness is not a

trivial task. Due to the periodic nature of the tasks we consider,

it is clearly impractical to a priori produce and keep the entire

static optimal schedule ß ü < :

will result in a total effective task

utilization which is no greater than 1. Hence, any scheduling

policy which can achieve up to 100% CPU utilization (Earliest

Deadline First, Least Laxity First) can be used to complete all

the task instances before their deadlines with the speed ð

during the execution. In order

to simultaneously address the problems of feasibility and ef-

ciency, while tasks execute, complete, re-arrive dynamically

and the actual schedule is produced, we choose to keep and up-

date a data structure (called -queue) that helps to compute the

. Œ

4 Dynamic Reclaiming Algorithm

The dynamic reclaiming algorithm is based on detecting

early completions and adjusting (reducing) the speed of other

tasks on-the-y in order to provide additional power savings

while still meeting the deadlines. To this aim, we perform com-

parisons between the actual execution history and the canon-

ical schedule ß ü < : , which is the static optimal schedule on

earliness of tasks when they are dispatched. At any time . dur-

ing actual execution, the -queue contains information about

tasks that would be active (i.e., running or ready) at time . in

the worst-case static optimal schedule ß ü < :

(in other words,

-queue is the ready queue of ß ü < :

at time . ). We assume that

the following information can be obtained for each task from

the -queue at any time . :

which every instance presents its worst-case workload to the

processor and runs at the constant speed ð

, the identity of the task (i.e., task number),

. The CPU speed

is adjusted only at task dispatch times: thus, we should be

able to say whether the task is being dispatched earlier than

, the arrival time of the instance (i.e., the period bound-

ary earlier than . ),

, and if so, determine the amount of additional CPU time

the dispatched task can safely use to slow down its execu-

tion; we will refer to this additional CPU time as the earli-

ness of the dispatched task. Before providing the details of our

approach, we underline that a simple approach that equates

earliness with previously unused CPU time and and blindly

slows down the processor is not a safe approach. To see

this, consider a 3-task system with the following parameters:

, the deadline of the instance (i.e., the period boundary

later than . ), and

, the remaining execution time of # $Xfg at time .

in ß ü < : , under the static optimal speed ð

Clearly, given . , the & $Xfg and ( $ fg values can be easily com-

puted for the periodic task model.

Note that the -queue at

time . contains information about all instances # $Xfg such that

. The

worst-case utilization of the task set is equal to 1.00, hence the

, and &o “æ $Xfg G;.PI v? . The -queue contains at

most ‘ elements, since the number of tasks in the ready queue

can never exceed the total number of tasks in any schedule.

Therefore, we will omit the instance number while referring to

Observation 1 stems from the following: (a) -queue is or-

dered according to EDF* order, (b) every arriving task pushes

its remaining worst-case execution time (under nominal speed)

into the -queue only once, (c) the queue is updated only at

-queue elements, whenever clarity is not compromised.

Our approach assumes that tasks are scheduled according

to EDF* policy. EDF* is the same as EDF (Earliest Deadline

First [12]), except that, among tasks whose deadlines are the

same, the task with the earliest arrival time has the highest pri-

ority (FIFO policy); in case that both deadline and arrival times

are equal, the task with the lowest index has the highest prior-

ity. This EDF* priority ordering is essential in our approach

because it provides a total order on the priorities. Further, we

assume that the -queue is also ordered according to EDF* pri-

the head, reecting the fact that only the task with the high-

est EDF* priority would be running in ß@ ü < : , and (d) a task

that would have nished in ß ü < :

is removed from the -queue.

This effectively yields a dynamic image of the ready queue in

at time . .

Note that the dynamic reduction of &o “æ $Xfg in R3 above does

not need to be performed at every clock cycle; instead, for

efciency, we perform the reduction whenever a task is pre-

empted or completes, by taking into account the time elapsed

since the last update. The above approach relies on two facts:

rst, the speed adjustment decision will be taken only at ar-

rival/preemption and completion times, and it is necessary to

have an accurate -queue only at these points (if speeds are to

orities. We denote the EDF* priority-level of the task by (

(low values denote high priorities).

At this point, we are ready to relate the -queue with the

computation of earliness factor. Let 3

denote the remain-

ing worst-case execution time of task # $ under the speed - at

time . . Further, set the nominal speed - $–/

for each task # $ .

Proposition 4 For any task #%= which is about to execute,

be changed at other points, the update of & o “ $ fg must reect

that). Second, between these points, each task is effectively

executed non-preemptively.

We are now ready to present our Generic Dynamic Reclaim-

ing Algorithm, GDRA, shown in Figure 2. Procedure Speed-

Reduce G;# = L

any unused computation time (slack) of any task in the -

queue having strictly higher priority than #%= will contribute

to the earliness of #%= along with already nished work of #%=

, in Figure 3, will be used by GDRA to re-

duce the speed - of # = , by allocating an extra

in the actual schedule.

That is, total earliness of #%= is no

units of time

to # = under worst-case remaining load, subject to - 9 $;: con-

less than = G;.PI /

straint. GDRA is “generic” in the sense that the amount of

additional time allocation in step 5.2 is not specied, it may

3 Ó

assume any value between 0 and = G;.PI without compromising

To understand the above result, note that when #%= is being dis-

the correctness.

The following theorem establishes that the schedules pro-

duced by GDRA are always ahead of ß ü < : .

patched, tasks with higher priority that are still in the -queue

must be already nished in the actual schedule (since # = cur-

rently has the highest EDF* priority), but they would have not

yet nished in ß ü < : .

Theorem 1 At any time . during the execution of GDRA,

Implementing the -queue: The -queue can be easily

, for any ready task # $ .

implemented using the following rules:

The formal proof of this theorem can be found in [3]. Focus-

ing exclusively on task completion times, the theorem implies

that in the actual schedule no task instance completes later than

its completion time in ß ü < :

R1. Initially the -queue is empty.

G;.PI 7 & o “ $ GV.PI

R2. Upon arrival, each task # g ”pushes” its worst-case execu-

(which is feasible), proving the

tion time under nominal speed -Eg /

to the -queue in

correctness of GDRA:

the correct EDF* priority position (this happens only once

for each arrival, no re-push at ’return from preemptions’).

Corollary 1 GDRA yields a feasible schedule under EDF*

priority for a workload no greater than the worst-case work-

load.

R3. As time elapses, the elements in the -queue are updated

(consumed) accordingly: the &N “Ý $Xfg eld at the head of -

Note that any specic algorithm should specify the exact

amount of earliness parameter , to use for speed reduction.

queue is decreased with a rate equal to that of the passage

of time. Whenever the &o “ $Xfg eld of the head reaches

One natural choice in Rule 5.2 of Figure 2 is to use / = G;.PI ,

zero, that element is removed from -queue and the up-

that is, to reduce the speed so as to prot from the full earliness.

We call this variation simply Dynamic Reclaiming Algorithm

(DRA).

date continues with the next element. No update is done

when the -queue is empty.

Observation 1 At time t, the -queue, updated according to

the rules R1, R2 and R3, contains only the tasks that would be

ready at time t in the static optimal schedule ß@ ü < : . Further, the

eld contains the remaining allotted time of each active

instance #%$Xfg at time t in ß ü < : .

%$– Ž J

As presented in [21], one can further slow down execution

when there is only one task in the ready queue and its worst

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: