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 schedul-ing, where the starting times for executing the application’s in-dividual tasks are determined. The minimum length of time re-quired to execute all tasks once is called the schedule length of the DFG. A great deal of research has been done attempting to opti-mize 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. 1