Transcript PinWheel Scheduling for Power Aware Real Time Systems

Pinwheel Scheduling for
Power-Aware Real-Time
Systems
Gaurav Chitroda
Komal Kasat
Nalini Kumar
OUTLINE
•Motivation
•Introduction
•Pinwheel Transformation
•Methods of Power Reduction
•Simulations and Results
•Conclusion
Motivation






Energy consumption is critical
Demand on performance and computation
constantly increase energy consumption
Maintaining high performance along with
increased battery life is a challenge
Using DVS and DFS to reduce Power
Consumption
Online vs Offline Scheduling
Power-Aware Real -Time Scheduling
3
OUTLINE
•Motivation
•Introduction
•Pinwheel Transformation
•Methods of Power Reduction
•Simulations and Results
•Conclusion
Introduction
Deadlines for tasks and Slack Time
 Dynamic Voltage Scaling(DVS)
 Dynamic Frequency Scaling(DFS)
 Distance Constrained Task Systems(DCTS)
 Rate Monotonic Scheduling(RM)
 Pinwheel Algorithm
 Benefits

5
Slack Time

Slack time of a job with deadline di at any time t such that t < di is (di –t)
deadline job1: d1
deadline job 2 : d2
Scheduling interval at time t0
Scheduling interval at time d1
Job 1
Job 2
Job 3
Job 4
Slack time (job1)
Slack time (job 2)
6
DVS & DFS

Powerdynamic = CL * NSW * V2dd * f
CL: Load Capacitance
Vdd: supply voltage
NSW: avg no of ckt switches per clock cycle
f: clock frequency
These techniques are applied meeting real time constraints
f
r
e
q
u
e
n
c
y
0
T1
T2
T3
T4
T1
T2
T3
T3
T4
T1
t1
t2
t3
t4
t5
T5
T5
T4
t6
time
7
DCTS - Distance Constrained Task System


Distance between 2 consecutive execution of a task
should be less than a predefined value
Example:
Period Pi
Period Pi
J ij
J ij+1
J ij+2
time
2Pi – ei

ei
The distance of two consecutive jobs can be as large as
2Pi-ei or as small as ei
8
Rate Monotonic Scheduling
Tasks are assigned Priority based on their Periods.
 Task with lowest period is assigned highest priority.


Consider a system with Five Tasks with Distance Constraints
{9.2,10.6,10.7,21.4,23.4} respectively and their execution times are
{1.5,2.0,3.4,1.4, 3.0}
T1
T2
T3
T4
T5
9
OUTLINE
•Motivation
•Introduction
•Pinwheel Transformation
•Methods of Power Reduction
•Simulations and Results
•Conclusion
Pinwheel Transformation
Distance-constrained specialization Technique to
transform all task distance constraints to Harmonic
numbers.
 Tasks can be scheduled as periodic tasks using the new
distance constraint as their periods.
 As the distance constraints are Harmonic numbers, the
execution schedule has no jitter and meets the distance
constraints.
 The system predictability is increased and thus
complexity of Power-Aware Real-time Scheduling can
be reduced.

11
Rate Monotonic Scheduling without Pinwheel. Periods are {9.2, 10.6, 10.7, 21.4, 23.4}
T1
T2’s period started, but T1 yet not
finished so T2 is delayed.
T2
Start of T1’s period, so T5 halted
T3
T4
T5
After Pinwheel Scheduling. The Periods are {5.3, 10.6, 10.6, 21.2, 21.2}
T1
Start of T1’s period. So T3 is halted
T2
Start of T1’s period. So T3 is halted
Start of T1’s period, so T5 halted
T3
T4
T5
0
5.3
10.6
15.9
12
Power-Aware Algorithm Using
Pinwheel model

Offline Scheduling- Apriori knowledge of realtime jobs
including periods,execution times,release times,etc.


Online Vs Offline Scheduling
Benefits obtained from Pinwheel model Tasks information can be known apriori
 Pinwheel schedule can be generated in Polynomial time and
space
 The rescheduling points within the hyperperiod can be
massively reduced.
13
Pinwheel Transformation Process
Power- Aware real-time Scheduling using Pinwheel
model can be divided into two phases1) Generate and store Pinwheel schedules. All task
periods are transformed to harmonic integers.
2) Second Phase- Schedulers perform more precise
power-aware scheduling according to their policies
based on timing information obtained from the
pinwheel schedule. Then DVS and DFS is dynamically
performed at every rescheduling point to reduce
energy consumption.

14
OUTLINE
•Motivation
•Introduction
•Pinwheel Transformation
•Methods of Power Reduction
•Simulations and Results
•Conclusion
Methods of Power Reduction
Key Idea- To manage slack times in order to reduce
energy dissipation.
Under the restriction that no task misses its deadline1) We can lower the processor voltage and frequency to
reduce energy consumption.
2) We can use a simple Heuristic to know slack times in
advance. This only partially solves the problem.
Three methods used in the paper1) Low Power Fixed Priority Scheduling(LPFPS)
2) Greedy Method
3) Linear Programming(LP method)
16
Low Power Fixed Priority Scheduling
Schedules using RM when there is not
more than one task in the ready queue.
 DVS and DFS are then applied if possible
 When there are no tasks in the ready
