Transforming Synchronous Data-Flow Graphs to Reduce Execution Time
Timothy W. O’Neil, Samer F. Khasawneh, Michael Richter, Rama Krishna Pullaguntla · Int. J. Comput. Their Appl. · 2011
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 not been extensively explored. In this paper, we continue our work on just this topic. We develop the basic defmitions and results necessary for expressing and studying the static repeating schedules of SDFGs. We then present a new algorithm based on rotation scheduling for retiming an SDFG in order to minimize clock period. Finally, we demonstrate the effectiveness of our methods on several examples.