VLSI Digital Signal Processing Systems: Design and Implementation

2.4    ALGORITHMS FOR COMPUTING ITERATION BOUND

The two iteration-bound algorithms described in this section are demonstrated using the DFG in Fig. 2.2. This DFG has three loops: loop l₁ = 1 → 4 → 2 → 1 with loop bound 4/2 u.t., loop l₂ = 1 → 5 → 3 → 2 → 1 with loop bound 5/3 u.t., and loop l₃ = 1 → 6 → 3 → 2 → 1 with loop bound 5/4 u.t. Therefore, the iteration bound of this DFG is

2.4.1    Longest Path Matrix Algorithm

In the longest path matrix (LPM) algorithm [3], a series of matrices is constructed, and the iteration bound is found by examining the diagonal elements of the matrices. Let d be the number of delays in the DFG. These matrices, L^(m), m = 1, 2, … , d, are constructed such that the value of the element is the longest computation time of all paths from delay element d_i to delay element d_j that pass through exactly m − 1 delays (not including d_i and d_j). If no such path exists, then = −1. Note that longest path between any two nodes can be computed using any path algorithm in Appendix A. For example, to determine for the DFG in Fig. 2.2, all paths from the delay element ...