"Parallelizing Synchronous Data-Flow Graphs via Retiming"

(by T. O'Neil, S. Tongsima, and E. H.-M. Sha) in the Proceedings of the 4th International Conference on Algorithms and Architectures for Parallel Processing, Hong Kong, December, 2000, pp. 252-263.



  Many common iterative or recursive DSP applications can be represented by synchronous data-flow graphs (SDFGs). A great deal of research has been done attempting to optimize such applications through retiming. However, despite its proven effectiveness in transforming single-rate data-flow graphs to equivalent DFGs with smaller clock periods, the use of retiming for attempting to reduce the execution time of synchronous DFGs has never been explored. In this paper, we do just this. We develop the basic definitions and results necessary for expressing and studying SDFGs. We review the problems faced when attempting to retime a SDFG in order to minimize clock period, then present an algorithm for doing this. Finally, we demonstrate the effectiveness of our method on several examples.


[ Published listings ] [ Top ]