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

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

ソフトウェアパイプライン: Software pipeline)とは、計算機科学における命令スケジューリング方法の一つで、命令パイプラインによる並列化と同じ方法でループ処理を最適化する技法である。ソフトウェアパイプラインはアウト・オブ・オーダー実行の一種であるが、命令の並べ替えがCPU ではなくコンパイラで (手動で行う場合にはアセンブリ言語を用いて)行われる点に違いがある。アーキテクチャによってはソフトウェアパイプラインをサポートするものもあり、特にインテル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 

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

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

IA-64 における実装[編集]

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

  • 回転レジスタバンク; ループ内で、命令は別のレジスタを指すレジスタ番号を用いてレジスタを参照することができる(最終的には最初に戻ることができる)。これによって、上記の例のようにレジスタの重複を避けるための命令列を追加する必要がなくなる。
  • プレディケート (命令を「断定」するために用いられる。分岐断定参照) プレディケートは特殊なループ命令から値を取得する。プレディケートはループ内の特定の命令を有効にしたり無効にしたりでき、これにより前処理や後処理のコードを記述する必要がなくなる。