Optimal scheduling of data-flow graphs using extended retiming

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 vari-ous graph transformation techniques to the DFG in order to mini-mize the schedule length. One of the most effective of these tech-niques is retiming. In this paper, we demonstrate that the tradi-tional retiming technique does not always achieve optimal sched-ules (although it can be used in combination with other techniques to do so) and propose a new graph-transformation technique, ex-tended retiming, which will