Computing the Loop Bound in Iterative Data Flow Graphs Using Natural Token Flow

Signal processing applications which are iterative in nature are best represented by data flow graphs (DFG). In these applications, the maximum sampling frequency is dependent on the topology of the DFG, the cyclic dependencies in particular. The determination of the iteration bound, which is the reciprocal of the maximum sampling frequency, is critical in the process of hardware implementation of signal processing applications. In this paper, a novel technique to compute the iteration bound is proposed. This technique is different from all previously proposed techniques, in the sense that it is based on the natural flow of tokens into the DFG rather than the topology of the graph. The proposed algorithm has lower run-time complexity than all known algorithms. The performance of the proposed algorithm is illustrated through analytical analysis of the time complexity, as well as through simulation of some benchmark problems.

Authors:

• Ali Shatnawi

Keywords:

• Data flow graph
• Iteration period bound
• Rateoptimalscheduling
• Recursive DSP algorithms.

References:

[1] M. Renfors, and Y. Neuvo, "The maximum sampling rate of digital
filters under hardware speed constraints," IEEE Transactions on Circuits
and Systems, vol. CAS-28, no. 3, pp. 196-202, Mar. 1981
[2] D. Y. Chao and D. Y. Wang, "Iteration Bounds of Single-Rate Data
Flow Graphs for Concurrent Processing," IEEE Trans. Circuits Syst.-I,
vol. CAS-40, pp. 629-634, Sept. 1993.
[3] S. H. Gerez, S. M. Heemstra de Groot, and O. E. Herrmann, "A
Polynomial-Time Algorithm for the Computation of the Iteration-Period
Bound in Recursive Data-Flow Graphs," IEEE Trans. Circuits Syst.-I,
vol. CAS-39, pp. 49- 52, Jan. 1992
[4] K. Ito and K. K. Parhi, "Determining the Iteration Bounds of Single-Rate
and Multi-Rate Data-Flow Graphs," in Proc. Of 1994 IEEE Asia-Pacific
Conf. on Circuits and Systems, Taipei, Taiwan, pp. 6A.1.1-6A.1.6, Dec.
1994.
[5] R. M. Karp, "A Characterization of the Minimum Cycle Mean in a
Digraph," Discrete Mathematics, vol. 23, pp. 309-311, 1978.
[6] R. Govindarajan and G. R. Gao, "A Novel Framework for Multi-Rate
Scheduling in DSP Applications," in Proc. 1993 Int. Conf. Application-
Specific Array processors, pp. 77-88, IEEE Computer Society Press,
1993.
[7] K. Ito and K. K. Parhi," determining the minimum iteration period of an
algorithm" Journal of VLSI Signal Processing, 11, (Dec.1995) 229-
244.
[8] A. Dasdan, S. S. Irani and R. K. Gupta, "An Experimental Study of
Minimum Mean Cycle Algorithms", UCI-ICS TR #98-32, UIUC,
Urbana, USA.
[9] M. N. S. Swamy, and K. Thulasiraman, "Graphs, networks, and
algorithms," John Wiley & Sons, Inc., New York, 1981.