Abstract
Digital signal processing algorithms are repetitive in nature. These algorithms are described by iterative data-flow graphs where nodes represent computations and edges represent communications. For all data-flow graphs, there exists a fundamental lower bound on the iteration period referred to as theiteration bound. Determining the iteration bound for signal processing algorithms described by iterative data-flow graphs is an important problem. In this paper we review two existing algorithms for determination of the iteration bound. Then we propose another novel method based on theminimum cycle mean algorithm to determine the iteration bound with a lower polynomial time complexity than the two existing techniques. It is convenient to represent many multi-rate signal processing algorithms by multi-rate data-flow graphs. The iteration bound of a multi-rate data-flow graph (MRDFG) can be determined by considering the single-rate data-flow graph (SRDFG) equivalent of the MRDFG. However, the equivalent single-rate data-flow graph contains many redundant nodes and edges. The iteration bound of the MRDFG can be determined faster if these redundancies in the equivalent SRDFG are first removed. A previous approach has considered elimination of edge redundancy. In this paper we present an approach to eliminatenode redundancy in the MRDFG. We combine elimination of node and edge redundancies to propose a novel algorithm for faster determination of the iteration bound of the MRDFG.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
K.K. Parhi, “Algorithm Transformation Techniques for Concurrent Processors,”Proc. of the IEEE, Vol. 77, pp. 1879–1895, Dec. 1989.
E.A. Lee and D.G. Messerschmitt, “Static Scheduling of Synchronous Data Flow Program for Digital Signal Processing,”IEEE Trans. Computers, Vol. C-36, pp. 24–35, Jan. 1987.
M. Renfors and Y. Neuvo, “The Maximum Sampling Rate of Digital Filters under Speed Constraints,”IEEE Trans. Circuits Syst., Vol. CAS-28, pp. 196–202, Mar. 1981.
D.A. Schwartz and T.P. Barnwell, III, “A Graph Theoretic Technique for the Generation of Systolic Implementations for Shift Invariant Flow Graphs,” inProc. of the 1984 IEEE ICASSP, San Diego, CA, Mar. 1984.
K.K. Parhi and D.G. Messerschmitt, “Static Rate-Optimal Scheduling of Iterative Data-Flow Programs via Optimum Unfolding,”IEEE Trans. Computers, Vol. C-40, pp. 178–195, Feb. 1991.
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.
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.
K. Ito and K.K. Parhi, “Determining the Iteration Bounds of Single-Rate and Multi-Rate Data-Flow Graphs,” inProc. of 1994 IEEE Asia-Pacific Conf. on Circuits and Systems, Taipei, Taiwan, Dec. 1994, pp. 6A.1.1–6A.1.6.
R.M. Karp, “A Characterization of the Minimum Cycle Mean in a Digraph,”Discrete Mathematics, Vol. 23, pp. 309–311, 1978.
R. Govindarajan and G.R. Gao, “A Novel Framework for Multi-Rate Scheduling in DSP Applications,” inProc. 1993 Int. Conf. Application-Specific Array Processors, pp. 77–88, IEEE Computer Society Press, 1993.
E.M. Reingold, J. Nievergelt, and N. Deo,Combinatorial Algorithms: Theory and Practice, Englewood Cliffs, NJ: Prentice Hall, 1977.
E.L. Lawler,Combinatorial Optimization: Networks and Matroids. New York: Holt, Rinehart and Winston, 1976.
S.S. Bhattacharyya, J.T. Buck, S. Ha, and E.A. Lee, “A Scheduling Framework for Minimizing Memory Requirements of Multirate DSP Systems Represented as Dataflow Graphs,” inVLSI Signal Processing, VI, pp. 188–196, 1993.
S.Y Kung, H.J. Whitehouse, and T. Kailath,VLSI and Modern Signal Processing, Englewood Cliffs, NJ: Prentice Hall, 1985.
J.-G. Chung and K.K. Parhi, “Pipelining of Lattice IIR Digital Filters,”IEEE Trans. Signal Processing, Vol. SP-42, pp. 751–761, Apr. 1994.
Author information
Authors and Affiliations
Additional information
This research was supported by the Advanced Research Projects Agency and monitored by Wright—Patterson AFB under contract number F33615-93-C-1309.
Rights and permissions
About this article
Cite this article
Ito, K., Parhi, K.K. Determining the minimum iteration period of an algorithm. Journal of VLSI Signal Processing 11, 229–244 (1995). https://doi.org/10.1007/BF02107055
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02107055