Transcript Fast and Near Optimal Scheduling In Automatic Data Path

courseware
List-Based Scheduling
Sune Fallgaard Nielsen
Informatics and Mathematical Modelling
Technical University of Denmark
Richard Petersens Plads, Building 322
DK2800 Lyngby, Denmark
Overview





Introduction
Related work
DFG and WPG
ASAP, ALAP and Mobility
Solution:




Algorithm
Selection function
Extenstions
Time complexity
 Results
 Conclussion
SoC-MOBINET courseware
[M-1] High-Level Synthesis
2
Introduction
 Given a DFG we want to schedule operations to
minimize the number of functional units needed
(adders, multiplier, ALUs, etc.)
 Input to algorithm
 DFG
 Number of cycles.(Not less than shortest path in DFG)
*
 Model must include
 Pipelined operations
 Chained operations
 Multicycle operations
SoC-MOBINET courseware
[M-1] High-Level Synthesis
+
*
*
3
Related Work
 Other algorithms fix operations one by one
 Tend to find local minima instead of global minima
 ILP(Integer Linear programming)
 Finds global minima
 Is an exponential time algorithm and are not usable for
large data-sets
 This algorithm can escape local minimals by
making several iterations.
 Tend to find global minimaes (But, no guarantee)
SoC-MOBINET courseware
[M-1] High-Level Synthesis
4
DFG and WPG
 From “Data Flow Graph” to “Weighted Precedence Graph”
SoC-MOBINET courseware
[M-1] High-Level Synthesis
5
ASAP Scheduling
 Minimum number of cycles with no resource limitation
SoC-MOBINET courseware
[M-1] High-Level Synthesis
6
ALAP Scheduling
 Minimum number of cycles with no resource limitation
SoC-MOBINET courseware
[M-1] High-Level Synthesis
7
Mobility
 Mobility tells which steps each operation can be
placed
SoC-MOBINET courseware
[M-1] High-Level Synthesis
8
Algorithm - overview
 Starts from ASAP/ALAP
 Iteratively moves operations based on selection
function Si(j,k). (Must not violate WPG)
 If no ”good” moves are possible, ”bad” ones are
taken.
 Stops when there are no movable operations
 Select best solution based on cost function from all
solutions explored. (Fx. number of functional units)
 Repeat the above iteration while the solution
improves
SoC-MOBINET courseware
[M-1] High-Level Synthesis
9
Algorithm - pseudu
repeat{
Count=1
While movable operations{
select tuple(i, k) with maximum Si(j,k)
move Oi to step k
lock tuple(i, k)
gaincount=change in cost when moving Oi to step k
}
find k that maximizes
k
gain max
gain i
if(gainmax>0)
i 1
Move operations 1 to k
}until(gainmax<=0)
SoC-MOBINET courseware
[M-1] High-Level Synthesis
10
Algorithm - example
SoC-MOBINET courseware
[M-1] High-Level Synthesis
11
Algorithm - solution
 Solution to running example
SoC-MOBINET courseware
[M-1] High-Level Synthesis
12
Selection Function
 In each step the selection function
 Causes most balanced distribution of operations
 Reduces number of required functional units.
Si j , k
max Density j , Density k CDG
 Expresses the gain by moving Oi from step j to k
 Proportional with
 Maximal density at step j and k
 Change in Density Gradient(DG)
(Density[i] is the number of functional units at step i)
SoC-MOBINET courseware
[M-1] High-Level Synthesis
13
Selection function
 “Change in Density Gradient” (CDG)
CDG DG before DG after
CDG Density j Density k
Density j 1
Density k 1
 CDG equals (Only concerns the 2 affected steps)
 2
 0
 -2
Number of functional units decreases by 1
No change in number of functional units needed
Number of functional units increases by 1
SoC-MOBINET courseware
[M-1] High-Level Synthesis
14
Selection function
 Examples of Selection function calculations
SoC-MOBINET courseware
[M-1] High-Level Synthesis
15
Extensions
 Mutually Exclusive(ME) operations
 Fx. an if-else statement. Operations that are ME can be
placed in the same step on the same functional unit
 Chained operations
 Are already incoporated into the WPG
 Multi-cycle operations
 Are included in the WPG, but selection function must be
expanded.
 Pipelined operations
 I do not understand the articles interpretation of a
pipeline. Shall be treated as a multi-cycle operation.
SoC-MOBINET courseware
[M-1] High-Level Synthesis
16
Time complexity
m Number of operations in DFG
S Number of control steps
n Total number of tuples( max=Sm)
 After each move update cost
O(m*log(m))
 This must be done for all tuples
O(nm*log(m))) = (Sm2*log(m))
 Practial time complexity (stated by authors)
O(n*log(m)) (since n i independant of m)
 Number of iterations is assumed independent of
problem
SoC-MOBINET courseware
[M-1] High-Level Synthesis
17
Results – Example 1
 Chained operations with the number of cycles less
than 8
SoC-MOBINET courseware
[M-1] High-Level Synthesis
18
Results – Example 2
 Pipelined 16-point FIR filter. 2 types of functions
units (Multiplier and adder)
SoC-MOBINET courseware
[M-1] High-Level Synthesis
19
Results – Example 3
 5th order elliptic filter with25 additions and 8
multiplications. Multiply is a multicycle operation
SoC-MOBINET courseware
[M-1] High-Level Synthesis
20
Conclusion
 Very fast an effective
 Can escape local minima
 Tend to reach optimal solution. (At least for all
experimental results so far)
 Must faster than than previous approaches.
 Handles multicycled, chained and pipelined
operations.
 Possible to use more sophisticated selection
functions.
SoC-MOBINET courseware
[M-1] High-Level Synthesis
21