"Optimal Scheduling of Data-Flow Graphs Using Extended Retiming"

(by T. O'Neil, S. Tongsima, and E. H.-M. Sha) in Proceedings of the ISCA 12th International Conference on Parallel and Distributed Computing Systems, Fort Lauderdale, Florida, August, 1999, pp. 292-297.



  Many iterative or recursive applications commonly found in DSP and image processing applications can be represented by data-flow graphs (DFGs). A great deal of research has been done attempting to optimize such applications by applying various graph transformations techniques to the DFG to minimize the schedule length. One of the most effective of these techniques is retiming. In this paper, we demonstrate that the traditional retiming technique does not always achieve optimal schedules (although it can be used in combination with other techniques to do so) and propose a new graph transformation technique, extended-retiming, which will.


[ Published listings ] [ Top ]