Modeling and Retiming Non-uniform Acyclic Loops

P. Xue, H. Bui, A. Joseph, and N.L. Passos (USA)


Pipelining, Multi-rate, Superscalar, Instruction LevelParallelism, Loop Transformation


New applications involving multi-rate systems, data compression and mathematical series, require high computational power which most of the time implies the use of parallel processing. When the parallelism is associated to superscalar architectures, code optimization must be applied at the instruction level in order to produce the desired performance. These improvements are usually applied to loop constructs due to their recurrence and criticality in the behavior of the application. In this study, the retiming theory is revisited and extended to the case of non-uniform one-dimensional acyclic loops with linear index expressions. A new data flow graph model is proposed in order to identify the possibility of applying retiming to a loop body. The same technique also identifies the constraints on the loop index that make retiming feasible.

Important Links:

Go Back