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

Authors: Ali Shatnawi

Abstract:

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.

Keywords: Data flow graph, Iteration period bound, Rateoptimalscheduling, Recursive DSP algorithms.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1080185

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.