Loop-carried dependence and the general URPR software pipelining approach [unrolling, pipelining and rerolling]

This paper first theoretically analyzes the influence of loop-carried dependence on software pipelining. It then defines two loop categories: restrictable and unrestrictable loops, puts forward and proves a sufficient and necessary condition for distinguishing the two kinds of loops. This condition is related with the number of operation pairs with loop-carried dependence, the execution time of operations, and other loop parameters. Next, this paper proves that any unrestrictable loop can be transformed into a semantically equivalent restrictable loop by unrolling K times. K is determined by the number of operation pairs with loop-carried dependence within the original unrestrictable loop. Finally, the paper presents a general URPR software pipelining approach which consists of a pre-processing algorithm, a new compaction algorithm for a loop body and a URPR algorithm. Preliminary experiments show that the general URPR can guarantee a time-optimal result for any loop in the absence of resource constraints and still keep good space efficiency and low complexity