Special-Case Techniques for the Efficient Computation of the Iteration-Period Bound in Multirate Data-Flow Graphs
Sabih H. Gerez, M.L.M. Jong, Sonia Heemstra de Groot · University of Twente Research Information · 1995
A multirate synchronous data-flow graph, in which nodes operate at distinct speeds, has a single-rate equivalent in which all nodes operate at the same speed. In order to find the fastest implementation of the graph, one needs to know the graph's iteration-period bound. It is well-known how to compute it after expanding the graph to its single-rate equivalent. However, the single-rate equivalent can be considerably larger than the original graph. In this paper, a method is presented for the construction of a reduced graph that has all relevant properties of the single-rate equivalent, but is much smaller in general. It can be proven that the size of the reduced graph does not depend on the relative speeds of the nodes in the original graph and grows as a polynomial function of the original graph's size. The presented method is limited to graphs without selfloops. 1 Introduction Synchronous data-flow graphs [12] are widely accepted for the representation of digital signal processing al...