This document discusses techniques for computing the iteration bound of digital signal processing (DSP) programs. It introduces the concepts of critical path, loop bound, and iteration bound. It then describes two algorithms - the Longest Path Matrix method and Minimum Cycle Mean method - for calculating the iteration bound of a data flow graph representing a DSP program. It also addresses how to compute the iteration bound of a multirate DSP program by first transforming it into an equivalent single-rate data flow graph.
This document discusses techniques for computing the iteration bound of digital signal processing (DSP) programs. It introduces the concepts of critical path, loop bound, and iteration bound. It then describes two algorithms - the Longest Path Matrix method and Minimum Cycle Mean method - for calculating the iteration bound of a data flow graph representing a DSP program. It also addresses how to compute the iteration bound of a multirate DSP program by first transforming it into an equivalent single-rate data flow graph.
This document discusses techniques for computing the iteration bound of digital signal processing (DSP) programs. It introduces the concepts of critical path, loop bound, and iteration bound. It then describes two algorithms - the Longest Path Matrix method and Minimum Cycle Mean method - for calculating the iteration bound of a data flow graph representing a DSP program. It also addresses how to compute the iteration bound of a multirate DSP program by first transforming it into an equivalent single-rate data flow graph.
This document discusses techniques for computing the iteration bound of digital signal processing (DSP) programs. It introduces the concepts of critical path, loop bound, and iteration bound. It then describes two algorithms - the Longest Path Matrix method and Minimum Cycle Mean method - for calculating the iteration bound of a data flow graph representing a DSP program. It also addresses how to compute the iteration bound of a multirate DSP program by first transforming it into an equivalent single-rate data flow graph.
2 Tsung-Han Tsai 1 Chapter 2 Iteration Bound NCU EE -- DSP VLSI Design. Chap. 2 Tsung-Han Tsai 2 Iteration Bound &Introduction &Critical path &Loop Bound t Important Definitions and Examples &Iteration Bound t Important Definitions and Examples t Techniques to Compute Iteration Bound NCU EE -- DSP VLSI Design. Chap. 2 Tsung-Han Tsai 3 Critical Path &The path with longest computation time and zero delay. &the minimal computation time required for one iteration of DFG &Speed of the DSP system: t depends on the critical path comp. time &The loop with the maximum loop bound NCU EE -- DSP VLSI Design. Chap. 2 Tsung-Han Tsai 4 Loop Bound &The lower bound on the loop computation time loop) of delays of number ( n time) computatio loop ( Bound Loop = = = l l w t NCU EE -- DSP VLSI Design. Chap. 2 Tsung-Han Tsai 5 Loop Bound (contd) &If no delay element in the loop, then t Delay-free loops are non-computable, see the example NCU EE -- DSP VLSI Design. Chap. 2 Tsung-Han Tsai 6 Iteration Bound &The critical loop is the loop with maximum loop bound which is the bound for the DSP program &Iteration bound= Max { 6/2 , 11/1 }=11 NCU EE -- DSP VLSI Design. Chap. 2 Tsung-Han Tsai 7 Recursive &A non-recursive DFG contains no loops &A recursive DFG at least one loop T
&A recursive DFG has a fundamental limit on the speed =
Iteration Bound &Iteration bound= Max { 4/2 , 5/3, 5/4 }=2 NCU EE -- DSP VLSI Design. Chap. 2 Tsung-Han Tsai 8 Iteration Bound (contd) &Algorithms to compute iteration bound t Longest Path Matrix (LPM) t Minimum Cycle Mean (MCM) NCU EE -- DSP VLSI Design. Chap. 2 Tsung-Han Tsai 9 Algorithms to Compute Iteration Bound &Longest Path Matrix Algorithm (LPM) t d: # of delays (=4 here ) t Compute L (1) ~L (4) t l, i, j: The longest computation time of all paths from delay element d i to delay element d j that pass through exactly m-1 delays t K: int in [1~d] t NCU EE -- DSP VLSI Design. Chap. 2 Tsung-Han Tsai 10 Examples for LPM 1 NCU EE -- DSP VLSI Design. Chap. 2 Tsung-Han Tsai 11 Examples for LPM(contd) Example 2: } 2 16 , 2 12 , 1 8 , 1 4 max{ 16 16 12 12 8 8 4 4 2 ) 2 ( ) 1 ( =
= =
T L L d NCU EE -- DSP VLSI Design. Chap. 2 Tsung-Han Tsai 12 Algorithms to Compute Iteration Bound &Minimum Cycle Mean Method (MCM) 1. Construct the new graph G d and G d
transform from DFG
decide the weight of each edge 2. Compute the maximum cycle mean construct the series of d+1 vectors f (m) find the max cycle mean 3. find the min cycle mean between each cycle NCU EE -- DSP VLSI Design. Chap. 2 Tsung-Han Tsai 13 &delay node &longest path length (computation time) weight w(i,j) Example to MCM NCU EE -- DSP VLSI Design. Chap. 2 Tsung-Han Tsai 14 Example to MCM(contd) &longest path length t path which pass through no delays t longest : two loops that contain Da and DB max { 6,4 } = 6 t cycle mean = 6/2=3 NCU EE -- DSP VLSI Design. Chap. 2 Tsung-Han Tsai 15 Example to MCM(contd) &Cycle mean= average length of the edge in c (cycle = loop ) &We need the maximum one G in cycles in these delays of number the c in delays e contain th G that in cycles all of n time computatio max NCU EE -- DSP VLSI Design. Chap. 2 Tsung-Han Tsai 16 Example to MCM(contd) &Compute the cycle mean t weights of the edges x-1 &hence called MCM NCU EE -- DSP VLSI Design. Chap. 2 Tsung-Han Tsai 17 Example to MCM(contd) &We will find d+1 vectors , f (m) m=0, 1,~, d ( dimension = d1 ) &s=1
= 0 ) 0 ( f NCU EE -- DSP VLSI Design. Chap. 2 Tsung-Han Tsai 18 Example to MCM(contd) & & I ={ i : path from node i to j exists }
= 0 ) 0 ( f
= 0 ) 1 ( f
= 0 4 ) 2 ( f
= 0 4 5 ) 3 ( f
= 4 5 8 ) 4 ( f NCU EE -- DSP VLSI Design. Chap. 2 Tsung-Han Tsai 19 Example to MCM(contd) &The iteration bound is given by: NCU EE -- DSP VLSI Design. Chap. 2 Tsung-Han Tsai 20 Example to MCM(contd) NCU EE -- DSP VLSI Design. Chap. 2 Tsung-Han Tsai 21 Multirate DFGs &Iteration bound of Multirate Data-flow Graphs t Construct a SRDFG that is equivalent to the MRDFG t Compute the iteration Bound of the equivalent SRDFG using the LPM algorithm O UV ,I UV : # of samples I/O of the node per invocation i UV : delay k U ,k V : # of invocation per iteration v UV U UV k l k O = NCU EE -- DSP VLSI Design. Chap. 2 Tsung-Han Tsai 22 Transformation of Multi Rate DFG NCU EE -- DSP VLSI Design. Chap. 2 Tsung-Han Tsai 23 Multi Rate DFG to Single Rate DFG NCU EE -- DSP VLSI Design. Chap. 2 Tsung-Han Tsai 24 Conclusion &When the DFG is recursive, the iteration bound is the fundamental limit on the minimum sample period of a hardware implementation of the DSP program. &Two algorithms to compute iteration bound, LPM and MCM, were introduced. &The iteration bound of a multirate DFG can also be determined.
