Exact and efficient advanced loop interchange

Chu Sing Yang, Chien Chih Chang, Jenn Ming Yang, Tsung Chuan Huang, K. C. Huang

Research output: Contribution to journalArticlepeer-review


Loop interchange is a transformation that exchanges two level of a nested loop for getting maximum performance in a target parallel computer. Loop interchange also is a powerful tool which can be used in a variety of ways to support parallelism. This paper proposed an improved loop interchange algorithm that can determine whether two arbitrary level of loops can be interchanged each other without invalid the data dependence. Conventional loop interchange considered by direction vector, they are constrained only on adjacent loop which lack of efficiency and accuracy. The algorithm is modified by a convinient direction vector that extends the loop interchange to arbitrary level, it has more efficiency and accuracy than previous approaches. We also derived an inequality with which to perform loop interchange by checking their bonds. Finally, interchange of imperfectly nested loop is also discussed, while most of loop interchange studies constrained only on perfectly loop that doesn't meet all conditions in coding program, and some previous approaches that used loop distribution and regular loop interchange to solve imperfect loop, they are still lack of accuracy and efficiency, we have an algorithm to address these problems.

Original languageEnglish
Pages (from-to)421-428
Number of pages8
JournalMicroprocessing and Microprogramming
Issue number1-5
Publication statusPublished - 1993 Sep

All Science Journal Classification (ASJC) codes

  • Engineering(all)


Dive into the research topics of 'Exact and efficient advanced loop interchange'. Together they form a unique fingerprint.

Cite this