ループインターチェンジ

コンパイラ理論では、ループ交換とは、ネストされたループで使用される 2 つの反復変数の順序を交換するプロセスです。内側のループで使用される変数は外側のループに切り替わり、その逆も同様です。これは、多次元配列の要素がメモリ内に存在する順序でアクセスされるようにするためによく行われ、参照の局所性が向上します。

たとえば、次のコード フラグメントでは、

jは0から20まで
  iは0から10まで
    a[i,j] = i + j

ループ交換の結果は次のようになります。

iは0から10まで
  jは0から20まで
    a[i,j] = i + j

場合によっては、このような変換により、配列割り当ての 自動ベクトル化など、さらに最適化する機会が生まれることがあります。

ループ交換の主な目的は、配列要素にアクセスするときにCPU キャッシュを活用することです。プロセッサが配列要素に初めてアクセスするとき、メモリからキャッシュにデータ ブロック全体を取得します。そのブロックには最初の要素の後にさらに多くの連続した要素がある可能性が高いため、次の配列要素アクセスでは、キャッシュから直接取得されます (低速のメイン メモリから取得するよりも高速です)。ループ内で連続してアクセスされる配列要素が異なるキャッシュ ブロックからのものである場合、キャッシュ ミスが発生しますが、ループ交換はこれを防ぐのに役立ちます。ループ交換の有効性は、基盤となるハードウェアで使用されるキャッシュ モデルとコンパイラで使用される配列モデルに依存し、それらを考慮して検討する必要があります。

C言語では、同じ行にある配列要素はメモリ内に連続して格納されます(a[1,1]、a[1,2]、a[1,3]) 。つまり、行優先順序です。一方、FORTRANプログラムは、同じ列の配列要素をまとめて格納します(a[1,1]、a[2,1]、a[3,1]) 。したがって、最初の例の2つの反復変数の順序はCプログラムに適しており、2番目の例はFORTRANに適しています。^[1]最適化コンパイラは、プログラマによる不適切な順序付けを検出し、順序を交換してキャッシュパフォーマンスを向上させることができます。

キャッシュ パフォーマンスは全体の一部に過ぎないため、ループ交換によってパフォーマンスが低下する可能性があります。次の例をご覧ください。

 i = 1 , 10000を実行しますj = 1 , 1000 a [ i ] = a [ i ] + b [ j , i ] * c [ i ]を実行します終了します   
      
           
   

この例のループ交換により、b(j,i) にアクセスするキャッシュ パフォーマンスが向上しますが、各反復中に 2 つの余分なロード (a(i) と c(i)) と 1 つの余分なストア (a(i)) が導入されるため、内側のループでの a(i) と c(i) の再利用が台無しになります。その結果、ループ交換後に全体的なパフォーマンスが低下する可能性があります。

実行順序に関するステートメント間の依存関係のため、反復変数を交換することは必ずしも安全ではありません。コンパイラがループを安全に交換できるかどうかを判断するには、依存関係の分析が必要です。

• ループ分割
• ループの傾斜
• ループ核分裂と核融合
• ループ展開

• Kennedy, Ken、Allen, Randy (2002)。『現代アーキテクチャのためのコンパイラの最適化:依存関係ベースのアプローチ』 (2011 年第 1 版デジタル印刷)。Academic Press / Morgan Kaufmann Publishers / Elsevier。ISBN 978-1-55860-286-1LCCN  2001092381 。