TY - JOUR
T1 - Exact and efficient advanced loop interchange
AU - Yang, Chu Sing
AU - Chang, Chien Chih
AU - Yang, Jenn Ming
AU - Huang, Tsung Chuan
AU - Huang, K. C.
N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.
PY - 1993/9
Y1 - 1993/9
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0027656302&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0027656302&partnerID=8YFLogxK
U2 - 10.1016/0165-6074(93)90177-M
DO - 10.1016/0165-6074(93)90177-M
M3 - Article
AN - SCOPUS:0027656302
VL - 38
SP - 421
EP - 428
JO - Euromicro Newsletter
JF - Euromicro Newsletter
SN - 1383-7621
IS - 1-5
ER -