ループ展開との組合せ

ウィキペディア小見出し辞書

ループ展開との組合せ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/16 13:56 UTC 版)

「ソフトウェアパイプライン」の記事における「ループ展開との組合せ」の解説

一般にソフトウェアパイプライニングはループ展開と組み合わせることで、うまく実現できる。例えば上記の例は、下記のようにも記述することができる（bignumber が 3 の倍数とする） for i = 1 to (bignumber - 2) step 3 A(i) A(i+1) A(i+2) B(i) B(i+1) B(i+2) C(i) C(i+1) C(i+2)end もちろん、繰り返し回数が展開する数で常に割り切れるとは限らない（この問題に対する解答は、ループ展開の項目を参照のこと)。なお、ソフトウェアパイプラインではこのような問題に対する効率的な解法であるDuff's device を利用できない点に注意が必要である。 一般的には、ループ展開がソフトウェアパイプラインの最適の実装方法でない場合もある。下のようにレイテンシが大きい命令を含むループを考えると、 for i = 1 to bignumber A(i) ; 3 cycle のレイテンシ B(i) ; 3 C(i) ; 12 (浮動小数点演算） D(i) ; 3 E(i) ; 3 F(i) ; 3end 命令 C のボトルネックを避けるためには、ループが 12 回以上回る必要がある。つまりループ部分のコードは12倍以上増加する(使用するメモリ量に影響するだけでなく、キャッシュ性能にも影響する。コードの膨張参照)。さらに、bignumber が 12 で割り切れない場合に追加するコードがループ自体より大きくなる可能性がある。このコードでは（これ以上をコードの膨張させずに）ソフトウェアパイプラインを使用できないために効率が悪くなる。また、bignumber がループが展開されない場合のループ回数に対してコードサイズの点から適切であったとすると（例えば10-20程度)、実行時間の大半を、効率的でない12の余りの部分のコード実行に費やしてしまい、ソフトウェアパイプラインによる最適化が非効率なものになってしまう。 上記の例を異なる方法でソフトウェア実装したものを示す。（前処理と後処理については後述する） 前処理for i = 1 to (bignumber - 6) A(i+6) B(i+5) C(i+4) D(i+2) ; i+3 をスキップする E(i+1) F(i)end後処理 ループの前後で実行する前処理・後処理について説明する前に、このコードが繰り返し部分について元のコードと同じ結果を得られるかを検証する。元のループで7度目の繰り返しを考える。パイプライン化されたループの最初の繰り返しでは、元のループでの7度目の繰り返しまでの命令を含んでいる。命令列は下記のようになる。 Iteration 1: A(7) B(6) C(5) D(3) E(2) F(1) Iteration 2: A(8) B(7) C(6) D(4) E(3) F(2) Iteration 3: A(9) B(8) C(7) D(5) E(4) F(3) Iteration 4: A(10) B(9) C(8) D(6) E(5) F(4) Iteration 5: A(11) B(10) C(9) D(7) E(6) F(5) Iteration 6: A(12) B(11) C(10) D(8) E(7) F(6) Iteration 7: A(13) B(12) C(11) D(9) E(8) F(7) しかし、元のループとは異なり、パイプライン化されたものは、命令 C のボトルネックを回避できる。C(7) およびその結果に依存した D(7) の間には命令が12個あり、C(7) のレイテンシが無駄にならずに他の命令の実行に使用される。 前処理と後処理では、繰り返しの始めと終わりを処理する。下記が前処理として考えられるコードである。 ; 前処理 (行に分割して表示)A(1)A(2), B(1)A(3), B(2), C(1)A(4), B(3), C(2)A(5), B(4), C(3), D(1)A(6), B(5), C(4), D(2), E(1) 各行がパイプライン化されたループにおける一回分の繰り返しに相当し、繰り返し自体のための命令は取り除かれている。後処理も同様である。