Retiming synchronous data-flow graphs to reduce execution time

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 to expres and study SDFGs. We review the problems faced when attempting to retime an SDFG in order to minimize clock period and then present algorithms for doing this. Finally, we demonstrate the effectiveness of our methods on several examples.