"Optimal Graph Transformation using Extended Retiming with Minimal Unfolding"

( by Timothy W. O'Neil , and Edwin H.-M. Sha) in the Proceedings of the IASTED International Conference Parallel and Distributed Computing and Systems, November, 1999, Cambridge, MA, pp. 764-769.



  Many computation-intensive iterative or recursive applications commonly found in digital signal processing and image processing applications can be represented by data-flow graphs (DFGs). The execution of all tasks of a DFG is called an iteration, with the average computation time of an iteration the iteration period. A great deal of research has been done attempting to optimize such applications by applying various graph transformation techniques to the DFG in order to minimize this iteration period. Two of the most popular are retiming and unfolding, which can be performed in tandem to achieve an optimal iteration period. However, the result is a transformed graph which is much larger than the original DFG. In our previous work, we proposed a new technique, extended retiming, which can be combined with minimal unfolding to transform a DFG into one whose iteration period matches that of the optimal schedule under a pipelined design. In this paper, we augment our previous work by designing an efficient retiming algorithm which may be applied directly to a DFG instead of the larger unfolded graph.


[ Published listings ] [ Top ]