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

ソフトウェアパイプライン（英: software pipelining なので正確には「パイプライン化」）は、コンピュータ・プログラムの最適化技法のひとつで、パイプライン化された（命令パイプラインの記事を参照）プロセッサの実行ユニットで効率良く実行できるように命令スケジューリングできるよう、プログラムを変形するという手法である。高度なコンパイラではコンパイラ最適化により行われることもあるが、一般にはしばしば、多数回繰り返されるが1回の処理内容がごくわずかなループ（画像処理や信号処理などには多い）について、手作業で、一種のアウト・オブ・オーダー実行のようなプログラムの書換え（ループの繰返しをまたいで、コードの順序を前後に入れ替えることが多い）を行う。アーキテクチャによっては、その仕様にソフトウェアパイプラインを特に意識した要素があるものもあり、特にインテルのIA-64アーキテクチャが著名である。
ソフトウェアパイプライニングの例.
下記のようなループ例を考える。
 for i = 1 to bignumber
 A(i)
 B(i)
 C(i)
 end
この例では、codice_1, codice_2, codice_3, がそれぞれcodice_4を操作する命令であり、互いに依存関係がある。
すなわち codice_1 は codice_2 の開始前に完了している必要がある。例えば、codice_7 はメモリからレジスタにデータをロードし、codice_8がデータに算術演算を行い、codice_9がデータをメモリに書き戻す。しかし、それぞれが異なるcodice_4の値に対して依存がないと仮定すると、codice_11 は codice_12 が完了する前に開始することができる。ソフトウェアパイプラインを考えない場合には、コードは下記の順序で実行される。
 A(1) B(1) C(1) A(2) B(2) C(2) A(3) B(3) C(3) ...
各命令は完了に 3 クロックかかるとする（制御ループのコストを考えない）。また（現代的なシステムでは一般的だが)実行中の命令に対して依存関係がなければ命令を各サイクルで割り当てることができるものとする。パイプライン化しない場合には、各ループが7サイクル(3 + 3 + 1, codice_13 は codice_3 を待つ必要がないため)かかることになる。
ソフトウェアパイプラインによって下記のように命令列を並べ替えると、
 A(1) A(2) A(3) B(1) B(2) B(3) C(1) C(2) C(3) ...
毎サイクルで命令を割り当てることができ、全体が9サイクル、ループが平均 3 サイクルで実行できる。
ループ展開との組合せ.
一般にソフトウェアパイプライニングはループ展開と組み合わせることで、うまく実現できる。例えば上記の例は、下記のようにも記述することができる（codice_15 が 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
命令 codice_9 のボトルネックを避けるためには、ループが 12 回以上回る必要がある。つまりループ部分のコードは12倍以上増加する(使用するメモリ量に影響するだけでなく、キャッシュ性能にも影響する。"参照")。さらに、codice_15 が 12 で割り切れない場合に追加するコードがループ自体より大きくなる可能性がある。このコードでは（これ以上をコードの膨張させずに）ソフトウェアパイプラインを使用できないために効率が悪くなる。また、codice_15 がループが展開されない場合のループ回数に対してコードサイズの点から適切であったとすると（例えば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度目の繰り返しまでの命令を含んでいる。命令列は下記のようになる。
しかし、元のループとは異なり、パイプライン化されたものは、命令 codice_9 のボトルネックを回避できる。codice_20 およびその結果に依存した codice_21 の間には命令が12個あり、codice_20 のレイテンシが無駄にならずに他の命令の実行に使用される。
前処理と後処理では、繰り返しの始めと終わりを処理する。下記が前処理として考えられるコードである。
 ; 前処理 (行に分割して表示)
 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倍大きい。この例ではまだループの展開を試みるほどではないが、ソフトウェアパイプラインは速度とメモリ使用量の点でトレードオフを必要とする。コードサイズが大きくなりすぎると、キャッシュの性能が相対的に下がるために実行速度に影響を与える。
さらに困難な点は、多くのアーキテクチャではほとんどの命令がレジスタを引数に用いており、特定のレジスタが命令にハードコードされている点である。つまり、多くのアーキテクチャでは、「レジスタcodice_23 の内容とレジスタcodice_24 の内容を乗算し、結果をレジスタcodice_25 に格納せよ」(codice_23, codice_24, codice_25 をレジスタやメモリから取得した数値とする)といった命令を使うことはできない。このことは従来のアーキテクチャ上ではソフトウェアパイプラインを効率的に実装できない理由としてしばしば取り上げられる。
 は論文 "A Systolic Array Optimizing Compiler"(1989) (ISBN 0-89838-300-5) の中でこの問題に対する優れた解決方法を示している。彼女はこの方法を "Modulo Renaming" と呼んでいる。この方法では、ループの本体をループがスケジュールされた後に複製し、同じ変数の異なる値に対して（両方が同時に生存する必要がある場合には）異なるレジスタが使用できるようにする。最も簡潔な例として、命令 codice_1 と命令 codice_2 が同時に発行でき、codice_2 のレイテンシが 2 サイクルであるとする。パイプライン化されたコードは下記のようになる。
 A(i+2); B(i)
ループ本体のコードにレジスタを割り当てる際、codice_32 の結果が2回のループの間ずっと生存させている必要がある。codice_32 の結果と codice_2 の入力に同じレジスタを用いると、誤った結果を生じる。
しかし、ループの本体を複製すると、問題が解決できる。
 A(i+2); B(i)
 A(i+3); B(i+1)
ここで命令 codice_32 と命令 codice_36 に異なるレジスタを割り当てることができる。詳細には
 r1 = A(i+2); B(i) = r1
 r2 = A(i+3); B(i+1) = r2
 i = i + 2 
各命令が出力レジスタに書き込む前に入力レジスタを読み込むことが保証できれば、このコードは正しく動作する。複製されたループ本体コードの最初では、codice_37 が codice_32 の結果を保持している。codice_4 が2増加するので、これは複製されたループの繰り返し部分では codice_1 の値である。
もちろんコードの複製により前処理や後処理と同様コードサイズが増加し命令キャッシュへの圧迫が大きくなる。にもかかわらず、十分な命令レベルの並列化が可能なアーキテクチャで、ループの回数が大きい場合に適用すれば、コードサイズを増加させても十分価値がある高い性能を容易に発揮することができる。
IA-64における例.
インテルの IA-64 はこのようなソフトウェアパイプラインの困難な点を念頭に置いて設計されたアーキテクチャの一例である。ソフトウェアパイプラインに関係するアーキテクチャ上のポイントの主要なものとして、以下のような点などがある。