パイプライン（コンピューティング）

コンピューティングにおいて、パイプラインまたはデータパイプライン^{[ 1 ]}とは、直列に接続されたデータ処理要素の集合であり、ある要素の出力が次の要素の入力となる。パイプラインの要素は、並列または時間分割方式で実行されることが多い。要素間には、一定量のバッファストレージが挿入されることが多い。

コンピュータ関連のパイプラインには以下が含まれます。

• 命令パイプラインは、中央処理装置（CPU）やその他のマイクロプロセッサで使用され、同じ回路で複数の命令をオーバーラップ実行することを可能にする、古典的なRISCパイプラインなどの例です。回路は通常、ステージに分割され、各ステージは一度に1つの命令の特定の部分を処理し、部分的な結果を次のステージに渡します。ステージの例としては、命令デコード、算術/論理演算、レジスタフェッチなどがあります。これらは、スーパースカラ実行、オペランド転送、投機的実行、アウトオブオーダー実行などの技術に関連しています。
• グラフィックスパイプラインは、ほとんどのグラフィックス処理ユニット（GPU）に搭載されており、複数の演算ユニット、または完全なCPUで構成され、一般的なレンダリング操作のさまざまな段階（透視投影、ウィンドウクリッピング、色と光の計算、レンダリングなど）を実行します。
• ソフトウェアパイプラインとは、一連の計算処理（コマンド、プログラム実行、タスク、スレッド、プロシージャなど）から構成され、概念的には並列に実行される。ある処理の出力ストリームは、自動的に次の処理の入力ストリームとして供給される。Unixのシステムコールパイプは、この概念の典型的な例である。
• HTTPパイプライン処理とは、同じTCP接続を介して複数のHTTPリクエストを発行する技術であり、前のリクエストの完了を待たずに次のリクエストを発行する。

パイプラインが冪等なステップで構成されている場合、最初の実行結果以降、これらのステップを再実行しても結果は変わりません。これは、信頼性と保守性の面で有利です。

パイプラインのスループットは、最も遅い要素のスループットを超えることはできないため、設計者は各ステージ間で作業とリソースを分割し、すべてのステージがタスクを完了するのに同じ時間を要するようにする必要があります。上記の自動車組立の例では、3つのタスクがそれぞれ20分、10分、15分ではなく15分で完了する場合、遅延時間は依然として45分ですが、新しい自動車は20分ごとではなく15分ごとに完成することになります。

理想的な状況では、すべての処理要素が同期しており、処理に同じ時間を要する場合、各要素は、前の要素によってリリースされたのとまったく同じタイミングで、単一のクロックサイクルで各要素に受信されます。このようにして、項目は水路の波のように、一定の速度でパイプラインを流れます。このような「波のパイプライン」^{[ 2 ]}では、データ項目のストレージ以外に、ステージ間の同期やバッファリングは必要ありません。

より一般的には、処理時間が不規則な場合や、パイプラインの途中でアイテムが生成または破棄される場合、パイプラインの各ステージ間でバッファリングが必要になります。たとえば、画面にレンダリングする三角形を処理するグラフィックスパイプラインでは、各三角形の可視性をチェックする要素が、三角形が見えない場合はその三角形を破棄したり、部分的に隠れている場合は要素の2つ以上の三角形の断片を出力したりすることがあります。また、アプリケーションが最初のステージにアイテムを供給し、最後のステージの出力を消費する速度の不規則性に対応するためにも、バッファリングが必要です。

2つのステージ間のバッファは、適切な同期および信号ロジックを備えたハードウェアレジスタで構成できます。ステージAがレジスタにデータ項目を格納すると、次のステージBに「データ利用可能」信号を送信します。Bはそのデータを使用すると、Aに「データ受信」信号で応答します。ステージAは、次のデータ項目をレジスタに格納する前に、この信号を待って停止します。ステージBは、次の項目を処理する準備ができていても、ステージAからまだデータが提供されていない場合、「データ利用可能」信号を待って停止します。

要素の処理時間が変動する場合、パイプライン全体が停止し、その要素とそれ以前のすべての要素が入力バッファ内の項目を消費するのを待つ必要が生じることがよくあります。このようなパイプラインの停止頻度は、そのステージの入力バッファに複数の項目を格納するスペースを設けることで低減できます。このような複数項目バッファは、通常、先入れ先出し（FIFO）キューとして実装されます。キューが満杯になると、上流ステージが停止する必要が生じる場合もありますが、バッファスロットが増えるほど、停止頻度は減少します。キューイング理論を用いることで、処理時間の変動性と要求されるパフォーマンスに応じて、必要なバッファスロット数を算出できます。

ある段階の処理に他の段階よりもはるかに時間がかかり（またはかかる可能性があり）、かつ処理速度を上げることができない場合、設計者は単一の入力バッファと単一の出力バッファを備えた2つ以上の処理要素を用意して、そのタスクを並列に実行させることができます。各要素は現在の処理中のデータ項目の処理が完了すると、それを共通の出力バッファに送り、共通の入力バッファから次のデータ項目を取り出します。この「非線形」または「動的」パイプラインの概念は、2人以上のレジ係が1つの待機列から顧客に対応する店舗や銀行などでよく見られます。

アプリケーションによっては、ステージAによるアイテムYの処理が、パイプラインの後段ステージBによる前のアイテムXの処理結果または影響に依存する場合があります。その場合、アイテムXがステージBを通過するまで、ステージAはアイテムYを正しく処理できません。

この状況は、命令パイプラインで非常によく発生します。たとえば、Y が、以前の命令 X によって変更されたはずのレジスタの内容を読み取る算術命令であるとします。A を命令オペランドをフェッチするステージ、B を結果を指定されたレジスタに書き込むステージとします。ステージ A が命令 X がステージ B に到達する前に命令 Y を処理しようとすると、レジスタにはまだ古い値が残っている可能性があり、Y の効果が正しくなくなります。

このような競合を適切に処理するためには、パイプラインに競合を検出して適切な措置を講じるための追加の回路またはロジックを組み込む必要があります。そのための戦略としては、以下のようなものがあります。

• 停止：影響を受けるすべてのステージ（Aなど）は、依存関係が解消されるまで、つまり必要な情報が入手可能になるか、必要な状態が達成されるまで停止します。
• 項目の順序変更：ステージAは、処理を停止する代わりに、項目Yを脇に置き、入力ストリーム内で、それ以前の項目との依存関係が保留されていない後続の項目Zを探すことがあります。命令パイプラインでは、この手法はアウトオブオーダー実行と呼ばれます。
• 推測と逆算：項目間の依存関係の重要な例の1つは、命令パイプラインによる条件分岐命令Xの処理です。パイプラインの最初のステージAは、次に実行される命令Yをフェッチしますが、Xがオペランドをフェッチし、分岐を実行するかどうかを決定するまで、そのタスクを実行できません。Xのオペランドは、メインメモリからデータをフェッチする前の命令に依存する可能性があるため、これには多くのクロックサイクルが必要になる場合があります。

X の完了を待って停止するのではなく、ステージ A は分岐が実行されるかされないかを推測し、その推測に基づいて次の命令 Y をフェッチすることができます。後でその推測が間違っていることが判明した場合 (まれなケースであることを願いますが)、システムはバックトラックして正しい選択で再開する必要があります。つまり、ステージ A およびその推測に基づいて後続のステージによってマシンの状態に加えられたすべての変更を元に戻し、パイプラインに既に存在する X に続く命令をフラッシュし、ステージ A を正しい命令ポインタで再開する必要があります。この分岐予測戦略は、投機的実行の特殊なケースです。