Real-Time Task Scheduling for Energy-Aware Embedded Systems.pdf
(
68 KB
)
Pobierz
Real-Time Task Scheduling for Energy-Aware Embedded Systems
1
Vishnu Swaminathan and Krishnendu Chakrabarty
Dept. of Electrical & Computer Engineering
Duke University
Durham, NC 27708
vishnus,krish
g
@ee.duke.edu
ABSTRACT
We present a new approach for scheduling workloads
containing periodic tasks in real-time systems. The pro-
posed approach minimizes the total energy consumed by the
task set and guarantees that the deadline for every periodic
task is met. As embedded software becomes a larger compo-
nent of system-on-a-chip design, energy management using
the operating system becomes increasingly important. We
present a mixed-integer linear programming model for the
NP-complete scheduling problem and solve it for moderate-
sized problem instances using a public-domain solver. For
larger task sets, we present a novel low-energy earliest-
deadline-rst (LEDF) scheduling algorithm and apply it to
two real-life task sets.
rithms have also been provided [13]. Hong et al. presented a
heuristic for the preemptive model with a limit on the num-
ber of speed changes [4]. Although the scheduling meth-
ods cited above are very efcient, most of them make the
assumption that the CPU can operate at several different
voltage levels (and hence different clock frequencies) which
can be varied continuously. In addition, a number of these
methods are aimed at the synthesis of low-power designs
and they do not address energy minimization during eld
operation.
In this paper, we present an on-line scheduling algorithm
for real-time systems that attempts to minimize the energy
consumed by a periodic task set. This is based on the well-
known earliest-deadline-rst (EDF) algorithm [8]. We con-
sider a practical scenario where a single CPU executes a set
of periodic non-preemptable tasks. The voltage, and conse-
quently the clock speed, of the CPU may be switched be-
tween two or more values dynamically at run-time through
OS system calls. This option is available in most modern
computers, which provide at least two different operating
speeds [5]. We attempt to nd the voltage at which each
task must be executed such that the energy consumed by
the entire set of periodic tasks is minimized and generate a
schedule for the task set such that the release time require-
ments are satised and the deadlines for every task is met.
1
Introduction
A number of energy-constrained embedded and mobile
systems are designed for real-time use. These systems must
be designed to meet both functional
and
timing require-
ments [2]. Thus, the correct behavior of these systems de-
pends not only on the accuracy of computations but also on
their timeliness. While energy minimization for embedded
and mobile computing is of great importance, energy con-
sumption must be carefully balanced against the need for
real-time responsiveness.
One approach to conserve energy is to employ low-
power design methodologies. These methods, however, are
limited in that they can be used only in systems with a xed
supply voltage. Most modern computers are equipped with
a voltage supply that is capable of providing at least two
different voltages to the system, and the above methods are
comparatively less effective than ones that are tailored to
make use of this feature.
In embedded systems with variable-speed processors,
the operating system (OS) can reduce energy consumption
by scheduling tasks appropriately. Energy minimization by
adjusting CPU speed was rst studied in [12]. For real-
time systems, optimal preemptive off-line scheduling algo-
2
Preliminaries
In this section, we present our notation and the under-
lying assumptions. We are given a set of
n
periodic tasks
. Associated with each task
ri
2
R
are (i) its
release
(or arrival) time
ai
, (ii) its deadline
di
,
(iii) its length
l
i
(represented in number of instruction cy-
cles), and (iv) its period
pi
.
R
=
f
r
Each task is released at time
. In other words, each task can begin execution only
at or after time
t
=
ai
. Release times are arbitrary in that a
task may be released at any time before its deadline. We as-
sume, without loss of generality, that all tasks have identical
periods. If the periods of tasks are different, we can perform
a polynomial transformation to this scenario through the ap-
plication of the LCM theorem [7]. In such a case, there may
be a need to execute a given task several times within the
t
=
a
This research was supported in part by DARPA under grant no.
N66001-001-8946, and in part by a graduate fellowship from the North
Carolina Networking Initiative.
1
“hyperperiod”. All tasks must complete execution before
their deadlines.
We assume that the CPU can operate at one of two volt-
ages:
V
1
or
V
2
. Depending on the voltage level, the CPU
speed may take on two values:
s
1
or
s
2
.The model can be
easily extended to handle more than two voltages (speeds).
The supply voltage to the CPU is under OS control and
the OS may dynamically switch the voltage during run-
time with relatively low overhead. We restrict ourselves
to two speeds out of practical considerations. CPU speeds
are specied in terms of the number of instructions exe-
cuted per second. Each task
ri
may be executed at a volt-
age
v
i
,
v
i
2f
V
1
;V
2
g
, and correspondingly, at a speed
x
i
,
as a comparison tool for providing lower bounds on energy
consumption.
4
The LEDF heuristic
Although MILP is a useful and optimal solution method
for small problem instances, it cannot be used for large test
cases. In order to solve large problem instances, we have
developed a heuristic algorithm to generate near-optimal so-
lutions in polynomial time.
The
low-energy earliest deadline rst
heuristic, or sim-
ply LEDF, is an extension of the well-known earliest dead-
line rst (EDF) algorithm.
The operation of LEDF is as
follows:
LEDF maintains a list of all released tasks, called the
“ready list”. When tasks are released, the task with the near-
est deadline is chosen to be executed. A check is performed
to see if the task deadline can be met by executing it at the
lower voltage (speed). If the deadline can be met, LEDF
assigns the lower voltage to the task and the task begins ex-
ecution. During the task’s execution, other tasks may enter
the system. These tasks are assumed to be placed automat-
ically on the “ready list”. LEDF again selects the task with
the nearest deadline to be executed. As long as there are
tasks waiting to be executed, LEDF does not keep the pro-
cessor idle. This process is repeated until all the tasks have
been scheduled.
. Tasks are not preemptable, i.e., once a task
starts executing, no other task can execute until it completes
execution. There is also no
inserted idle time
. This means
that the scheduling algorithm does not allow the processor
to be idle if there is a task that has been released but has not
completed execution.
It is well-known that power consumption in CMOS cir-
cuits has a quadratic dependence on the CPU voltage.
Therefore, the energy
E
i
consumed by task
r
i
of length
l
i
is
Ei
/
v
i
2f
s
1
i
. Thus, energy consumption of task
ri
varies
quadratically with its assigned processor voltage
vi
and lin-
early with its length
l
i
.
The low-energy scheduling problem can be shown to be
NP-complete. Nevertheless, it can be solved exactly for
moderate-sized instances using mixed-integer linear pro-
gramming (MILP).
l
Figure 1 gives the algorithm in pseudo-
code form.
Procedure
LEDF()
begin
Repeat forever
3 Mixed-integer linear programming model
The optimization problem we address is to minimize the
total energy consumed by the set of
n
tasks by optimally de-
termining their start times
t
1
;t
2
;:::;tn
, their voltages and
corresponding execution speeds.
The following constraints need to be modeled: (i) CPU
speeds are limited to one of two values—
s
1
or
s
2
, (ii) The
deadline for each task must be met, (iii) Tasks are non-
preemptable, and (iv) A task may start only after it has been
released.
We observed in Section 2 that the energy consumed by
task
ri
is proportional to
v
i
li
.
Hence, the objective function is
Minimize
f
Are tasks waiting to be scheduled in ready list?
yes
Sort deadlines in ascending order
Schedule task with earliest deadline
Check if deadline can be met at lower speed (voltage)
If deadline can be met, schedule task to execute at lower voltage (speed)
If deadline cannot be met, check if deadline can be met at higher speed (voltage)
If deadline can be met, schedule task to execute at higher voltage (speed)
If deadline cannot be met, task cannot be scheduled. Call exception handler!
no
do-nothing
g
end
.
The modeling of the constraints and their subsequent lin-
earization are omitted here due to space limitations.
The MILP model is too computationally-intensive to be
used for large task sets. However, it is helpful in providing a
lower bound on the amount of energy consumed by a given
task set. In our MILP formulation, a priori knowledge of
the release times has been inherently assumed. We observe
that energy can be minimized to a greater extent in the off-
line case than in the on-line one. This justies use of MILP
Figure 1. The LEDF algorithm
Our
algorithm
has
a
computational
complexity
of
. The worst-case scenario occurs when all
n
tasks are released at time
t
= 0
. This involves sorting
n
tasks in the ready list and then selecting the task with the
earliest deadline for execution. Given that all
n
tasks have
already arrived and that they are already sorted by dead-
line, we no longer need to perform sorting on the task set.
O
(
n
log
n
)
1.7
x
10
5
Task
Release
a
i
Deadline
d
i
Length
l
i
(x
10
6
)
(x
10
6
)
(x
10
6
)
=
300
=
400
3
7
800
2.66
2.0
1.6
9
21
750
2.5
1.875
LEDF
MILP
0
5
1600
5.33
4.0
18
25
1000
3.33
2.5
1.5
14
16
600
2.0
1.5
7
10
1200
4.0
3.0
20
27
1100
3.66
2.75
1.4
14
20
1600
5.33
4.0
11
14
500
5.0
3.75
30
35
1400
4.66
3.5
1.3
27.5
30
800
2.66
2.0
40
42
600
2.0
1.5
1.2
34
39
1600
5.33
4.0
40
46
1200
4.0
3.0
44
50
1400
4.66
3.5
1.1
44
55
2000
6.66
5.0
13
14
15
16
17
Number of tasks
40
43
300
1.0
0.75
Figure 4. Comparison of schedules generated by
MILP and LEDF.
Table 1. A simple task set consisting of 17 tasks.
Scheduling a task for execution has
O
(1)
complexity. This
results in a worst-case execution time of
O
(
n
log
n
)
.
We now present our experimental results. First we show
the results of the MILP simulations and LEDF for a task set
of seventeen tasks.
Our example task set is given in Table 1. It consists of
seventeen tasks
r
1
to
r
17
. Each task has a release time, a
deadline and length. We assume the two processor speeds
to be 300 million instructions per second (MIPS) at 2.47 V
and 400 MIPS at 3.3 V.
same task set. The energy consumed by this schedule is
169709.75 units. We observe that the energy consumed here
is marginally greater than that for the MILP schedule. Nev-
ertheless, our results show that our algorithm can generate
near-optimal schedules with an energy increase of around
.
We observe that the order in which tasks are executed re-
mains the same in both the MILP and LEDF schedules. The
increased energy consumption of LEDF arises due to the
fact that LEDF does not possess knowledge of the release
times a priori. Our MILP model, which does not have such
a restriction, executes tasks
r
12
and
r
17
at a higher speed
(voltage) even though both could have met their respec-
tive deadlines by executing at a lower speed (voltage). We
showed in Section 2 that energy consumed by a task is pro-
portional to its length. Since the length of task
r
15
is greater
than the lengths of both
r
12
and
r
17
, we see that by execut-
ing
r
12
and
r
17
at a higher speed (voltage), we can execute
r3 r1 r6 r2 r9 r5 r8 r4 r7 r11 r10 r13 r12r17 r14 r15 r16
0 10 20 30 40 50 55
Task at 3.3 V ( 400 MIPS )
Energy consumption: 167327 units
Task at 2.47 V ( 300 MIPS )
Figure 2. Schedule generated using MILP
r3 r1 r6 r2 r9 r5 r8 r4 r7 r11 r10 r13 r12r17 r14 r15 r16
15
at a
lower
speed (voltage) and thus reduce the effect of
the length of
r
15
on energy. This, in fact, does result in an
optimal schedule. This characteristic of the task set cannot
be utilized by LEDF, or any other on-line scheduling al-
gorithm, because no scheduling algorithm has prior knowl-
edge of release times. In order to evaluate the effective-
ness of LEDF, we generated energy-optimal schedules us-
ing MILP and the corresponding schedules using LEDF for
task sets containing upto seventeen tasks. The results, plot-
ted in Figure 4, show that LEDF produces optimal sched-
ules for upto fourteen tasks. Beyond that, it slowly starts to
diverge from the optimal schedule.
We also applied the LEDF algorithm to a real-time task
0 10 20 30 40 50 55
Task at 3.3 V ( 400 MIPS )
Energy consumption: 169709.75 units
Task at 2.47 V ( 300 MIPS )
Figure 3. Schedule generated using LEDF
The execution times for the tasks at the two different
speeds are also shown. Figure 2 shows the schedule gen-
erated using MILP. The energy consumed by the schedule
generated through MILP is 167327 units (measured by the
sum of the
v
i
li
values).
Figure 3 shows the corresponding LEDF schedule for the
set consisting of twenty-four tasks. This task set was used
for the development of an application-specic integrated
circuit for an avionics application [10]. The processor
speeds were assumed to be 100 MIPS and 260 MIPS, with
corresponding voltages 1.2 V and 3.3 V respectively. The
energy consumed by this task set was 203803.55 units. If
all tasks are scheduled at the higher speed, the energy con-
sumed is as high as 360938 units, i.e.
77%
higher. On the
other hand, if only the lower speed is used, as many as seven
tasks miss their deadlines.
Finally, we applied LEDF to a 39-task example. This
task set comes from an embedded signal processing appli-
cation for an anti-submarine warfare (ASW) system [1].
The task set runs on a Mercury PowerPC 6U VME board
with a 200 MHz 603e processor. We have assumed that
the processor is capable of operating at 100 MHz and that
the processor speeds are dynamically switchable. We have
also assumed that the CPU operates at 200 MHz at 3.3 V
and at 100 MHz at 1.65 V. Furthermore, in order to em-
phasize energy minimization, the deadlines we have used
are tighter than the actual deadlines for the actual task set.
For this example, LEDF generated a schedule that con-
sumed 323680.78 units of energy. For this task set, if only
the higher speed (voltage) is used, the energy consumed is
477482 units, i.e,
47
:
5%
higher. However, if only the lower
speed is used, seventeen tasks miss their deadlines.
The MILP model took prohibitively large amounts of
time for scheduling task sets consisting of more than sev-
enteen tasks running on a dual-processor Sun Ultra-1 with
a 256 MB memory capacity. For an eighteen task data set,
MILP took over a day to generate the optimal solution. On
the other hand, LEDF took under a second to generate a
near-optimal solution for the thirty-nine task example.
[6] K. Jeffay, D. F. Stanat and C. U. Martel, “On non-
preemptive scheduling of periodic and sporadic tasks
with varying execution priority,”
Proc. IEEE Real-
Time Systems Symposium,
pp.
129–139, December
1991.
[7] E. L. Lawler and C. U. Martel, “Scheduling period-
ically occurring tasks on multiple processors”,
Infor-
mation Processing Letters,
vol. 12, no. 1, pp.
9–12,
1981.
[8] C. L. Liu and J. Layland, “Scheduling algorithms for
multiprogramming in a hard real-time environment”,
Journal of the ACM,
vol. 20, pp. 46–61, 1973.
[9] J. R. Lorch and A. J. Smith, “Scheduling techniques
for reducing processor energy use in MacOS”,
Wire-
less Networks,
, vol. 3, pp. 311–324, 1997.
[10] J. H. Wensley, K. N. Levitt, M. W. Green, J. Goldberg
and P. G. Neumann, “ Design of a fault tolerant air-
borne digital computer. Volume 1: Architecture,” Fi-
nal Report, Stanford Research Institute, Menlo Park,
CA, October 1973.
[11] J. M. Rabaey and M. Pedram,
Low Power Design
Methodologies,
Kluwer Academic Publishers, Nor-
well, MA, 1996.
[12] M. Weiser, B. Welch, A. Demers and S. Shenker,
“Scheduling for reduced CPU energy,”
Proc. Sympo-
sium on Operating System Design and Implementa-
tion,
pp. 13–23, 1994.
[13] F. Yao, A. Demers and S. Shenker, “A scheduling
model for reduced CPU energy”,
Proc. IEEE An-
nual Foundations of Computer Science,
pp. 374–382,
1995.
References
[1] J. Anderson, private communication, March 2000.
[2] G. C. Buttazzo,
Hard Real-time Computing Systems:
Predictable Scheduling Algorithms and Applications,
Kluwer Academic Publishers, Norwell, MA, 1997.
[3] M. R. Garey and D. S. Johnson,
Computers and
Intractability:
A
Guide
to
the
Theory
of
NP-
Completeness,
Freeman and Co.,
New York, NY,
1979.
[4] I. Hong, G. Qu, M. Potkonjak, and M. B. Srivastava,
“Synthesis techniques for low-power hard real-time
systems on variable-voltage processors”,
Proc. Real-
time Systems Symposium,
pp. 178–187, 1998.
[5]
Intel Pentium III Processor Brief,
http://www.intel.com
Plik z chomika:
atari666
Inne pliki z tego folderu:
Analysis of the PASR Standard and its usability in Handheld Operating Systems such as Linux.pdf
(84 KB)
Compiler-controlled and Compiler-hinted Voltage Scaling Approaches.pdf
(144 KB)
Dynamic and Aggressive Scheduling Techniques for Power Aware RTS.pdf
(181 KB)
CRC.Press.The.Compiler.Design.Handbook.2nd.Edition.Dec.2007.pdr
(0 KB)
Evaluation and Modeling of Power Consumption of a Heterogeneous Dual-Core Processor.pdf
(1804 KB)
Inne foldery tego chomika:
Zgłoś jeśli
naruszono regulamin