RCRS: A framework for loop scheduling with limited number of registers

Many real time applications such as multimedia and DSP systems terms require high throughput, so it is necessary to have special purpose designs for them. Loop pipelining is an effective approach to reduce the total execution time of loops. While most previous research concentrates on the scheduling of computation, the experiments show that data access may give significant overhead if the register resource is limited. This paper studies the register constraint problem and presents Register Constrained Rotation Scheduling (RCRS), including the algorithm analyzing the number of required registers for loops and two classes of algorithms based on different assumptions. The first class is for loop scheduling with a given number of registers. If the number of registers is too stringent, the second class of algorithms are applied by inserting necessary LOAD/STORE operations into the loop schedule. Through the series of experiments, the RCRS algorithms are shown to achieve near optimal schedule length while satisfying register constraints.