Transcript Enhancing Performance and Fault Tolerance in Reward

Determining Optimal Processor Speeds
for Periodic Real-Time Tasks with
Different Power Characteristics
H. Aydın, R. Melhem, D. Mossé, P.M. Alvarez
University of Pittsburgh
ECRTS’2001
Motivation
• Power Management: Crucial for devices with
scarce power resources (Mobile, embedded..)
• Variable Voltage Scheduling: Adjust the supply
voltage and the frequency (hence, the speed) of
the CPU on-the-fly to obtain power savings.
Variable Voltage Scheduling
• The speed / power function is a strictly convex function:
Prospects of saving energy at the expense of increased latency.
• Example: Assume that power consumption, P, is
proportional to the square of the execution speed, S.
t
S
Execution
time
1
power
2
3
4
5
16
7
4
2.5
64
energy
consumed
64
32
21
16
12.5
Product of CPU speed, S , and allocated time, t = # of cycles, C.
RT Variable Voltage Scheduling
Clock rate
Given
• a deadline
• a worst case workload
• a capability to adjust the processor speed
Power, P
and
Energy, E
Start time
P(S)
Exec. at
max speed
E(S)
Smin
Speed
Smax
We can find the speed to
• meet the deadline, and
• minimize energy consumption
Exec. at
opt. speed
time
Exec. at
min speed
deadline
Variable Voltage Scheduling versus
Reward-Based Scheduling
t_min
Reward
Reward increases beyond
t_min in a convex manner.
Additional
CPU time ti
t_max
• Find CPU allocations per task to maximize total reward
while meeting the deadlines.
Variable Voltage Scheduling versus
Reward-Based Scheduling
t_min
Energy consumption
Max CPU Speed
Additional
CPU time ti
t_max
Min CPU Speed
• Energy savings are increasing beyond t_min in a concave manner.
• Find optimal CPU allocations per task to maximize the energy savings
while meeting the deadlines.
• Note that, for a fixed computation (# of cycles, C), more time, t, means
smaller speed, S.
When all tasks consume the same power, total energy is minimized
if all tasks run at the same speed (allocated same CPU time)
Example: Three tasks with C1 = C2 = C3
Pi(S) = a S2 , for task i ,
energy consumed by task i is Ei = a / ti .
E
P(S)
E(S)
Smin
Smax
Start time
t1
Task
1
t2
Task
2
time t3
Task
3
S
D/3
t1 = t2 = t3 minimizes total energy
deadline
D
Task-level Power Characteristics
• At a given voltage/speed level, the power consumption is
proportional to the effective switched capacitance of the
running task.
• The power - speed function is highly dependent on:
– Locality of reference exhibited by the task
– On-chip units actively being used (FPU, DSP, …)
– Effects of other power management techniques
• To obtain full benefit through Variable Voltage Scheduling,
different power/speed curves for different tasks should be
considered.
When tasks consume different powers, total energy is not minimized
if all tasks run at the same speed (allocated same CPU time)
Example: Three tasks with C1 = C2 = C3
E
Pi(S) = ai S2 , for task i ,
energy consumed by task i is Ei = ai / ti . t1
Start time
t2
D
D/3
time
t1 = t2 = t3 does not minimize total energy
t3
deadline
Minimizing energy consumption
The problem is to find Si , i=1, … , n, such that to
Start time
n
minimize

ti
i 1
n
subject to
t
i 1
and
Note that ti

S min
i
Pi ( Si )
 D
 Si
 S max
D
Ci
Si
• We solved this optimization problem, consequently developing
a solution for arbitrary convex power functions.
• Algorithm complexity: O(n2 log n)
deadline
PERIODIC VARIABLE VOLTAGE SCHEDULING
MODEL
• A set of n periodic tasks
• Task i has:
– the period Ti
– the worst-case number of instruction cycles, Ci
– the power consumption function Pi(S), where S is the
processor speed (0 <= Smin <= S <= Smax= 1)
PROBLEM:
Determine the schedule and speed assignments for every
instance of each task during hyperperiod T (least common
multiple of all the periods), so as to:
– Minimize the total energy consumed by the system
– Meet all the deadlines.
Optimal Speed Assignments
• Power consumption curve is convex:
– No need to change speed during the lifetime an instance
– No need to change speed at different instances of a task
• Identical power consumption functions 
Use the uniform speed S = Utilization =  Ci / Ti
• Non-identical power functions lead to different optimal
speed assignments for different tasks!
– High-power tasks should be executed with lower speeds
Optimal Speed Assignments
n
minimize

i 1
n
T
Pi ( Si )
Ti
T Ci
subject to 
T
i 1 Ti Si
and
S min  Si  S max
• Convex minimization
problem
• Solution sketch:
– Consider only equality
constraint: Problem OPT
– Consider only equality and
lower bound constraints:
Problem OPT-L
– Adjust solutions using
properties derived from
Kuhn-Tucker conditions
– O(n2 log n) solution exists
Scheduling with Optimal Speeds
• Theorem: Any hard real-time scheduling policy which can
fully utilize the processor can be used to obtain a feasible
schedule with the optimal speed assignments.
– Earliest Deadline First
– Least Laxity First
– Rate Monotonic with Harmonic Periods
• Implementation: The optimal speed Si becomes part of the
process state / descriptor. CPU speed is dynamically modified
at context-switch time (overhead of changing speed: 100 - 1000
clock cycles)
Experimental results
• Evaluated experimentally the improvement over the uniform slow down
of all the tasks (the optimal scheme for identical power functions).
• Assumed that Pi(Si) = i Si3
• Considered k = (max / min)
% energy improvement
35
Bimodal distribution
30
25
20
15
Uniform distribution
10
5
0
1
2
3
4
5
6 7
8
k
Conclusion
• To obtain the full benefit of Variable Voltage Scheduling,
the power characteristics must be considered at the tasklevel.
• Optimal speed assignments can be computed efficiently
for the periodic model.
• Earliest Deadline First policy can be used to produce a
feasible schedule.
Future Work
• Consider variations in the actual workload.
• Develop dynamic reclaiming techniques while still
guaranteeing the feasibility.
• Address the precision (reward) and the energy issues
simultaneously.