Rotation scheduling
Liang-Fang Chao, Andrea S. LaPaugh · 1993
We consider the resource-constrained scheduling of loops with inter-iteration dependencies.A loop is modeled as a data flow graph (DFG), where edges are labeled with the number oj iterations between dependencies.We design a novel and ji'exible technique, called rotation scheduling, for scheduling cyclic DFGs using loop pipelining.The rotation technique 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 experimental results showing that they have very good performance.