循环体间相关问题及改进的URPR软件流水方法

LOOP-CARRIED DEPENDENCE AND THE IMPROVED URPR SOFTWARE PIPELINING APPROACH

本文首先在理论上分析了循环体间相关对软件流水的影响.提出了一个由循环本身性质决定的充分必要条件并证明了满足此条件的循环是可限制的,否则是不可限制的;其次我们证明了任意不可限制的循环展开K次后即可转换为可限制循环,K取决于循环本身的性质;最后给出了循环预处理算法和一个新的循环体压缩算法.实验结果表明,这两个算法可使URPR算法对任意循环都能得到最优时间效益并保持了良好的空间效益及低的计算复杂性.

This paper first theoretically analyzes the influence of loop-carried dependen-ce on software pipelining, puts forward and proves a sufficient and necessary condition for distinguishing the two kinds of loops-restrictable and unrestrictable. Next, it 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, a pre-processing algorithm and a new compaction algorithm for loop bodies are presented. The preliminary experimtnts show that with these two algorithms URPR can guarantee time optimal result for any loop in the absence of resource constraints and still keep the good space efficiency and low time complexity.