ソフトウェアパイプライン

一般にソフトウェアパイプライニングはループ展開と組み合わせることで、うまく実現できる。例えば上記の例は、下記のようにも記述することができる（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) ; 3
end

命令 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)

各行がパイプライン化されたループにおける一回分の繰り返しに相当し、繰り返し自体のための命令は取り除かれている。後処理も同様である。

前処理と後処理の必要性は、ソフトウェアパイプラインを実装する上で難しい点の一つである。例における前処理は18命令で、ループ自体の3倍も大きい。また後処理も18命令である。すなわち、前処理と後処理は合わせてループ自体より6倍大きい。この例ではまだループの展開を試みるほどではないが、ソフトウェアパイプラインは速度とメモリ使用量の点でトレードオフを必要とする。コードサイズが大きくなりすぎると、キャッシュの性能が相対的に下がるために実行速度に影響を与える。

さらに困難な点は、多くのアーキテクチャではほとんどの命令がレジスタを引数に用いており、特定のレジスタが命令にハードコードされている点である。つまり、多くのアーキテクチャでは、「レジスタX の内容とレジスタY の内容を乗算し、結果をレジスタZ に格納せよ」(X, Y, Z をレジスタやメモリから取得した数値とする)といった命令を使うことはできない。このことは従来のアーキテクチャ上ではソフトウェアパイプラインを効率的に実装できない理由としてしばしば取り上げられる。

Monica Lam は論文 A Systolic Array Optimizing Compiler(1989) (ISBN 0-89838-300-5) の中でこの問題に対する優れた解決方法を示している。彼女はこの方法を Modulo Renaming と呼んでいる。この方法では、ループの本体をループがスケジュールされた後に複製し、同じ変数の異なる値に対して（両方が同時に生存する必要がある場合には）異なるレジスタが使用できるようにする。最も簡潔な例として、命令 A(i) と命令 B(i) が同時に発行でき、B(i) のレイテンシが 2 サイクルであるとする。パイプライン化されたコードは下記のようになる。

A(i+2); B(i)

ループ本体のコードにレジスタを割り当てる際、A(i+2) の結果が2回のループの間ずっと生存させている必要がある。A(i+2) の結果と B(i) の入力に同じレジスタを用いると、誤った結果を生じる。

しかし、ループの本体を複製すると、問題が解決できる。

 A(i+2); B(i)
 A(i+3); B(i+1)

ここで命令 A(i+2) と命令 A(i+3) に異なるレジスタを割り当てることができる。詳細には

 r1 = A(i+2); B(i) = r1
 r2 = A(i+3); B(i+1) = r2
 i = i + 2 

各命令が出力レジスタに書き込む前に入力レジスタを読み込むことが保証できれば、このコードは正しく動作する。複製されたループ本体コードの最初では、r1 が A(i+2) の結果を保持している。i が2増加するので、これは複製されたループの繰り返し部分では A(i) の値である。

もちろんコードの複製により前処理や後処理と同様コードサイズが増加し命令キャッシュへの圧迫が大きくなる。にもかかわらず、十分な命令レベルの並列化が可能なアーキテクチャで、ループの回数が大きい場合に適用すれば、コードサイズを増加させても十分価値がある高い性能を容易に発揮することができる。

インテルの IA-64 はこのようなソフトウェアパイプラインの困難な点を念頭に置いて設計されたアーキテクチャの一例である。ソフトウェアパイプラインに関係するアーキテクチャ上のポイントの主要なものとして、以下のような点などがある。

• "rotating" レジスタバンク —— ループ内で、命令は別のレジスタを指すレジスタ番号を用いてレジスタを参照することができる（最終的には最初に戻ることができる）。これによって、上記の例のようにレジスタの重複を避けるための命令列を追加する必要がなくなる。
• "predicate" レジスタ —— predicateレジスタは、ループ内の比較命令によりセットされる。その値により後続するスロットの実行/否を制御することで、分岐を削除しパイプラインの乱れを抑制する（if 変換）。IA-64のpredicate レジスタは、その名前からしばしば分岐予測（branch prediction）と混同されるが、ARMアーキテクチャの条件付き実行命令と同様のコンセプトで、参照するpredicate レジスタの値によってスロットのオペレーションの実行/否を制御するものである。64本あるpredicate レジスタの1つpr0は常に真を返し、無条件実行のために使われる。