Hard Real-Time Scheduling for Low-Energy Using Stochastic Data
Download
Report
Transcript Hard Real-Time Scheduling for Low-Energy Using Stochastic Data
Hard Real-Time Scheduling for LowEnergy Using Stochastic Data and DVS
Processors
Flavius Gruian
Department of Computer Science, Lund University
Box 118
S-221 00 Lund, Sweden
Tel.: +46 046 2224673
e-mail: [email protected]
Dynamic Voltage Scaling (DVS)
2
Pd Cef Vdd
f
P: dynamic power dissipation for CMOS
C: effective switched capacitance
V: voltage
f: frequency of the clock
Different Abstraction Level for Power
Saving
• Task set level
– Scheduling at inter-task level
• Task level
– Scheduling at intra task level. Insert rescheduling points inside a task
Different Abstraction Level for Power
Saving
• DVS for soft real-time systems
– Deadline misses are allowed
– QoS is kept
• DVS for hard real-time systems
– No deadline miss is allowed
Three execution mode for a task
Mode 1: ideal schedule ; Mode 2: WCET oriented schedule;
Mode 3: stochastic schedule
Obtaining Stochastic Schedule
• Obtained off-line
• Obtained by simulation
• Built and improved at runtime
Obtaining Stochastic Schedule
E
(1 cdf
0 y W X
y
) ey
E: average energy for the whole task
WX: worst case number of clock cycles of
a task
cdf : cumulative density of probability
function, cdfx=P(X<=x)
e: energy consumption for clock cycle y
Obtaining Stochastic Schedule
k
0 y W X
y
E
A,
k V
(1 cdf y )
0 y W X
(1 )
,
e V
2
k y2
Ky: the clock length associated to clock cycle y
A: the maximum execution time for a task to
complete
Goal of DVS: to minimize E
Obtaining Stochastic Schedule
by mathematical induction:
1
2
E 2 ( 1 cdf y )
A 0 y W X
when :
k y A ( 1 cdf y ) /(
0 y W X
1 cdf y )
Optimal Values -> Real Case Values
• Optimal clock length ky may not overlap
with the available clock lengths, need to be
converted to real clock cycles
• Find two bounding available clock cycles
CKi<Ky<=CKj
• Distribute the work of the ideal cycle into
two parts:
k y wi CKi (1 wi ) CK j
Off-line Task Stretching
• Computing stretching factors in an iterative
manner, from the higher to the lower priority
tasks ( priority computed by RMS)
• For the tasks which already have assigned a
stretching factor, we use that one r
• For the rest of the tasks, assume they will all
use the same and yet to be computed
stretching factor ij
S ij
S ij
r Cr ij C p Sij
1 r q
q p i
Tp
Tr
Off-line Task Stretching
On-line Slack Distribution
• An early finishing task may pass on its unused
processor time for any of the tasks executing
next
• Not all the slacks can be used by any task at any
time, because deadlines have to be met at the
same time
On-line Slack Distribution
• Multiple levels slacks
• If the tasks in the task set have m different
priorities, we use m levels of slacks
• The slack in each level is a cumulative value: the
sum of the unused processor times remaining
from the tasks with higher priority
Run-time Management of Slack
Level
• Whenever an instance k of a task Ti starts executing
(with priority i), it can use an arbitrary part Cik of the
slack available at level i, Si.
• Allowed executing time for Ti : Aik Ci Cik
• Remaining slack from level I will degrade into level
i+1 slack. Update each level slack with:
0, j i
Sj
k
S j Ci , j i
Run-time Management of Slack
Level
• Whenever a task instance finishes its execution, if it
finishes before its allowed time, it will generate some
k
k
k
slack: Ai Ai Ei
• This slack can be used by the lower priority tasks.
The level slacks are updated according to:
Sj
Sj, j i
k
S j Ai , j i
Slack Assignment
• Greedy: the task gets all the slack available for its
level
Cik S i
• Mean proportional: the task gets the slack according
to the proportion of their mean execution time i
C S i i /(
k
i
j )
jRe adyQ
Experimental Results ---Example 1
Experimental Results ---Example 2
Conclusions
• DVS policy for hard real-time systems
• Both off-line and on-line scheduling
decisions are taken
• Scheduling at both task level and task set
level
• Task splitting
• Multi-level slacks