ループ最適化

コンパイラ理論において、ループ最適化とは、ループの実行速度を向上させ、ループに伴うオーバーヘッドを削減するプロセスです。キャッシュ性能の向上や並列処理機能の有効活用において重要な役割を果たします。科学計算プログラムの実行時間の大部分はループ処理に費やされるため、ループ処理を高速化するためのコンパイラ最適化手法が数多く開発されてきました。

ループ内の命令は繰り返し実行される可能性があるため、ループ最適化によって影響を受ける命令実行回数の上限を設定することはしばしば不可能です。これは、ループ最適化の正当性と利点、特に最適化される計算の表現と実行される最適化について推論する際に課題となります。^{[ 1 ]}

ループ最適化は、ソースコードまたは中間表現に対して、特定のループ変換のシーケンス（以下、または高性能コンピューティングのためのコンパイラ変換^{[ 2 ]}に記載）を適用することと見なすことができ、各変換には正当性を確認するためのテストが関連付けられています。変換（または変換のシーケンス）は、プログラムの結果を保持するため（つまり、正当な変換であるため）には、一般的にすべての依存関係の時間的シーケンスを保持する必要があります。このアプローチでは、変換または変換のシーケンスの利点を評価することは非常に困難です。なぜなら、有益な変換を適用するには、それ自体ではパフォーマンスが低下するような、1つ以上の他の変換を事前に使用する必要がある場合があるからです。

一般的なループ変換には以下が含まれます。

• ループの分割または分散 – ループの分割は、同じインデックス範囲でループを複数のループに分割しようとしますが、各新しいループは元のループ本体の一部のみを使用します。これにより、ループ内でアクセスされるデータとループ本体内のコードの両方の参照の局所性を向上させることができます。
• 融合または結合 – これは、コンパイル時にその回数がわかっているかどうかに関わらず、互いのデータを参照しない限り、同じ回数だけ反復する隣接する 2 つのループの本体を結合します。
• 交換または順列 – これらの最適化では、内側のループと外側のループを交換します。ループ変数が配列のインデックスである場合、このような変換は、配列のレイアウトに応じて、参照の局所性を向上させることができます。
• 反転– この手法では、標準的なwhileループを、if条件で囲まれたdo/while (別名repeat/until ) ループに変更します。これにより、ループが実行されるケースでのジャンプ回数が 2 回削減されます。この方法では条件チェックが重複するためコードのサイズは大きくなりますが、ジャンプは通常パイプラインの停止を引き起こすため、より効率的です。さらに、コンパイル時に初期条件が既知であり、副作用がないことがわかっている場合は、最初のifガードをスキップできます。
• ループ不変コードの移動– ループ内からループ外へ計算を移動させ、ループ開始前に一度だけ値を計算することで、効率を大幅に向上させることができます。ただし、計算結果の値がループの各反復で同じ値になる場合（つまり、ループ不変量である場合）に限ります。これは、配列に対するループによって生成されるアドレス計算式において特に重要です。正しく実装するには、この手法を反転と組み合わせて使用​​する必要があります。なぜなら、すべてのコードがループ外に移動しても安全とは限らないからです。
• 並列化とは、ループに焦点を当て、マルチプロセッサシステム上で効率的に実行できるようにループを再構築する、自動並列化の特殊なケースです。これはコンパイラによって自動的に行われる場合（自動並列化）と、手動で行われる場合（ OpenMPなどの並列ディレクティブを挿入する）があります。
• 反転– インデックス変数に値を割り当てる順序を反転させる微妙な最適化。これにより依存関係を排除し、他の最適化が可能になります。特定のアーキテクチャでは、アセンブリレベルで一方向のみをカウントするループ構造を使用します(例: decrement-jump-if-not-zero [DJNZ] ^{[ 3 ]} )。
• スケジューリングとは、ループを複数の部分に分割し、それらを複数のプロセッサで同時に実行できるようにする処理です。
• スキューイング– この手法は、多次元配列を反復処理するネストされたループに適用され、内側のループの各反復処理が前の反復処理に依存し、配列へのアクセスを再配置することで、依存関係が外側のループの反復処理間のみになるようにします。
• ソフトウェアパイプライン処理とは、プロセッサの機能ユニットの遅延を隠蔽するために、ループ反復処理を順不同で実行する手法の一種である。
• 分割または剥離とは、ループを複数のループに分割することで、ループを簡略化したり、依存関係を解消したりする手法です。分割されたループは、同じ本体を持ちながら、インデックス範囲の異なる部分を反復処理します。特殊なケースとしてループ剥離があり、これは最初の反復処理に問題があるループを、ループに入る前にその反復処理を個別に実行することで簡略化できます。
• タイリングまたはブロッキングとは、キャッシュに収まるサイズのデータ​​ブロックを反復処理するようにループを再編成することです。
• ベクトル化とは、 SIMDシステム上で可能な限り多くのループ反復処理を同時に実行しようとする試みである。
• ループの展開とは、ループ条件のテスト回数とジャンプ回数を減らすために、ループ本体を複数回複製することです。ジャンプ回数は、命令パイプラインに悪影響を与え、パフォーマンスを低下させる可能性があります。ループを完全に展開すると、オーバーヘッドはすべて解消されます（ただし、複数の命令フェッチとプログラムロード時間の増加は除きます）。ただし、コンパイル時に反復回数が既知である必要があります（ジャストインタイムコンパイルの場合を除く）。また、インデックス付き変数の複数回の再計算が、元のループ内でポインタを進めるよりも大きなオーバーヘッドにならないように注意する必要があります。
• アンスイッチングとは、ループ本体を複製し、その複製を条件文のif節とelse節のそれぞれの中に配置することで、条件文をループの内側から外側に移動させる方法です。
• ループセクショニングまたはストリップマイニング –ベクトルプロセッサ向けに導入されたループセクショニングは、ループのSIMD （単一命令複数データ）エンコーディングを可能にし、メモリパフォーマンスを向上させるためのループ変換技術です。これには、各ベクトル演算が、特定のベクトルマシン上の最大ベクトル長以下のサイズで実行されることが含まれます。^{[ 4 ] [ 5 ]}

• ループネストの最適化
• 多面体モデル
• スケーラブルな並列処理
• スケーラブルな地域性