Exact and efficient advanced loop interchange

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.