Transcript A Voltage Scheduling Heuristic for Real

VOLTAGE SCHEDULING
HEURISTIC for REAL-TIME
TASK GRAPHS
D. Roychowdhury, I. Koren, C. M. Krishna
University of Massachusetts, Amherst
Y.-H. Lee
Arizona State University
Motivation


Energy Constrained Complex Real-Time
Systems are becoming increasingly important
Scheduling – an effective system
management entity to exploit



Schedule tasks such that energy expenditure is
minimized while still meeting the deadline
Exploit multiple voltage levels provided by
processors to achieve our goal
We focus on applications having tasks with
precedence constraints (can be represented as
task graphs)
June 25, 2003
CMOS system equations

slow(v) is the factor by which processor is slower at
voltage v than it is at the reference high voltage vh :
 Threshold voltage is vT
2
v
slow (v) 
vh

 vh  vT

 v  vT



energy_per_cycle(v) is the ratio of energy
consumed per cycle at voltage v to that at vh :
v
energy _ per _ cycle (v)   
 vh 
2
June 25, 2003
System Assumptions




Can run in discrete number of variable voltage levels
 Algorithms are provided for a 2-voltage level
system followed by extensions for systems
supporting multiple voltage levels
A task can only continue if all preceding tasks on
which it depends complete
The energy cost during communication and idle state
in processors is negligible
Voltage switching costs are incorporated within the
worst scale profiling of tasks
June 25, 2003
Required Inputs




Task graph (directed acyclic graph) showing
the precedence constraints between the
tasks after their assignment
Deadline by which the given task set must
finish
Worst case execution profile of individual
tasks under different voltage levels
Distribution of execution profile of each task
June 25, 2003
Key issues



Static scheduling of the assigned Task
Graph
Run-time scheme for dynamic resource
reclamation
Extension to a Multi-Voltage System
June 25, 2003
Optimization Problem




D - Deadline
Si - speed up in time associated with task i
tk - worst case time when all tasks in path Pk
run in low voltage
Constraint equations:


s
For path Pk
jPk
Objective function:

Minimize :
s
j
 tk  D
i
i
June 25, 2003
Static Scheduling


Start by keeping all tasks in low voltage
Start speeding up tasks with highest weight gradually



We speed up the task with highest weight until some
other task has a higher weight



Weight of a task is number of critical paths of which that
task is a member
Critical path is a path that currently fails to meet its deadline
under worst case execution profile.
For the tasks with equal weights break the tie by speeding
up the task nearest to a leaf in graph
We continue until all paths meet the deadline
Assign start time and commit time for each task
based on the above voltage scheduling
June 25, 2003
Example Graph
Paths
(60) 28
1
1
4
3
2
24
3
(43)
20
2
5
28
1
3
2->4->5
2->4->6
4
6
1->5
2->4->7
16
1
DEADLINE=93
7
3->7
18
2
June 25, 2003
Example Graph
Paths
28
1
1
4
2
24
2
2
28
1
3
1->5
2->4->5
2->4->6
4
2->4->7
3->7
20
2
5
6
16
0
7
18
2
June 25, 2003
Gantt Chart (Static)
June 25, 2003
Run-Time Adjustments



Each task has an assigned start time and
commit time from static scheduling
If a task can be issued before its statically
assigned start time, we can slow down the
task to save energy
The slow down must still yield same commit
time
June 25, 2003
Example Graph
22.88
1
2.5
26.8
11.8
5
2
26.1
3
4
7
6
11.2
14.86
June 25, 2003
Gantt Chart (dynamic)
June 25, 2003
Key issues



Static scheduling
Run-time dynamic resource reclamation
Extension to a Multi-Voltage System
June 25, 2003
Using Multiple Voltage Levels




Calculate start time and commit time for
tasks using the static scheduling
Vunique - voltage at which we can finish task
within specified interval without voltage
switching
2 voltage levels are chosen within which
Vunique falls
The switching point is chosen between the
two levels such that task finishes exactly at
commit time
June 25, 2003
Simulation Results


We used systems which support the following
voltage-frequency combinations
Voltage
(V)
Frequency
(MHz)
1
1.75
1000
2
1.40
800
3
1.20
600
4
1.00
466
We use sparse matrix calculation as an
example application
June 25, 2003
Energy Saving after runtime
adjustment
Task execution time uniformly
distributed in [A,100] of WCET
June 25, 2003
Energy Saving due to Dynamic
Resource Reclamation
June 25, 2003
Energy saving over an Infinite
Voltage Levels Algorithm (Zhu et al.)
voltage switching allowed only during context switching
June 25, 2003
Energy saving when multiple (4)
voltage levels used instead of 2
June 25, 2003
Conclusion



Considerable energy can be saved by using
our algorithm which takes into account the
relationship among tasks in the set
The algorithm is based on a practical
assumption that processor supports two
voltage levels
We have extended the algorithm for cases
which can use multiple voltage levels though
the gain is not much more significant than
two voltage level case
June 25, 2003
Thank You
URL: http://www.ecs.umass.edu/ece/realtime
June 25, 2003