{"title":"Computing the Loop Bound in Iterative Data Flow Graphs Using Natural Token Flow","authors":"Ali Shatnawi","volume":10,"journal":"International Journal of Computer and Information Engineering","pagesStart":3336,"pagesEnd":3342,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/12934","abstract":"Signal processing applications which are iterative in\r\nnature are best represented by data flow graphs (DFG). In these\r\napplications, the maximum sampling frequency is dependent on the\r\ntopology of the DFG, the cyclic dependencies in particular. The\r\ndetermination of the iteration bound, which is the reciprocal of the\r\nmaximum sampling frequency, is critical in the process of hardware\r\nimplementation of signal processing applications. In this paper, a\r\nnovel technique to compute the iteration bound is proposed. This\r\ntechnique is different from all previously proposed techniques, in the\r\nsense that it is based on the natural flow of tokens into the DFG\r\nrather than the topology of the graph. The proposed algorithm has\r\nlower run-time complexity than all known algorithms. The\r\nperformance of the proposed algorithm is illustrated through\r\nanalytical analysis of the time complexity, as well as through\r\nsimulation of some benchmark problems.","references":"[1] M. Renfors, and Y. Neuvo, \"The maximum sampling rate of digital\r\nfilters under hardware speed constraints,\" IEEE Transactions on Circuits\r\nand Systems, vol. CAS-28, no. 3, pp. 196-202, Mar. 1981\r\n[2] D. Y. Chao and D. Y. Wang, \"Iteration Bounds of Single-Rate Data\r\nFlow Graphs for Concurrent Processing,\" IEEE Trans. Circuits Syst.-I,\r\nvol. CAS-40, pp. 629-634, Sept. 1993.\r\n[3] S. H. Gerez, S. M. Heemstra de Groot, and O. E. Herrmann, \"A\r\nPolynomial-Time Algorithm for the Computation of the Iteration-Period\r\nBound in Recursive Data-Flow Graphs,\" IEEE Trans. Circuits Syst.-I,\r\nvol. CAS-39, pp. 49- 52, Jan. 1992\r\n[4] K. Ito and K. K. Parhi, \"Determining the Iteration Bounds of Single-Rate\r\nand Multi-Rate Data-Flow Graphs,\" in Proc. Of 1994 IEEE Asia-Pacific\r\nConf. on Circuits and Systems, Taipei, Taiwan, pp. 6A.1.1-6A.1.6, Dec.\r\n1994.\r\n[5] R. M. Karp, \"A Characterization of the Minimum Cycle Mean in a\r\nDigraph,\" Discrete Mathematics, vol. 23, pp. 309-311, 1978.\r\n[6] R. Govindarajan and G. R. Gao, \"A Novel Framework for Multi-Rate\r\nScheduling in DSP Applications,\" in Proc. 1993 Int. Conf. Application-\r\nSpecific Array processors, pp. 77-88, IEEE Computer Society Press,\r\n1993.\r\n[7] K. Ito and K. K. Parhi,\" determining the minimum iteration period of an\r\nalgorithm\" Journal of VLSI Signal Processing, 11, (Dec.1995) 229-\r\n244.\r\n[8] A. Dasdan, S. S. Irani and R. K. Gupta, \"An Experimental Study of\r\nMinimum Mean Cycle Algorithms\", UCI-ICS TR #98-32, UIUC,\r\nUrbana, USA.\r\n[9] M. N. S. Swamy, and K. Thulasiraman, \"Graphs, networks, and\r\nalgorithms,\" John Wiley & Sons, Inc., New York, 1981.","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 10, 2007"}