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

コンピュータサイエンスにおいて、ソフトウェア パイプラインは、ハードウェア パイプラインと並行してループを最適化する ために使用される手法です。ソフトウェア パイプラインは、順序変更がプロセッサではなくコンパイラ(または手書きのアセンブリ コードの場合はプログラマ)によって実行される点を除いて、アウトオブオーダー実行の一種です。一部のコンピュータ アーキテクチャでは、ソフトウェア パイプラインが明示的にサポートされています。IntelのIA-64アーキテクチャが代表的です。

ループ反復の重複を対象としたコード手法であるソフトウェア パイプライン を、ソフトウェア パイプライン ループを生成するための現在最も効果的なコンパイラ手法として知られているモジュロ スケジューリングと区別することが重要です。ソフトウェア パイプラインは、命令レベルの並列性を備えたマシンのアセンブリ言語プログラマには、そのようなアーキテクチャが存在していた頃から知られています。このようなコードの効果的なコンパイラ生成は、Rau と Glaeser によるモジュロ スケジューリングの発明にまで遡ります。^[1] Lam は、効果的なモジュロ スケジューリングには特別なハードウェアは不要であることを示しました。彼女の手法であるモジュロ変数拡張は、実際に広く使用されています。^[2] Gao らは、整数線形計画法における最適なソフトウェア パイプラインを定式化し、評価論文で高度なヒューリスティックの検証に至りました。^[3]この論文には、このトピックに関する優れた参考文献があります。

次のループを考えてみましょう。

i = 1 から bignumber まで
  A(i)
  B(i)
  C(i)
終わり

この例では、、、を命令としA(i)、B(i)各C(i)命令はデータ に対して動作しi、互いに依存関係があります。つまり、が開始するA(i)前に完了する必要があります。たとえば、 はメモリからレジスタにデータをロードし、データに対して何らかの算術演算を実行し、データをメモリに戻すことができます。ただし、 の異なる値に対する操作間に依存関係がないものとします。つまり、が終了する前に開始できます。 B(i)ABCiA(2)A(1)

ソフトウェア パイプラインがない場合、操作は次の順序で実行されます。

A(1) B(1) C(1) A(2) B(2) C(2) A(3) B(3) C(3) ...

各命令が完了するまでに 3クロック サイクルかかると仮定します(ループ制御フローのコストは今のところ無視します)。また、(ほとんどの最新システムの場合と同様に) 命令は、すでに実行中の命令に依存していない限り、サイクルごとにディスパッチできると仮定します。パイプライン化されていない場合、各反復は完了するまでに 9 サイクルかかります。 の場合は 3 クロック サイクルA(1)、 の場合は 3 クロック サイクルB(1)、 の場合は 3 クロック サイクルですC(1)。

ここで、ソフトウェア パイプラインを使用した次の命令シーケンスを検討します。

A(1) A(2) A(3) B(1) B(2) B(3) C(1) C(2) C(3) ...

命令を各サイクルにディスパッチできることは簡単に確認できます。つまり、同じ 3 つの反復を合計 9 サイクルで実行でき、反復あたり平均 3 サイクルになります。

ソフトウェア パイプラインはループ アンローリングと組み合わせて使用​​されることが多く、この手法の組み合わせはループ アンローリングのみを使用する場合よりもはるかに優れた最適化となることがよくあります。上記の例では、次のようにコードを記述できます (現時点では がbignumber3 で割り切れると仮定します)。

i = 1 から (bignumber - 2) までステップ 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)
終わり

もちろん、（通常はそうであるように）反復の総数が展開する反復の数で割り切れることを保証できない場合は、問題は複雑になります。 この問題の解決策の詳細については、ループ展開に関する記事を参照してください。ただし、ソフトウェア パイプラインによってDuff のデバイスが使用できなくなることに注意してください。^{[引用が必要]}

一般的に、ループ アンローリングはソフトウェア パイプラインを実装する最善の方法ではない可能性があります。レイテンシの高い命令を含むループについて考えてみましょう。たとえば、次のコードです。

i = 1 から bignumber まで
  A(i) ; 3サイクルの待ち時間
  B(i) ; 3
  C(i) ; 12(おそらく浮動小数点演算)
  D(i) ; 3
  E(i) ; 3
  F(i) ; 3
終わり

命令のボトルネックを回避するには、ループを 12 回展開する必要がありますC。つまり、ループのコードが 12 倍に増えます (メモリ使用量に影響するだけでなく、キャッシュパフォーマンスにも影響する可能性があります。コードの膨張を参照)。さらに悪いことに、プロローグ (ループの前の、 が 12 で割り切れない場合の処理​​コードbignumber) は、ループのコードよりもさらに大きくなる可能性が高く、このコードではソフトウェア パイプラインを使用できないため (少なくとも、大幅なコード膨張なしでは) 非効率的になる可能性が非常に高くなります。さらに、bignumberが展開される反復回数に比べて中程度の大きさになると予想される場合 (たとえば 10～20)、実行のほとんどの時間がこの非効率的なプロローグ コードで費やされ、ソフトウェア パイプラインの最適化が無効になります。

対照的に、この例のソフトウェア パイプラインは次のとおりです (プロローグとエピローグについては後で説明します)。

プロローグ
i = 1 から (bignumber - 6) まで
  A(i+6)
  B(i+5)
  C(i+4)
  D(i+2) ; i+3をスキップすることに注意
  （i+1）
  F(i)
終わり
エピローグ

