Transcript Application-Specific Heterogenous Multiprocessor Synthesis Using

Application-Specific
Heterogeneous Multiprocessor Synthesis
Using Differential-Evolution
Allan Rae
Sri Parameswaran
Dept. of Computer Science and Electrical Engineering
University of Queensland
St. Lucia, Queensland, Australia.
{rae,sridevan}@csee.uq.edu.au
HeMPS
Overview
 Motivation
 Related work
 Differential Evolution overview
 Description of algorithms
 Worked example
 Results
 Conclusions
HeMPS
Motivation
 Application specific systems range from washing machines to
supercomputers (GRAPE IV)
 Most are embedded computers
– becoming more complex with shorter time-to-market
 Short product cycles limit the number of test designs
 Design quality limited by designers experience
– design reuse or adaptation
 Innovative design methodologies required to assist designers
HeMPS
HeMPS Strategy
 Problem-space differential-evolution heuristic
– Differential evolution in conjunction with a problem-specific
heuristic
• list-scheduling heuristic
 Input :
– task data flow graph
– library of processor and communication link types
– set of subtask execution times for each processor type
 Output :
– a distributed, heterogeneous multiprocessor architecture
using a point-to-point network
– subtask allocations for each processor
– a static task schedule
HeMPS
Related Work








Scheduling and allocation problem is NP-complete
Numerous heuristics developed in scheduling work
Very few heuristics for multiprocessor synthesis
Prakash & Parker (SOS) 1992
– Mixed Integer, Linear-Programming model
Dhodhi, Ahmad and Storer (SHEMUS) 1995
– Problem-space genetic algorithm with list-scheduling.
Wolf 1997
– multistep heuristic
Dasgupta & Karri (RELSYNOPT) 1997
– reliability-optimal synthesis
Bjørn-Jørgensen and Madsen 1997
– Heterogeneous Critical-Path (HCP) algorithm
– maximum performance for a given set of processors
HeMPS
Differential Evolution
 Evolutionary Computation
– Evolutionary Strategies
• Germany 1960’s, Rechenberg, Schwefel
– Evolutionary Programming
• USA 1960’s, Larry Fogel
– Genetic Algorithms
 Differential Evolution, Storn and Price.
– Descendent of Evolutionary Strategies
– Mutation generated by vector differentials
• Optimum mutation step size is a function of the
standard deviation of the parameters in the population.
• Each parameters optimum step size is different and
varies over time.
HeMPS
Differential Evolution Crash Course
X
 Population X

 Parent vectorXc
 Two randomly chosen vectors


– X a andX b




Xc  Xc  F   Xa  Xb 

 
Xc  Crossover  Xc , Xc 

Better ofXc

and
Xc
goes in new population X’
X’
HeMPS
DE Algorithm
X
 Initialise the population
with uniform random values
X of
 Determine quality of members
using a scheduling
heuristic

 repeat
Xc X


– foreach parent
in
Xa
Xb




• RandomlyXselect
and
  Xa  Xbpair
c  Xc a Fdifference


 
• CalculateX
c  Crossover  Xc , Xc 

• Calculate
Xc


• Determine
the quality
of
Xc
X
c

• if
is X
better
than
X
c

– thenX
goes in new population
X
c
– else
goes in new population
– X
endfor

X
–
replaces
 until population converged or generation limit
HeMPS
Synthesis Strategy
 Trial vectors represent
– Numbers of each type of processor available for selection
– List of subtask priorities
 Fitness of a solution determined by a problem-specific heuristic
– simple list-scheduling heuristic
 Output of heuristic used to judge fitness
n
n
n
– Total time: Tt
CPi 
CL ( i , j )
– Implementation cost: Ct 

i 1

i 1 j 1
– Choice of cost, Ct , or performance, Tt , optimisation
– Target value,
V
• for example: TtV
Ct0
HeMPS
Scheduling Heuristic
 Any heuristic could be used.
 We use a simple list-scheduler so the DE algorithm does the
work of finding a good solution.
 Better heuristics should therefore help HeMPS achieve even
faster results.
 Subtask priorities (part of trial vector) establish the order in
which to attempt to schedule the subtasks onto processors.
 Priority Scheduling
– A given priority list may not be achievable
• Modify or repair the priority list so it is achievable
HeMPS
Illustrative Example
 Prakash and Parker’s first example
 3 processor types and 4 subtasks
1
2
3
4

Xc  0.84, 1.43, 0.46 1.04, 2.19, 0.1, 3.38
1, 1, 0
4, 2, 1, 3
Priority Schedule:
Unachievable
Repaired Priority Schedule: 1, 2, 4, 3
HeMPS
(Swapping repair)
Example Continued
 Processor
P0:
2
4
P1:
1
Links:
1, 1, 0
costs and subtask times
x, 3, 1, x
1, 1, x, 3
1
1
2
1, 2, 4, 3
3
4
P0
1
2
3
4
P1
1
Total Cost: 4+2+1 = 7
Total Time: 4
2
4
3
HeMPS
Results
#
period
Implementation Cost
Wolf SHEMUS
HeMPS
P&P
HeMPS
CPU Time (s)
SHEMUS
Wolf
-
P&P
11
24
28
37
pp1
4
2.5
3
4
7
14
7
5
14
14
7
5
-
14
13
7
5
0.09
0.09
0.09
0.05
0.05
0.05
0.05
pp2
9
5
6
7
8
15
15
12
8
7
5
15
12
8
8
5
15
7
-
15
12
8
7
5
0.24
0.16
0.16
0.18
0.12
0.7
1.1
1.6
1.0
1.1
dye
15
0.1
59
59
-
-
0.83
7.2
-
-
robot 25
20
23
14
9
-
17
-
1.55
1.55
-
7.3
-
Examples from Prakash and Parker, Wolf and SHEMUS
HeMPS
3732
1.3
- 26710
- 32320
4511
1.1
- 385012
Conclusions
 HeMPS, combines a problem-specific heuristic with differential
evolution.
 This combination enables the system to rapidly and efficiently
search the design-space for an optimal or near-optimal
solution.
 Provides equal or better results for the examples described.
 As the number of subtasks is increased the execution time of
HeMPS remains low.
HeMPS
Latest Advances
 Power minimisation
– selection of low power implementations
– voltage reduction to further minimise power consumption
 Database of previous calculations
– Reduces runtime when evolution results in repetition of
earlier trial solutions
 Initialisation experiments
– Previously only random initialisations were used
– Trialled ALAP, ASAP, HCP…
 Revised problem-specific heuristic
– experimenting with a modified HCP heuristic
– trial solutions now represent a list of allocations to
processor types and numbers of those types of processors
HeMPS