循环交换（一）——基本概念

交换紧嵌套中两个循环的嵌套顺序&＃xff08;提高程序性能最有效的变换之一&＃xff09;。例如&＃xff1a;

1Do I &＃61; 1,N
2   Do J &＃61; 1,M
3      A(I,J&＃43;1) &＃61; A(I,J) &＃43; B
4   ENDDO
5ENDDO

此例子中最内层语句3存在内层循环携带依赖。无法按向量代码生成算法codegen作向量化。

但是交换这两层循环&＃xff0c;如

1Do J &＃61; 1,M
2   Do I &＃61; 1,N
3      A(I,J&＃43;1) &＃61; A(I,J) &＃43; B
4   ENDDO
5ENDDO

依赖关系变成外层循环&＃xff0c;而内层循环不携带依赖。因此&＃xff0c;内层循环可以被向量化为&＃xff1a;

1Do J &＃61; 1,M
2   A(1:N,J&＃43;1) &＃61; A(1:N,J) &＃43; B
3ENDDO

如果把此过程颠倒过来&＃xff0c;变成内层并行循环移动到最外层以增加并行粒度和减少同步开销。

结论&＃xff1a;循环变换实际上是一种重排序交换&＃xff0c;可以把循环看成所包含语句的一系列参数化实例。循环变换就是改变这些参数化实例的执行顺序&＃xff0c;但并没有产生任何新的实例。

在以下的代码中令S(I,J)表示参数为I,J的语句S的实例。换句话说&＃xff0c;S(I,J)是语句S在迭代向量为&＃xff08;I,J&＃xff09;的迭代中执行时的实例。

1DO J &＃61; 1,M
2   DO I &＃61; 1,N
3      S
4   ENDDO
5ENDDO

使用这种记法&＃xff0c;在此代码中S&＃xff08;1&＃xff0c;2&＃xff09;在S&＃xff08;2&＃xff0c;1&＃xff09;之后执行&＃xff0c;但是在循环变换后&＃xff0c;它变成在S&＃xff08;2&＃xff0c;1&＃xff09;之前执行。

循环变换实际上是重排序变换。因为是重排序变换&＃xff0c;故其合法性可以通过数据依赖关系判定。