Loading article…
ループアンローリング（ループアンワインディングとも呼ばれる）は、プログラムの実行速度をバイナリサイズを犠牲にして最適化しようとするループ変換技術であり、空間時間トレードオフとして知られるアプローチです 。この変換は、プログラマが手動で行うことも、最適化コンパイラによって行うこともできます。最新のプロセッサでは、コードサイズの増加によりキャッシュミスが増加する可能性があるため、ループアンローリングはしばしば逆効果になります。ダフのデバイスを参照してください。[ 1 ]
ループアンワインディングの目的は、ポインタ演算や各イテレーションでの「ループ終了」テストなど、ループを制御する命令を削減または排除することによってプログラムの速度を向上させることです。[ 2 ]分岐ペナルティを削減し、メモリからのデータ読み取りの遅延などのレイテンシを隠蔽します。[ 3 ]この計算オーバーヘッドを排除するために、ループは類似した独立したステートメントの繰り返しシーケンスとして書き直すことができます。[ 4 ]
ループ展開は、特定の形式検証手法、特に境界付きモデル検査の一部でもある。[ 5 ]
タイトなループにおけるオーバーヘッドは、配列内の次の要素へのポインタまたはインデックスをインクリメントする命令（ポインタ演算）や、「ループ終了」判定などで構成されることが多い。最適化コンパイラまたはアセンブラが、個別に参照される各配列変数へのオフセットを事前に計算できる場合、これらのオフセットをマシンコード命令に直接組み込むことができるため、実行時に追加の算術演算は不要となる。
最適化コンパイラは、アンローリングを自動的に実行する場合もあれば、要求に応じて実行する場合もあります。
手動（または静的）ループ展開では、プログラマがループを分析し、反復処理をループのオーバーヘッドを削減する一連の命令に解釈します。これは、コンパイラによって実行される動的ループ展開とは対照的です。
コンピュータプログラムにおいて、コレクションから100個の項目を削除する処理があります。これは通常、remove(item_number)for関数を呼び出すループによって行われます。プログラムのこの部分を最適化する必要があり、ループのオーバーヘッドがremove(x)関数に比べて大きなリソースを必要とする場合、アンワインディングを使用して処理速度を向上させることができます。
この変更により、新しいプログラムは100回ではなく20回の反復で済むようになります。その後、ジャンプと条件分岐の実行回数は全体の20%に減り、多くの反復処理において、ループ管理のオーバーヘッドを大幅に削減できる可能性があります。最適な効果を得るには、展開されたコード内でポインタ演算を必要とする変数を指定しないようにする必要があります。これは通常、インデックス参照ではなく、「ベースアドレス＋オフセットアドレス」によるアドレス指定を必要とします。
一方、この手動ループ展開では、ソースコードのサイズが 3 行から 7 行に拡張され、生成、チェック、デバッグが必要になります。また、コンパイラは拡張されたループ反復で変数を格納するために、より多くのレジスタを割り当てる必要がある場合があります。さらに、展開されたループ構造内のループ制御変数と操作の数は、結果が元のコードと同じになるように慎重に選択する必要があります (既に動作しているコードに対する後からの最適化であると仮定した場合)。たとえば、反復回数が 5 で割り切れない場合の影響を考えてみてください。テスト条件が変数である場合、必要な手動修正もやや複雑になります。Duffのデバイスも参照してください。
単純なケースでは、ループ制御は単に生産的なステートメントを配置するための管理上のオーバーヘッドにすぎません。ループ自体は望ましい結果に何ら貢献せず、プリプロセッサやテキストエディタが複製を生成できたはずのコードを100回も複製するというプログラマの面倒な作業を省くだけです。同様に、if-ステートメントやその他のフロー制御ステートメントもコードの複製に置き換えることができますが、その結果としてコードが肥大化する可能性があります。コンピュータプログラムは組み合わせを容易に追跡できますが、プログラマはこの繰り返しを退屈に感じ、ミスを犯します。以下を考えてみてください。
しかしもちろん、実行されるコードはプロシージャの呼び出しである必要はなく、次の例では計算にインデックス変数が関係します。
コンパイルすると大量のコードが生成される可能性がある（print文は特に有名）が、さらなる最適化が可能である。この例では、ループ内でx(i)とx(i-1)のみを参照している（後者は新しい値x(i)を生成するためのみ）。したがって、ここで生成された配列xへの後続の参照がないことを考慮すると、その使用箇所を単純な変数に置き換えることができる。ただし、このような変更は、値が変化する単純な変数を意味する。一方、配列をそのまま使用する場合、コンパイラの分析では、配列の値が定数であり、それぞれが前の定数から派生していることに気づき、定数値を引き継ぐため、コードは次のようになる。
2、2を印刷します。 3、6を印刷する。 4、24を印刷する。 ...等。
一般的に、ループの内容は複雑で配列のインデックス付けを伴う場合が多く、大規模になる可能性があります。このようなケースは、最適化コンパイラによる展開に任せるのがおそらく最善でしょう。最も内側のループを複製することで、多くの最適化が可能になりますが、n が大きい場合を除き、得られる効果はわずかです。
次のような擬似コードのWHILEループを考えてみましょう。
この場合、ENDWHILE（ループの先頭へのジャンプ）の実行頻度が66%少なくなるため、アンローリングの方が高速になります。
さらに良いのは、一部の最適化コンパイラによって自動的に実行される可能性のある「微調整された」擬似コードの例であり、無条件ジャンプを完全に排除します。
ループ展開の利点は配列のサイズに依存することが多く、そのサイズは実行時まで分からない場合が多いため、JITコンパイラ（例えば）は、「標準」ループシーケンスを呼び出すか、各要素に対して（比較的短い）個別の命令シーケンスを生成するかを判断できます。この柔軟性は、ループ展開の文脈において、静的最適化や手動最適化と比較したジャストインタイム方式の利点の1つです。この場合、nの値が比較的小さい場合に、依然として節約効果が有効であり、プログラム全体のサイズ増加はごくわずか（あるいは全くない）で済みます（標準ライブラリの一部として一度だけ含めるだけで済む場合もあります）。
アセンブリ言語プログラマ（最適化コンパイラ開発者を含む）も、効率的な分岐テーブルと同様の方法を用いて、動的ループ展開の技術から恩恵を受けることができます。ここで最も効果的なのは、特定の配列内の参照されるフィールドの最大オフセットが、マシン命令で指定できる最大オフセットよりも小さい場合です（このオフセットを超えると、アセンブラによって警告が表示されます）。
この例は、IBM/360またはZ/Architectureアセンブラ向けで、配列FROMから配列TOへ、 100 バイトのフィールド (オフセット 0 の位置) をコピーすることを想定しています。どちらの配列も、要素長が 256 バイトのエントリが 50 個あります。
* 返送先住所はR14に記載されています。 * レジスタ R15、R0、R1、R2 を、末尾で定義されたデータから初期化します。 * ラベル INIT/MAXM1 で始まるプログラム。 LM R15,R2,INIT R15 を MVC の最大数に設定します * 命令 (MAXM1 = 16) * R0 = 配列のエントリ数、 * R1 = 'FROM'配列のアドレス、 * R2 = 'TO'配列のアドレス。 * * ループはここから始まります。 LOOP EQU * LOOP ラベルを定義します。 * この時点で、R15 には常に数値 16 (MAXM1) が含まれます。 SR R15、R0 残りの数を引きます * R15から配列(R0)のエントリ。 BNP ALL R15が正でない場合、つまり * 残りエントリー数が16件以上 * 配列内で、全体をジャンプします * MVCシーケンスを実行し、その後繰り返します。 * * 無条件分岐のためのオフセット（MVCシーケンスの開始位置から）を計算します。 * 以下に示す「展開された」MVCループ。 * 配列の残りのエントリ数がゼロの場合、R15 は 16 になります。 * すべてのMVC命令はスキップされます。 MH R15,=AL2(ILEN) R15に1の長さを掛けます * MVC命令。 B ALL(R15) ALL+R15 にジャンプします。 * 特定のMVC命令を計算しました * 残りのものにもドロップスルーされます。 * * MVC命令「table」。 * 最初のエントリは、単一レジスタで許容される最大オフセットが16進数F00です。 この例では、* (15*256) となります。 * 以下の 16 個の MVC (「文字の移動」) 命令はすべて、ベース + オフセットを使用します * アドレス指定と各to/fromオフセットは、配列要素1つ分の長さだけ減少します。 * (256)。これにより、各要素に対してポインタ演算が不要になります。 * 16進数FFF命令内の最大許容オフセット * (15*256+255)。命令はオフセットの降順なので、最後の * セット内の要素が最初に移動されます。 ALL MVC 15*256(100,R2),15*256(R1) 16 番目のエントリの 100 バイトを移動します * 配列 1 から配列 2 へ ( * ドロップスルー）。 ILEN EQU *-ALL ILEN を前の文字列の長さに設定します * MVC命令。 MVC 14*256(100,R2),14*256(R1) 15 番目のエントリの 100 バイトを移動します。 MVC 13*256(100,R2),13*256(R1) 14 番目のエントリの 100 バイトを移動します。 MVC 12*256(100,R2),12*256(R1) 13 番目のエントリの 100 バイトを移動します。 MVC 11*256(100,R2),11*256(R1) 12 番目のエントリの 100 バイトを移動します。 MVC 10*256(100,R2),10*256(R1) 11 番目のエントリの 100 バイトを移動します。 MVC 09*256(100,R2),09*256(R1) 10 番目のエントリの 100 バイトを移動します。 MVC 08*256(100,R2),08*256(R1) 9番目のエントリの100バイトを移動します。 MVC 07*256(100,R2),07*256(R1) 8番目のエントリの100バイトを移動します。 MVC 06*256(100,R2),06*256(R1) 7 番目のエントリの 100 バイトを移動します。 MVC 05*256(100,R2),05*256(R1) 6 番目のエントリの 100 バイトを移動します。 MVC 04*256(100,R2),04*256(R1) 5番目のエントリの100バイトを移動します。 MVC 03*256(100,R2),03*256(R1) 4 番目のエントリの 100 バイトを移動します。 MVC 02*256(100,R2),02*256(R1) 3番目のエントリの100バイトを移動します。 MVC 01*256(100,R2),01*256(R1) 2番目のエントリの100バイトを移動します。 MVC 00*256(100,R2),00*256(R1) 最初のエントリの100バイトを移動します。 * S R0、MAXM1 残りのエントリ数を減らす * 処理する。 BNPR R14 処理するエントリがなくなったら、返します * R14で対処する。 AH R1,=AL2(16*256) 'FROM'配列ポインタをインクリメントします * 最初のセット。 AH R2,=AL2(16*256) 'TO'配列ポインタをインクリメントします * 最初のセット。 L R15、MAXM1 MVCの最大数をリロードします * R15へのバッチごとの指示 * (計算によって破壊されました) * ループの最初の命令)。 B ループ ループを再度実行します。 * * 静的定数と変数（これらはパラメータとして渡すことができますが、 * MAXM1) INIT DS 0A 4 アドレス (ポインタ) * 「LM」命令がプリロードされています * プログラムの冒頭で。 MAXM1 DC A(16) MVC命令の最大数 * バッチごとに実行されます。 N DC A(50) 配列内の実際のエントリ数 (a * 変数、別の場所で設定。 DC A(FROM) 配列1の開始アドレス *（「ポインタ」）。 DC A(TO) アレイ2の開始アドレス *（「ポインタ」）。 * * 静的配列（これらは動的に取得することも可能です）。 FROM DS 50CL256 配列。各エントリは256バイトで、エントリ数は50個です。 TO DS 50CL256 256バイトのエントリが50個含まれる配列。 この例では、「従来型」ループ（50回繰り返し）では約202命令が必要ですが、上記の動的コードでは約89命令（約56%の削減）で済みます。配列のエントリが2つだけだった場合でも、元の展開ループとほぼ同じ時間で実行されます。配列に数千のエントリがあっても、コードサイズの増加は約108バイトに過ぎません。
もちろん、複数の命令が関係する場合にも同様の手法を使用できますが、その場合は結合された命令の長さを適切に調整する必要があります。たとえば、この例では、コピーされた 100 バイトのフィールドの直後に各配列エントリの残りを null にクリアする必要がある場合、シーケンス内のすべての MVC の直後にクリア命令 を追加できます ( は、その上の MVC の値と一致します)。XC xx*256+100(156,R1),xx*256+100(R2)xx
もちろん、単一のアセンブラマクロステートメントを使用して上記のコードを「インライン」で生成し、4つか5つのオペランドを指定するだけで（あるいは、単純な呼び出しでアクセスし、パラメータのリストを渡すライブラリサブルーチンにすることもできます）、最適化を容易に利用できるようにすることが可能です。
次の例は、 C言語で記述された単純なプログラムにおける動的ループ展開を示しています。上記のアセンブリ言語の例とは異なり、この例では変数(i)が配列要素のアドレス指定に使用されているため、ポインタ/インデックス演算はコンパイラによって生成されます。完全な最適化は、置換文で絶対インデックスが使用されている場合にのみ可能です。
#include <stdio.h>// ループの反復ごとに処理されるエントリの数。// この数値は、以下のコードを反映した「定数」であることに注意してください。constexpr int BUNCHSIZE = 8int main ( void ) { int i = 0 ; // カウンタint entries = 50 ; // 処理する要素の総数// 要素数が BUNCHSIZE で割り切れない場合、// while ループでほとんどの処理を実行するために必要な繰り返し回数を取得しますint repeat = ( entries / BUNCHSIZE ); // 繰り返し回数int left = ( entries % BUNCHSIZE ); // 余りを計算// ループを 8 個の「束」で展開しますwhile ( repeat -- ) { printf ( "process(%d) \n " , i ); printf ( "process(%d) \n " , i + 1 ); printf ( "process(%d) \n " , i + 2 ); printf ( "process(%d) \n " , i + 3 ); printf ( "process(%d) \n " , i + 4 ); printf ( "process(%d) \n " , i + 5 ); printf ( "process(%d) \n " , i + 6 ); printf ( "process(%d) \n " , i + 7 );// 一度に処理した量でインデックスを更新するi += BUNCHSIZE ; }// switch文を使用して、残りのケースラベルにジャンプし、そのラベルでドロップスルーしてセットを完了しますswitch ( left ) { case 7 : printf ( "process(%d) \n " , i + 6 ); // 処理してドロップスルーに依存case 6 : printf ( "process(%d) \n " , i + 5 ); case 5 : printf ( "process(%d) \n " , i + 4 ); case 4 : printf ( "process(%d) \n " , i + 3 ); case 3 : printf ( "process(%d) \n " , i + 2 ); case 2 : printf ( "process(%d) \n " , i + 1 ); // 残り2つcase 1 : printf ( "process(%d) \n " , i ); // 処理すべき残り1つcase 0 : break ; // 残りなし} }コードの重複は、ダフの装置のように2つの部分を一緒に記述することで回避できる。
出典: [ 9 ]
次の例では、100個の要素を持つ2つのベクトルAとB（型）の内積doubleを計算します。C言語のコードは以下のとおりです。
double dotProduct = 0 ;for ( int i = 0 ; i < 100 ; i ++ ) {dotProduct += A [ i ] * B [ i ];}以下は、ループ展開を実行する前に、100個の要素を持つ2つのベクトルAとBの内積を計算するMIPSアセンブリコードです。以下のコードでは、ループの初期化は省略されています。
A[i]のベースアドレスへのポインタ（$5）を初期化しますA。B[i]のベースアドレスへのポインタ（$6）を初期化しますB。 配列の要素 (a) のサイズはdouble8 バイトであることに注意してください。
ループ3:ld $f10 , 0 ( $5 ) ; $f10 ← A[i]ld $f12 、0 ( $6 ) ; $f12 ← B[i]mul.d $f10 、$f10 、$f12 ; $f10 ← A[i]*B[i]add.d $f8 , $f8 , $f10 ; $f8 ← $f8 + A[i]*B[i]addi $5 , $5 , 8 ; A[i] のポインタをサイズ分インクリメントする二重の。addi $6 , $6 , 8 ; B[i] のポインタをサイズ分インクリメントする二重の。addi $7 , $7 , -1 ; ループ回数をデクリメントするテスト：bgtz $7 、loop3 ; ループ回数が 0 より大きい場合は続行する 以下は上記と同じですが、ループ展開を4倍の係数で実装しています。配列の1つの要素（a double）のサイズは8バイトであることに注意してください。したがって、各ループで0、8、16、24、および32の変位が発生します。
ループ3:ld $f10 , 0 ( $5 ) ; 変位0での反復ld $f12 、0 ( $6 )mul.d $f10 、$f10 、$f12add.d $f8 、$f8 、$f10ld $f10 , 8 ( $5 ) ; 変位8での反復ld $f12 、8 ( $6 )mul.d $f10 、$f10 、$f12add.d $f8 、$f8 、$f10ld $f10 , 16 ( $5 ) ; 変位16での反復ld $f12 、16 ( $6 )mul.d $f10 、$f10 、$f12add.d $f8 、$f8 、$f10ld $f10 , 24 ( $5 ) ; 変位24での反復ld $f12 、24 ( $6 )mul.d $f10 、$f10 、$f12add.d $f8 、$f8 、$f10addi $ 5 、$ 5、32addi $ 6 、$ 6、32addi $7 、$7 、-4テスト：bgtz $7 、loop3 ; $7 > 0 の場合、ループを続行するJim Gettys は、X サーバーにおけるこの効果について素晴らしい説明をしています。過去 10 年間で分岐予測と CPU とメモリの相対速度が変化したため、ループ アンローリングはほとんど意味がないことがわかりました。実際、XFree86 4.0 サーバーから Duff のデバイスをすべて削除することで、サーバーのサイズが _0.5_ _1_ _メガバイト_ (!!!) 縮小し、余分なコードをすべて削除したことで X サーバーがキャッシュ ラインをそれほど激しく使用しなくなったため、起動が速くなりました。
{{cite book}}: CS1 maint: 複数の名前: 著者リスト (リンク){{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）12.11 ループ展開