Schedule-based multi-dimensional retiming on data flow graphs

Transformation techniques are usually applied to get optimal execution rates in parallel and/or pipeline systems. The retiming technique is a common and valuable tool in one-dimensional problems, represented by Data Flow Graphs (DFGs) such as DSP filters, which can maximize the parallelism of a loop body represented by a DFG. Since most scientific or DSP applications are recursive or iterative, to increase the parallelism of the loop body can substantially decrease the overall computation time. This paper develops a novel multi-dimensional retiming technique that considers the final schedule as part of the process. The description and the correctness of our algorithm are presented in the paper.