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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:61961", author = "Ali Shatnawi", title = "Computing the Loop Bound in Iterative Data Flow Graphs Using Natural Token Flow", 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.", volume = "1", number = "10", pages = "3243-6", }