VLSI Digital Signal Processing Systems: Design and Implementation

2.5    ITERATION BOUND OF MULTIRATE DATA-FLOW GRAPHS

Up to this point, we have only considered single-rate DFGs (SRDFGs), i.e., DFGs where each node is executed exactly once per iteration. Another class of DFGs, called multirate DFGs (MRDFGs) [7], allows each node to be executed more than once per iteration, and 2 nodes are not required to execute the same number of times in an iteration (see Section 1.4.3). A 2-step process can be used to compute the iteration bound of a multirate DFG. This 2-step process is

1. Construct a SRDFG that is equivalent to the MRDFG.
2. Compute the iteration bound of the equivalent SRDFG using the LPM algorithm, or the MCM algorithm.

The iteration bound of the MRDFG is the same as the iteration bound of the equivalent SRDFG. In this section, MRDFGs are defined and an algorithm is presented for constructing an equivalent SRDFG from an MRDFG (Step 1) so that 1 of the 2 algorithms described in this chapter can be used to compute the iteration bound of the equivalent SRDFG (step 2).

An edge from the node U to the node V in an MRDFG is shown in Fig. 2.8. The value O_UV is the number of samples produced on the edge by an invocation of the node U, and the value I_UV is the number of samples consumed from the edge by an invocation of the node V. The value i_UV is the number of delays on the edge.

If the nodes U and V are invoked k_U times and k_V times, respectively, in an iteration, then the number of samples produced on the edge from the node U to the node V in 1 ...