ループ展開
ループ展開（ループてんかい、英語: Loop Unwinding）は、プログラムのサイズを犠牲に実行速度を最適化する（時間と空間のトレードオフ）、ループ変換と呼ばれる手法の1つである。ループアンローリング（英語: Loop Unrolling）とも呼ぶ。プログラマが手動で行うこともあるし、コンパイラが行うこともある。
ループ展開の目的は、毎回の繰り返しごとに発生する「ループの終了」条件のテストを減少させる（もしくはなくす）事によって、実行速度を向上させることである[1][2]。ループは、ループ自体を制御するためのオーバーヘッドがなくなるように、独立した命令ブロックの連続に書き換えることができる[3]。
利点
[編集]ループのオーバーヘッドは、ポインタまたはインデックスをインクリメントして配列の次の要素を指すための命令群（ポインタ演算）と「ループ終了条件」のテストに由来する。最適化コンパイラなどで配列の個々の要素への参照のためのオフセットを事前に計算でき、それを直接機械語命令列にできるなら、実行時の余分な演算を省くことができる。
- ループ展開によってプログラムが長くなったとしても、それ以上に実質的な実行命令数が削減されれば、全体としては性能が強化される。
- 分岐ペナルティが最小化される[4]。
- ループ内の各文が相互に依存していない場合（すなわち、ループのある周回の結果がその後の周回で必要とされない場合）、それらの文は並列計算できる可能性がある。
- コンパイル時にループ回数（配列要素数）が不明な場合でも、動的ループ展開を実装可能である（Duff's device）。
最適化コンパイラには自動的または要求に応じてループ展開できるものもある。
欠点
[編集]- プログラムのコードサイズが増大するため、組み込みシステムなどメモリ容量が小さい場合は適切でない。
- 命令キャッシュミス回数が増え、性能を低下させることがある。
- 最適化コンパイラは透過的にループ展開するが、展開後のコードは可読性が低下する。
- ループ内の処理が関数呼び出しだった場合、インライン展開を伴ったループ展開はコードが膨大になりすぎて現実的でないことがある。従ってそれら2つの最適化の間にはトレードオフの関係があるともいえる。
- 展開後にどのような最適化が可能かにも依存するが、一時変数用にレジスタを多く必要とする場合は性能が低下する可能性もある[5]。
- 小さく単純なループは別として、ループ本体内に分岐がある場合は再帰呼び出しより遅くなることがある[6]。
静的/手動ループ展開
[編集]人手による（または静的な）ループ展開は、プログラマがループを分析し展開することでループのオーバーヘッドを低減させるものである。一方コンパイラが行うループ展開を動的ループ展開と呼ぶ。
C言語での簡単な例
[編集]あるプログラムの手続きで、データの集合体から100個の要素を削除(delete)する必要があるとする。このため、for ループ内で関数 delete(要素の番号) を呼び出す。この部分を最適化する場合、ループに必要なオーバヘッドがリソースを多大に消費しているなら、ループ展開で性能が向上する。
| 通常のループ | ループ展開後 |
|---|---|
int x;
for (x = 0; x < 100; x++)
{
delete(x);
}
|
int x;
for (x = 0; x < 100; x+=5)
{
delete(x);
delete(x+1);
delete(x+2);
delete(x+3);
delete(x+4);
}
|
この修正の結果、新たなプログラムのループ回数は 100 回から 20 回に削減される。ジャンプ命令と条件付分岐命令の実行回数は5分の1となり、ループそのものの処理にかかる時間は大幅に削減される可能性がある。その効果を最大にするため、展開されたコードではポインタ計算をしないようにすることが重要である。そのため通常はインデックスによる参照からベースとオフセットによる参照に転換する必要がある。
一方、ループ展開によってコードサイズは 3 行から 7 行に増え、コンパイラは展開された部分で必要となる変数を格納するレジスタをさらに必要とすることになる可能性がある。加えて、展開前と展開後で処理結果が同じになるように、ループ変数のループ内での操作は注意深く行わなければならない。例えば、上の例で 6 回ぶんのループを展開した場合、100 は 6 で割り切れないため、展開前と同じ結果を得るには細工が必要となる。また、ループの終了条件が変数だった場合にはさらに問題は複雑化する。Duff's device を参照されたい。
複雑性
[編集]単純なループでは、ループ制御は単なる管理オーバヘッドである。ループ自体は必要な結果に直接貢献することはなく、単にプログラマが同じコードをいくつもコーディングする手間を省くだけである。それだけであれば、コードの複製はプリプロセッサやエディタの機能を使っても実現できる。同様に if 文などの他の制御構造もコードの複製で置き換えることもできるが、結果として滅茶苦茶なコードが出来上がってしまう。プログラムは組み合わせに絶えず注意することができるが、人間は退屈な作業に我慢できず、間違いを犯す。
| 通常のループ | ループ展開後 |
|---|---|
for i:=1:8 do
if i mod 2 = 0 then do_evenstuff(i)
else do_oddstuff(i);
next i;
|
do_oddstuff(1); do_evenstuff(2); do_oddstuff(3); do_evenstuff(4); do_oddstuff(5); do_evenstuff(6); do_oddstuff(7); do_evenstuff(8); |
しかし、もちろん展開される中身は手続き呼び出しである必要はない。次の例ではインデックス変数の計算が関わっている。
| 通常のループ | ループ展開後 |
|---|---|
x(1) = 1;
For i:=2:9 do
x(i):=x(i - 1)*i;
print i,x(i);
next i;
|
x(1):=1; x(2):=x(1)*2; print 2,x(2); x(3):=x(2)*3; print 3,x(3); ...etc. . |
コンパイラのループ展開によって大量のコード（特に print 文）が生成されるとしても、更なる最適化が可能である。この例ではループ内で x(i) と x(i - 1) しか参照しておらず（後者は x(i) の値を作るためにのみ参照）、配列 x に他から参照することがないなら、配列の各要素を単純な変数に置き換えることもできる。しかもこのコードでは各変数の値を定数から求めていて、全て定数とみなすこともできる。すると次のように最適化できる。
print 2,2; print 3,6; print 4,24; ...etc.
コンパイラが x を階乗のテーブルだと認識したとしたら驚きである。
一般にループの中身は大きく、複雑な配列のインデックス付けに関連している。その場合は最適化コンパイラに展開を任せるのが最善であろう。最も内側のループを展開することで様々な最適化が可能となるかもしれないが、ループ回数が多くない限り効果は限定的である。
WHILEループの展開
[編集]WHILEループの擬似コードの例を示す。
| 通常のループ | ループ展開後 | 展開し「調整」したループ |
|---|---|---|
WHILE (condition) DO
action
ENDWHILE
.
.
.
.
.
.
|
WHILE (condition) DO
action
IF NOT(condition) THEN GOTO break
action
IF NOT(condition) THEN GOTO break
action
ENDWHILE
LABEL break:
.
|
IF (condition) THEN
REPEAT {
action
IF NOT(condition) THEN GOTO break
action
IF NOT(condition) THEN GOTO break
action
} WHILE (condition)
LABEL break:
|
展開した例ではENDWHILE（コンパイルされるとループ先頭へのジャンプになる）の実行回数が66%少なくなり、高速化される。
さらに「調整」を加えた擬似コードの例では、最適化コンパイラを使えば無条件ジャンプを全く使わない形に最適化されるだろう。
動的ループ展開
[編集]ループ展開の有効性は対象となる配列の大きさに依存するが、実行時にならないとその大きさが判明しないことも多い。実行時コンパイラ (JIT) などは、通常のループにすべきか、展開すべきかを判断できる。ループ展開の観点では、この柔軟性が静的または手動の最適化に比べてJIT方式の強みとなっている。
アセンブリ言語では、効率的なジャンプテーブルを使うような技法で動的ループ展開を行うことができる。ここで重要となるのは、配列の最大オフセットが機械語命令で表せる範囲かどうかである。その範囲外の場合、最適化の効果が薄れる。次の例はSystem/360またはZ/Architectureのアセンブリ言語で書かれている。FROM配列とTO配列はそれぞれ1要素256バイトで50要素あり、各要素の先頭から100バイトをFROMからTOにコピーするものである。
アセンブリ言語（System/360）の例
[編集]* 配列などを指すよう全レジスタを初期化しておく（R14はリターンアドレス）
LM R15,R2,INIT load R15= '16'、R0= 配列要素数、R1--> FROM配列、R2--> TO配列
LOOP EQU *
SR R15,R0 配列要素数を16から引く
BNP ALL n > 16 なら全命令列を実行し、繰り返す
* MVC命令列の先頭からのオフセットを計算し、展開されたMVCループの所定の位置に無条件ジャンプする
MH R15,=AL2(ILEN) MVC命令の長さ（この例では6）をかける
B ALL(R15) インデックス付き分岐命令（その位置からMVC命令を実行）
* 転送テーブル - 1つめが最大オフセットであり、この例では X'F00'
ALL MVC 15*256(100,R2),15*256(R1) * 16番目のエントリの100バイトをFROMからTOに転送
ILEN EQU *-ALL MVC命令の長さ。この例では6
MVC 14*256(100,R2),14*256(R1) *
MVC 13*256(100,R2),13*256(R1) *
MVC 12*256(100,R2),12*256(R1) * これら16個の文字転送命令 (MVC) はベース+オフセットのアドレッシングであり
MVC 11*256(100,R2),11*256(R1) * オフセットは配列の要素長 (256) ずつ減っている。
MVC 10*256(100,R2),10*256(R1) * System/360では命令で指定できるオフセットの最大値は X'FFF' であり
MVC 09*256(100,R2),09*256(R1) * それを越えない範囲で展開可能な最大が16要素ということになる。
MVC 08*256(100,R2),08*256(R1) * オフセットの大きい方から転送するので、先頭の要素が最後に転送される。
MVC 07*256(100,R2),07*256(R1) *
MVC 06*256(100,R2),06*256(R1) *
MVC 05*256(100,R2),05*256(R1) *
MVC 04*256(100,R2),04*256(R1) *
MVC 03*256(100,R2),03*256(R1) *
MVC 02*256(100,R2),02*256(R1) *
MVC 01*256(100,R2),01*256(R1) 2番目の要素の100バイトを転送
MVC 00*256(100,R2),00*256(R1) 1番目の要素の100バイトを転送
*
S R0,MAXM1 残り要素数を引く
BNPR R14 全部転送し終えたので、R14のリターンアドレスで呼び出し元に復帰
AH R1,=AL2(16*256) FROMへのポインタを1反復ぶんだけずらす
AH R2,=AL2(16*256) TOへのポインタを1反復ぶんだけずらす
L R15,MAXM1 R15をMVC命令数 (16) に再設定する（計算で壊れているため）
B LOOP ループの先頭に戻る
*
* ----- 定数と変数の定義（引数として渡すこともできる） --------------------------------- *
INIT DS 0A LM命令で事前ロードされる4つのアドレス（ポインタ）
MAXM1 DC A(16) MVC命令数
N DC A(50) 配列の要素数（変数であり、変更可能）
DC A(FROM) 配列1の先頭アドレス（ポインタ）
DC A(TO) 配列2の先頭アドレス（ポインタ）
* ----- 配列の定義（動的に確保することも可能） -------------------------------------------------- *
FROM DS 50CL256 256バイト×50エントリの配列
TO DS 50CL256 256バイト×50エントリの配列
この例を通常の50回反復するループで記述すると202命令を必要とするが、このように動的コードにすると約89命令で済む（約56%のコード削減）。配列が2要素しかない場合でも、単純なループ展開と同程度の命令数となる。バイナリサイズの増大は約108バイトほどであり、配列の要素数が数千であっても対応可能である。この場合はMVC命令の反復を展開しただけだが、複数命令の場合も同様の技法が適用可能である。例えば、この例で各要素の先頭100バイトをコピーした後、残りの部分をヌル文字でクリアしたい場合、'XC xx*256+100(156,R1),xx*256+100(R2)' という命令を各MVC命令の後に追加すればよい（'xx' は直前のMVC命令と同じ値にする。ILENの位置に注意）。
4つまたは5つの引数を持つマクロで上記コードをインライン展開することも可能だし、サブルーチン化することも可能である。
C言語の例
[編集]次の例はC言語で書かれた簡単なプログラムを動的ループ展開したものである。アセンブリ言語の上掲の例とは異なり、変数 (i) が配列の要素を指すのに使われているため、コンパイラはポインタ/インデックスの計算コードを生成することになる。最大限最適化するには、全てのインデックス指定を定数に置き換えなければならない。
#include<stdio.h>
#define TOGETHER (8)
int main(void)
{
int i = 0;
int entries = 50; /* 総処理回数 */
int repeat; /* ループ回数 */
int left = 0; /* 余り（後で処理する） */
/* 要素数がBLOCKSIZEで割り切れないとしても、 */
/* 処理の大部分をwhileループで行うように、反復回数を得る。 */
repeat = (entries / TOGETHER); /* 反復回数 */
left = (entries % TOGETHER); /* 余りを計算 */
/* 8回ぶんの処理を展開 */
while( repeat-- > 0 )
{
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 += TOGETHER;
}
/* switch文を使い、caseラベルのジャンプすることで余りの部分を処理する。 */
/* フォールスルーにより、余りのぶんを全部処理する。 */
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 : ; /* 割り切れた場合 */
}
}
脚注
[編集]- ^ Ullman, Jeffrey D.; Aho, Alfred V. (1977). Principles of compiler design. Reading, Mass: Addison-Wesley Pub. Co. pp. 471–2. ISBN 0-201-10073-8
- ^ Petersen, W.P., Arbenz, P. (2004). Introduction to Parallel Computing. Oxford University Press. p. 10
- ^ Nicolau, Alexandru (1985). Loop Quantization: Unwinding for Fine-Grain Parallelism Exploitation. Dept. of Computer Science Technical Report. Ithaca, NY: Cornell University. OCLC 14638257.
- ^ Fog, Agner (2012年2月29日). “Optimizing subroutines in assembly language”. Copenhagen University College of Engineering. pp. 100. 2012年9月22日閲覧。 “12.11 Loop unrolling”
- ^ Sarkar, Vivek (2001). “Optimized Unrolling of Nested Loops”. International Journal of Parallel Programming 29 (5): 545–581. doi:10.1023/A:1012246031671.
- ^ Adam Horvath "Code unwinding - performance is far away"
参考文献
[編集]- Kennedy, Ken; & Allen, Randy. (2001). Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann. ISBN 1-55860-286-0
関連項目
[編集]- 実行時コンパイラ
- ループ分割
- ループ融合
- Duff's device
- 命令レベルの並列性
- 並列計算
外部リンク
[編集]- Chapter 7, pages 8 to 10 at the Wayback Machine (archived 2008-12-01), of Michael Abrash's Graphics Programming Black Book - ループ展開について論じており、x86アセンブリ言語の例もある。
- Generalized Loop Unrolling
- Optimizing subroutines in assembly language Agner Fog の最適化についてのハンドブック。ループ展開技法も掲載されている。
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.
