ソフトウェアパイプライン
 |
ソフトウェアパイプライン（英: software pipelining なので正確には「パイプライン化」）は、コンピュータ・プログラムの最適化技法のひとつで、パイプライン化された（命令パイプラインの記事を参照）プロセッサの実行ユニットで効率良く実行できるように命令スケジューリングできるよう、プログラムを変形するという手法である。高度なコンパイラではコンパイラ最適化により行われることもあるが、一般にはしばしば、多数回繰り返されるが1回の処理内容がごくわずかなループ（画像処理や信号処理などには多い）について、手作業で、一種のアウト・オブ・オーダー実行のようなプログラムの書換え（ループの繰返しをまたいで、コードの順序を前後に入れ替えることが多い）を行う。アーキテクチャによっては、その仕様にソフトウェアパイプラインを特に意識した要素があるものもあり、特にインテルのIA-64アーキテクチャが著名である。
ソフトウェアパイプライニングの例
[編集]下記のようなループ例を考える。
for i = 1 to bignumber A(i) B(i) C(i) end
この例では、A(i), B(i), C(i), がそれぞれiを操作する命令であり、互いに依存関係がある。
すなわち A(i) は B(i) の開始前に完了している必要がある。例えば、A はメモリからレジスタにデータをロードし、Bがデータに算術演算を行い、Cがデータをメモリに書き戻す。しかし、それぞれが異なるiの値に対して依存がないと仮定すると、A(2) は A(1) が完了する前に開始することができる。ソフトウェアパイプラインを考えない場合には、コードは下記の順序で実行される。
A(1) B(1) C(1) A(2) B(2) C(2) A(3) B(3) C(3) ...
各命令は完了に 3 クロックかかるとする（制御ループのコストを考えない）。また（現代的なシステムでは一般的だが)実行中の命令に対して依存関係がなければ命令を各サイクルで割り当てることができるものとする。パイプライン化しない場合には、各ループが7サイクル(3 + 3 + 1, A(i+1) は C(i) を待つ必要がないため)かかることになる。
ソフトウェアパイプラインによって下記のように命令列を並べ替えると、
A(1) A(2) A(3) B(1) B(2) B(3) C(1) C(2) C(3) ...
毎サイクルで命令を割り当てることができ、全体が9サイクル、ループが平均 3 サイクルで実行できる。
ループ展開との組合せ
[編集]一般にソフトウェアパイプライニングはループ展開と組み合わせることで、うまく実現できる。例えば上記の例は、下記のようにも記述することができる（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における例
[編集]インテルの IA-64 はこのようなソフトウェアパイプラインの困難な点を念頭に置いて設計されたアーキテクチャの一例である。ソフトウェアパイプラインに関係するアーキテクチャ上のポイントの主要なものとして、以下のような点などがある。
- "rotating" レジスタバンク —— ループ内で、命令は別のレジスタを指すレジスタ番号を用いてレジスタを参照することができる（最終的には最初に戻ることができる）。これによって、上記の例のようにレジスタの重複を避けるための命令列を追加する必要がなくなる。
- "predicate" レジスタ —— predicateレジスタは、ループ内の比較命令によりセットされる。その値により後続するスロットの実行/否を制御することで、分岐を削除しパイプラインの乱れを抑制する（if 変換）。IA-64のpredicate レジスタは、その名前からしばしば分岐予測（branch prediction）と混同されるが、ARMアーキテクチャの条件付き実行命令と同様のコンセプトで、参照するpredicate レジスタの値によってスロットのオペレーションの実行/否を制御するものである。64本あるpredicate レジスタの1つpr0は常に真を返し、無条件実行のために使われる。