Transcript At a PMP

Power Aware
Real-time Systems
A joint project with profs
Rami Melhem
Bruce Childers
Ahmed Amer
Trying to rope in
everyone else
And students
Nevine Abougazaleh
Cosmin Rusu
Dakai Zhu
Sameh Gobriel
Matt Craven
Ruibin Xu
Outline

Introduction to real-time systems

Introduction to power management

Speed adjustment in frame-based systems

Dynamic speed adjustment in multiprocessor environment

Tradeoff between energy consumption and reliability

Saving power in wireless networks
Real-time systems
Hard RT systems
Periodic
preemptive
non
preemptive
uni-processor
Soft RT systems
Aperiodic
(frame-based)
preemptive
non
preemptive
parallel processors
REAL-TIME SYSTEMS
Hard Real Time system
guarantee deadlines
• To guarantee deadlines, we need to know worst case execution times
• Predictability: need to know if deadlines may be missed
Soft Real Time system
try to meet deadlines
• If a deadline is missed, there is a penalty
• Provides statistical guarantees (probabilistic analysis)
• Need to know the statistical distribution of execution times
Applications:
Safety critical systems, control and command systems, robotics,
Communication, multimedia
Periodic, EDF scheduling
• n tasks with maximum computation times Ci and
periods Ti, for i=1,…,n.
C=2, T=4
C=3, T=7
• Dynamic priority scheduling (high priority to the task with
earlier deadline)
• All tasks will meet their deadlines if utilization is not more
than 1.
• Task set utilization is percentage of CPU used by all tasks:
• This example: 24 + 37
Outline

Introduction to real-time systems

Introduction to power management

Speed adjustment in frame-based systems

Dynamic speed adjustment in multiprocessor environment

Tradeoff between energy consumption and reliability

Saving power in wireless networks
Power Management

Why & What: Power Management?




Battery operated: Laptop, PDA and Cell phone
Heating : complex Servers (multiprocessors)
Power Aware: maintain QoS, reduce energy
How?


Power off un-used parts: LCD, disk for Laptop
Gracefully reduce the performance

CPU: dynamic power Pd = Cef*Vdd2*f [Chandrakasan-1992, Burd-1995]
 Cef : switch capacitance
 Vdd : supply voltage
 f : processor frequency  linear related to Vdd
Power Aware Scheduling

Static Power Management
(SPM)

Static slack: uniformly slow all
tasks [Weiser-1994, Yao-1995,
fmax
Static Slack
T1
T2
idle
E
time
Gruian-2000]
T2
T1
Energy
D
T1
0.6E
time
0.6E
T2
time
fmax/2
T1
T2
f
T1
T2
E/4
time
Power Management

Dynamic Power Management
(DPM)


Dynamic slack: non-worst execution
10% [Ernst-1997]
DPM: [Krishna-2000, Kumar-2000,
Pillai-2001, Shin-2001]
fmax
Static Slack
T1
T2
idle
D
E
time
fmax/2
T1
T2
E/4
time
fmax/2 Dynamic Slack

Multi-Processor


T1
SPM: length of schedule over
deadline
DPM ???
time
fmax/3
T1
T2
0.12E
time
Outline

Introduction to real-time systems

Introduction to power management

Speed adjustment in frame-based systems

Dynamic speed adjustment in multiprocessor environment

Tradeoff between energy consumption and reliability

Saving power in wireless networks
Speed adjustment in frame-based systems
Static speed adjustment
Assumption: all tasks have the same deadline.
CPU speed
WCET
deadline
Smax
Smin
time
Smax
Smin
time
Select the speed based on worst-case execution time,WCET,
and deadline
Dynamic Speed adjustment techniques
for linear code
WCET
time
ACET
time
Speed adjustment based on remaining WCET
Note: a task very rarely consumes its estimated worst case execution time.
Dynamic Speed adjustment techniques
for linear code
Remaining WCET
time
Remaining time
time
Speed adjustment based on remaining WCET
Dynamic Speed adjustment techniques
for linear code
Remaining WCET
time
Remaining time
time
Speed adjustment based on remaining WCET
Dynamic Speed adjustment techniques
for linear code
time
time
Speed adjustment based on remaining WCET
Dynamic Speed adjustment techniques
for linear code
time
time
Speed adjustment based on remaining WCET
time
Greedy speed adjustment:
Give reclaimed slack to next task rather than all future tasks
Dynamic Speed adjustment techniques
for linear code
WCET
WCE
ACET
Smax
WCE
WCE
time
Remaining time
Remaining av. ex. time
AV
AV
time
Smax
WCE
WCE
Speed adjustment based on
remaining average execution time
time
An alternate point of view
WCET
WCE
WCE
WCE
time
ACET
WCE
Reclaimed
slack
WCE
AV
time
stolen
slack
WCE
time
Dynamic Speed adjustment techniques
for non-linear code
p1
p2
p3
min
average
At a
• Remaining WCET is based on the longest path
• Remaining average case execution time is based on
the branching probabilities (from trace information).
max
correct
Greedy dynamic speed adjustment
 Giving reclaimed slack to the next ready task is not always a
correct scheme
 Theorem: A reclaimed slack has to be associated with a deadline
