Extended retiming: Optimal scheduling via a graph-theoretical approach

Many iterative or recursive applications commonly found in DSP and image processing applications can be represented by data-flow graphs (DFGs). This graph is then used to perform DFG scheduling, where the starting times for executing the application's individual tasks are determined. The minimum length of time required to execute all tasks once is called the schedule length of the DFG. 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 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 and propose a new graph-transformation technique, extended retiming, which will. We will also present an algorithm for finding an extended retiming which transforms a DFG into one with minimal schedule length. Finally, we will demonstrate a constant-time algorithm which verifies the existence of a retimed DFG with the minimum schedule length.