O'Reilly logo

VLSI Digital Signal Processing Systems: Design and Implementation by Keshab K. Parhi

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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

image

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 image 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 image = −1. Note that longest path between any two nodes can be computed using any path algorithm in Appendix A. For example, to determine image 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.

Start Free Trial

No credit card required