ループ最適化
「プログラムの実行時間の8は原始プログラムの2割の部分の実行で占められる」と言われる
この2割の部分はループ、特に多重ループ
ループ部分の最適化は重要
loop-based strength reduction
以下のような例のiのことを「帰納変数」と呼ぶ
ループの各繰り返しで値が一定値だけ増加、減少するもの
*を+で表現するように変換するなど
code:c
for(i-1; i<n; i++)
a=a+b*i;
↓
t=0;
for(i=1; i<n; i++){
t=t+b;a=a+t; // +だけになった
}
table:ループ内の演算の強さの軽減
ループ内に出現する式 ループ文の直前の文 一時変数tの代入文
b*i t=0; t = t + b;
b^i t=1; t = t * b;
(-1)^i t=1; t = - t;
(iは帰納変数、bはループ不変)
以下のコード、iとtは帰納変数
iは1ずつ、tはbずつ増加する
ループを繰り返す条件i<nをt<n*bで置き換えることでiを消去してる
code:c
t=b;
for(i=1;i<n;i++){
a=a+t;t=t+b;
}
↓
m=n*b;
for(t=b;t<m;t=t+b)
a=a+t;
loop fusion, loop
2つの繰り返し文を融合する
帰納変数iの範囲が同じ、2つのループでの変数間の依存関係が変わらないときに融合可能
帰納変数iの同じ計算を1回で済ますことができる
基本ブロックが合体されることで、基本ブロック内での最適化の可能性が増加する
code:c
for(i=1;i<n;i++)
for(i=1;i<n;i++)
↓
for(i=1;i<n;i++){
}
loop distribution
よくわからないので、そのまま引用
この例では、ループ分解によって得られた最初の繰り返し文は、元の繰り返しの本体の依存関係が除去されることにより、並列実行が可能となっている。
また、この変換によって繰り返し本体が小さくなることにより、ハードウェア(レジスタ、キャッシュメモリなど)の必要量が減少するという利点がある。
融合とどっちが効果あるんだろうmrsekut.icon
code:c
for(i=1;i<n;i++){
}
↓
for(i=1;i<n;i++)
for(i=1;i<n;i++)
A_i, B_i, C_iはループのi回目の繰り返しに置いて実行されるループ本体の最初の文
C_{i-2}, B_{i-1}, A_iが並列実行可能であることに着目して変換してる
↑この3つがループ本体となるように変換
有向グラフを作ることで、B_iはA_iの後に実行されないといけないことなどがわかる 破線は有向辺のループ運搬依存を表す
こうすることで実行スケジュールの表を作成でき、新しいfor文の本体としてC_{i-2}, B_{i-1}, A_iを実行すると良いことがわかる
https://gyazo.com/32cdb5deac0c31ca6d6fde8e89b7b4da
code:example
for(i=i;i<1000;i++){
}
↓
A1;
B1;A2;
for(i=3; i<1000; i++){
C_{i-2};B_{i-1};Ai;
}
C_998;B_999;
C_999;
参考