ループの最初と最後の反復を処理するプロローグとエピローグに進む前に、このコードがループの途中の反復に対して元のコードと同じことを実行することを確認しましょう。具体的には、元のループの反復 7 について考えます。パイプライン ループの最初の反復は、元のループの反復 7 からの命令を含む最初の反復になります。命令のシーケンスは次のとおりです。

反復1:A(7) B(6) C(5) D(3) E(2) F(1)

反復2:A(8) B(7) C(6) D(4) E(3) F(2)

反復3:A(9) B(8) C(7) D(5) E(4) F(3)

反復4:A(10) B(9) C(8) D(6) E(5) F(4)

反復5:A(11) B(10) C(9) D(7) E(6) F(5)

反復6:A(12) B(11) C(10) D(8) E(7) F(6)

反復7:A(13) B(12) C(11) D(9) E(8) F(7)

ただし、元のループとは異なり、パイプライン バージョンでは命令 でのボトルネックを回避します。と依存命令Cの間には 12 個の命令があることに注目してください。これは、命令 のレイテンシ サイクルが無駄にされるのではなく、他の命令に使用されることを意味します。 C(7)D(7)C(7)

プロローグとエピローグは、ループの最初と最後の反復を処理します。上記の例のプロローグの例を次に示します。

; ループプロローグ（わかりやすくするために線で配置）
A(1)
A(2)、B(1)
A(3)、B(2)、C(1)
A(4)、B(3)、C(2)；D(1)はまだ開始できない
A(5)、B(4)、C(3)、D(1)
A(6)、B(5)、C(4)、D(2)、E(1)

上記の各行は、メインのパイプライン ループの反復に対応していますが、まだ開始されていない反復の命令は含まれていません。同様に、エピローグでは、完了した反復の命令が段階的に削除されます。

; ループエピローグ（わかりやすくするために線で配置）
B(ビッグナンバー)、C(ビッグナンバー-1)、D(ビッグナンバー-3)、E(ビッグナンバー-4)、F(ビッグナンバー-5)
C(大きな数)、D(大きな数-2)、E(大きな数-3)、F(大きな数-4)
D(ビッグナンバー-1)、E(ビッグナンバー-2)、F(ビッグナンバー-3)
D(大きな数)、E(大きな数-1)、F(大きな数-2)
E(大きな数)、F(大きな数-1)
F(大きな数)

プロローグとエピローグの要件は、ソフトウェア パイプラインを実装する際の大きな難しさの 1 つです。この例のプロローグは 18 命令で、ループ自体の 3 倍の大きさであることに注意してください。エピローグも 18 命令です。言い換えると、プロローグとエピローグを合わせるとループ自体の 6 倍の大きさになります。この例ではループ アンローリングを試みるよりはまだましですが、ソフトウェア パイプラインでは速度とメモリ使用量のトレードオフが必要になります。また、コードが大きくなりすぎると、キャッシュ パフォーマンスの低下によって速度に影響が出ることにも留意してください。

さらに難しいのは、多くのアーキテクチャでは、ほとんどの命令がレジスタを引数として使用し、使用する特定のレジスタを命令にハードコードする必要があることです。言い換えると、多くのアーキテクチャでは、「レジスタXとレジスタの内容を乗算しY、結果をレジスタ に格納するZ」などの命令をコーディングすることは不可能です。ここでX、、、およびはY、Z他のレジスタまたはメモリから取得された数値です。これは、従来のアーキテクチャでソフトウェア パイプラインを効果的に実装できない理由としてよく挙げられます。

実際、Monica Lam は、論文「A Systolic Array Optimizing Compiler (1989)」( ISBN  0-89838-300-5 ) で、この問題に対する洗練された解決策を提示しています。彼女はこれをモジュロ変数拡張と呼んでいます。その秘訣は、スケジュールされた後にループ本体を複製し、同時に有効にする必要がある場合に、同じ変数の異なる値に異なるレジスタを使用できるようにすることです。最も単純な例として、A(i)とをB(i)並列に発行でき、前者のレイテンシが 2 サイクルであると仮定します。パイプライン化された本体は次のようになります。

A(i+2) と B(i)

このループ本体のレジスタ割り当てでは、 の結果が 2 回の反復にわたって有効のままでなければならないという問題が発生します。 の結果と の入力A(i+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の値を保持します。 はその間に 2 ずつ増加しているので、これは実際にはこの複製されたループ反復における の値です。A(i+2)iA(i)

もちろん、コードのレプリケーションは、プロローグとエピローグと同様に、コード サイズとキャッシュ プレッシャーを増加させます。ただし、十分な命令レベルの並列性を備えたアーキテクチャでトリップ カウントが大きいループの場合、この手法はコード サイズの増加に見合うだけの十分なパフォーマンスを発揮します。

Intel の IA-64 アーキテクチャは、ソフトウェア パイプラインの難しさを考慮して設計されたアーキテクチャの例です。ソフトウェア パイプラインのアーキテクチャ サポートには、次のものがあります。

• 「ローテーション」レジスタ バンク。命令は、ループの各反復ごとに別のレジスタにリダイレクトされるレジスタ番号を参照できます (最終的には先頭に戻ります)。これにより、前の例で挿入された追加の命令^[指定]は不要になります。
• 特別なループ命令から値を取得する述語(命令を「述語化」するために使用されます。分岐述語を参照)。これらの述語はループ内の特定の命令をオンまたはオフにするため、個別のプロローグとエピローグは不要になります。