ROTATION SCHEDULING - A LOOP PIPELINING ALGORITHM

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.