and can be given safely to a task with an earlier or equal deadline.
aggressive dynamic speed adjustment
 Theorem: if tasks 1, …, k are ready and will complete before the
next task arrival, then we can swap the time allocation of the k
tasks. That is we can add stolen slack to the reclaimed slack
 Experimental rule: Do not be very aggressive and reduce the
speed of a task below a certain speed (the optimal speed
determined by Uav )
Outline

Introduction to real-time systems

Introduction to power management

Speed adjustment in frame-based systems

Dynamic speed adjustment in multiprocessor environment

Tradeoff between energy consumption and reliability

Saving power in wireless networks
Multiprocs and AND/OR Applications

(1,2/3)
Real-Time Application
Set of tasks
 Single Deadline

Directed Acyclic Graph
(DAG)



Ti
Comp. (ci, ai)
AND (0,0)
OR (0,0): probabilities
40%
60%
(2,1)

T1
(1,1)
T2
(4,2)
T3
(3,2)
T4
T5
(1,1)
T6
(1,1)
T7
The Example
Slack Stealing

Shifting Static Schedule: 2-proc, D = 8
f
T3
T2
T1
D
L1
T6
L0
T7
T5
`
T4
0
1
2
3
4
5
6
7
8
time
Shifting Recursive if embedded OR nodes
f
L1
L0
D
T3
T2
T1
T6
T7
T5
T4
0
1
2
3
4
5
6
7
8
time
Proposed Algorithms
 Greedy
algorithm, two phases:
Off-line:
longest task first heuristic; Slack
stealing via shifting: LSTi , EOi
On-line:
 Same
execution order
 Claim the slack: LSTi – ti (tiLSTi)
 Compute speed:
ci
f gi  f max 
ci  Slack i
 Meet
timing requirement [Zhu-2001]
Proposed Algorithms (cont)
Actual Running Trace: left branch, Ti use ai

L1
D
f
T3
L0

1
2
3
4
5
6
Possible Shortcomings
 Number
T7
T2
T1
0
T6
of Speed change (overhead)
 Too greedy: slow  fast
7
8
time
Proposed Algorithms (cont)

Optimal for uniprocessor: Single speed



Energy – Speed: Concave
Minimal Energy when all tasks SAME speed
Speculation: statistical information about
Application
all
w
average
 Static Speculation
f ss 
 All tasks
D
i
i

f = max ( fss, fg )
 Adaptive


Speculation
Remaining tasks
fi = max ( fas, fgi)
f as 
remaining
waverage
timer
References











[Chandrakasan-1992] A. P. Chandrakasan and S. Sheng and R. W. Brodersen. Low-Power CMOS Digital
Design. IEEE Journal of Solidstate Circuit, V27, N4, April 1992, pp 473--484
[Burd-1995] T. D. Burd and R. W. Brodersen. Energy efficient cmos microprocessor design. In Proc. of The
HICSS Conference, pages 288-297, Maui, Hawaii, Jan. 1995.
[Weiser-1994] M. Weiser, B. Welch, A. J. Demers, and S. Shenker. Scheduling for reduced CPU energy. In
Operating Systems Design and Implementation, pages 13-23, 1994
[Yao-1995] F. Yao, A. Demers, and S. Shenker. A scheduling model for reduced cpu energy. In Proc. of The 36th
Annual Symposium on Foundations of Computer Science, pages 374-382, Milwaukee, WI, Oct. 1995.
[Gruian-2000] F. Gruian. System-Level Design Methods for Low-Energy Architectures Containing Variable
Voltage Processors. The Power-Aware Computing Systems 2000 Workshop at ASPLOS 2000, Cambridge, MA,
November 2000
[Ernst-1997] R. Ernst and W. Ye. Embedded program timing analysis based on path clustering and architecture
classification. In Proc. of The International Conference on Computer-Aided Design, pages 598–604, San Jose,
CA, Nov. 1997.
[Krishna-2000] C. M. Krishna and Y. H. Lee. Voltage clock scaling adaptive scheduling techniques for low
power in hard real-time systems. In Proc. of The 6th IEEE Real-Time Technology and Applications Symposium
(RTAS00), Washington D.C., May. 2000.
[Kumar-2000] P. Kumar and M. Srivastava, Predictive Strategies for Low-Power RTOS Scheduling,
Proceedings of the 2000 IEEE International Conference on Computer Design: VLSI in Computers and
Processors
[Pillai-2001] P. Pillai and K. G. Shin. Real-Time Dynamic Voltage Scaling for Low-Power Embedded Operating
Systems, 18th ACM Symposium on Operating Systems Principles (SOSP?1), Banff, Canada, Oct. 2001
[Shin-2001] D. Shin, J. Kim and S. Lee, Intra-Task Voltage Scheduling for Low-Energy Hard Real-Time
Applications, IEEE Design and Test of Computers, March 2001
[Zhu-2001] D. Zhu, R. Melhem, and B. Childers. Scheduling with Dynamic Voltage/Speed Adjustment Using
Slack Reclamation in Multi-Processor RealTime Systems, RTSS'01 (Real-Time Systems Symposium), London,
England, Dec 2001 152