queue, the system enters Sleep mode

17
frequency
Example:
T1
Slack Time
T2
T3
T4
T5
time
frequency
RM Scheduling
T1
T2
T2
T3
T4
LPFPS using pinwheel
T5
T5
time
T1 and T3 finish earlier then their WCETs, but only T2 and T 5 execute
using lower processor frequency to make use of the slack times.
T4 executes using the maximum frequency because it is not the only
one task left in the ready queue.
18
Greedy Method
LPFPS extended to perform DVS & DFS at
every rescheduling point
 Next ready job greedily uses up idle time
within its scheduling interval
 Processor frequency is lowered as much as
possible
 Reschedules at every rescheduling point to
determine processor voltage and frequency
 Some slack time may be wasted as
remainder not sufficient for adjustments

19
Greedy Method
frequency
Example:
T1
T2
T3
time
frequency
Pinwheel
T1
T1
Greedy Method
T2
T3
Slack time wasted
time
The first ready task gets scheduled to maximize slack time utilization
20
LP Method
We want to minimize the slack time
 Processor frequencies are not continuous
 Problem mapped to Integer Linear

Programming - ILP problem – NP Complete
 Heuristic used is Linear Programming – LP
 LP is applied at every scheduling interval to utilize
maximum slack time
21
LP Method
C

ij
q
m *C
i
q
i
for I = 1,2,…..m
For n jobs, with scheduling interval T
q: frequency [q1: minimum & qm: maximum]
C: execution times
[C1 to Cn ]
• Determine processor frequency of each job in the
scheduling interval
Xi 
qm
qi
•
Ratio of lengthened task execution time when processor
frequency reduced from qm to qi is given as X:
n
C
i 1
i
*X i
•Find n real numbers X1, X2…… Xn such that the summation is
maximum
22
LP Method - Constraints
(1)
Xi  1
for i =1,2,….n
(2)
qm
Xi 
q1
for i =1,2,….n
(3)
C i*X i  D i  t i
for i =1,2,….n
n
(4)
C * X
i 1
i
i
T
for i =1,2,….n
•LP Method uses all slack times for energy saving
•Obtains more energy reduction than Greedy Method
23
Adaptive WCET to AET
Optimized energy consumption not
obtained using WCET
 Use a profiling tool

 insert codes which issue rescheduling system call to
update WCET
 AET can be obtained from the updated WCET
 Further energy saving for applications which do not
use their WCET
 This approach maximizes system energy reduction
24
Issue with Pinwheel Model





New periods may be shorter than the original
periods
Job execution too frequent leading to change in
behavior of the task
Some applications cannot accept this
Example: Video system
A frame may be repeated every 22ms instead
of 33ms resulting in fast forward effect
Solution: Make task idle and use this as slack
time for energy saving
25
26
OUTLINE
•Motivation
•Introduction
•Pinwheel Transformation
•Methods of Power Reduction
•Simulations and Results
•Conclusion
Simulation Results
Transmeta
processors –
TM55EL-667 and
TM58EX-933 for
practical results
 System utilization of
10% to 70%
 140000 test sets
 Each test set has 2 to
8 real-time tasks

28
RESULTS
RM scheduling
energy consumption
is taken as the base
 As system utilization
increases, system
slack time decreases
 As load increases, it
becomes difficult to
obtain energy
savings

29
RESULTS
LP methods give better energy savings
than greedy methods
 Average reduction of 37% to 56% at 70%
utilization
 More reduction on TM58EL-933 than on
TM58EX-667

 More frequency steps available to adjust CPU
frequencies.
30
Scheduling Overheads


RM, LPFPS, ccRM and Greedy method – little time to schedule and constant
overhead
LP method – more time to schedule; and average overhead of 53us – large
overhead is unacceptable
31
Scheduling Overheads


Small hyperperiod – reduces the number of rescheduling
points
Overall overlap of LP method using pinwheel method is
reduced due to lesser number of scheduling points
32
Effect of Profiling Tool
More energy can be saved according to task
execution at runtime
 Rescheduling when the codes inserted by
the profiling tool are executed
 Parameter of interest – AET / WCET
 Bigger ratio, more saving – greater
opportunity for adjustment
 33% additional energy saving at 50%
AET/WCET at 70% utilization
 For AET close to WCET, there is very little
unused time for online schedule adjustment

33
Energy Reduction
at
Runtime
TM 58EL-667
Average
energy saving of 17.85%
TM58EX-993
34
OUTLINE
•Motivation
•Introduction
•Pinwheel Transformation
•Methods of Power Reduction
•Simulations and Results
•Conclusion
Conclusion





Harmonic nature of pinwheel model is beneficial for
deterministic task scheduling in power-aware real-time
scheduling
Various techniques can be used to fully utilize whole system
slack times
Power-aware scheduling with Pinwheel method achieves
considerable energy savings with manageable scheduling
overhead
Profiling tool provides runtime information for better
scheduling
In summary :
Pinwheel model is a systematic approach and a computationally feasible
solution for full utilization of system slack times to minimize energy
consumption.
36
QUESTIONS
37