Lf. Chao et al., ROTATION SCHEDULING - A LOOP PIPELINING ALGORITHM, IEEE transactions on computer-aided design of integrated circuits and systems, 16(3), 1997, pp. 229-239
We consider the resource-constrained scheduling of loops with interite
ration dependencies. A loop is modeled as a data flow graph (DFG), whe
re edges are labeled with the number of iterations between dependencie
s. We design a novel and flexible technique, called rotation schedulin
g, for scheduling cyclic DFG's using loop pipelining. The rotation tec
hnique repeatedly transforms a schedule to a more compact schedule. We
provide a theoretical basis for the operations based on retiming. We
propose two heuristics to perform rotation scheduling and give experim
ental results showing that they have very good performance.