## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

## 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 l1 = 1 → 4 → 2 → 1 with loop bound 4/2 u.t., loop l2 = 1 → 5 → 3 → 2 → 1 with loop bound 5/3 u.t., and loop l3 = 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 di to delay element dj that pass through exactly m − 1 delays (not including di and dj). 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 ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required