## 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} = 1 → 4 → 2 → 1 with loop bound 4/2 u.t., loop *l*_{2} = 1 → 5 → 3 → 2 → 1 with loop bound 5/3 u.t., and loop *l*_{3} = 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 ...