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

コンピューティングにおいて、パイプライン(データ パイプラインとも呼ばれる) は、直列に接続されたデータ処理要素のセットであり、1 つの要素の出力が次の要素の入力になります。パイプラインの要素は、多くの場合、並列またはタイム スライス方式で実行されます。要素間には、ある程度のバッファー ストレージが挿入されることがよくあります。

パイプラインは日常生活でよく使用される概念です。たとえば、自動車工場の組み立てラインでは、エンジンの取り付け、ボンネットの取り付け、ホイールの取り付けなどの特定のタスクは、多くの場合、別々の作業ステーションで実行されます。ステーションは、それぞれ異なる車でタスクを並行して実行します。1 つのタスクが完了すると、車は次のステーションに移動します。タスクを完了するために必要な時間の変動は、「バッファリング」(ステーション間のスペースに 1 台以上の車を保持) や「ストール」(上流のステーションを一時的に停止) によって、次のステーションが利用可能になるまで対応できます。

1 台の自動車を組み立てるのに、それぞれ 20 分、10 分、15 分かかる 3 つの作業が必要だとします。3 つの作業すべてを 1 つのステーションで実行した場合、工場は 45 分ごとに自動車 1 台を生産することになります。3 つのステーションのパイプラインを使用すると、工場は 45 分で最初の自動車を生産し、その後 20 分ごとに新しい自動車を生産することになります。

この例が示すように、パイプライン化によってレイテンシ(つまり、1 つの項目がシステム全体を通過する合計時間) が短縮されるわけではありません。ただし、システムのスループット(つまり、最初の項目の後に新しい項目が処理される速度) は向上します。

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

コンピュータ関連のパイプラインには次のものがあります。

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

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

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

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

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

要素の処理時間が可変である場合、その要素とそれ以前のすべての要素が入力バッファ内の項目を消費するのを待って、パイプライン全体が停止しなければならないことがよくあります。このようなパイプライン停止の頻度は、そのステージの入力バッファに複数の項目のためのスペースを提供することで減らすことができます。このような複数項目のバッファは、通常、先入れ先出しキューとして実装されます。キューがいっぱいになると上流ステージを停止しなければならない場合もありますが、バッファ スロットが増えるにつれて、これらのイベントの頻度は減ります。キューイング理論では、処理時間の可変性と必要なパフォーマンスに応じて、必要なバッファ スロットの数を判断できます。

ある段階が他の段階よりもずっと長くかかる (またはかかる可能性がある) 場合、速度を上げることができないため、設計者は 1 つの入力バッファと 1 つの出力バッファを使用して、そのタスクを並列に実行するための 2 つ以上の処理要素を提供できます。各要素が現在のデータ項目の処理を終了すると、それを共通の出力バッファに渡し、次のデータ項目を共通の入力バッファから取得します。この「非線形」または「動的」パイプラインの概念は、1 つの待機キューから顧客にサービスを提供する 2 人以上のレジ係がいる店舗や銀行で例証されます。

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

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

このような競合を適切に処理するには、競合を検出して適切なアクションを実行する追加の回路またはロジックをパイプラインに提供する必要があります。これを行うための戦略には次のものがあります。

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

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

データ パイプラインを効果的に実装するには、利用可能な CPU コアに作業をディスパッチする CPUスケジューリング戦略と、パイプライン ステージが操作するデータ構造の使用が必要です。たとえば、UNIX派生製品では、オペレーティング システムによって実装されたパイプを使用して、さまざまなプロセスの標準 IO を接続するコマンドをパイプライン化できます。一部のオペレーティング システム^{[要例]では、パイプラインで複数のプログラム実行を連結するための}UNIX 風の構文が提供されていますが、パイプライン化は、各プログラムが終了するまで待ってから次のプログラムを開始するという真のパイプライン化ではなく、単純なシリアル実行として実装されています。^[要出典]

低レベルのアプローチでは、ステージ上の作業をスケジュールするためにオペレーティングシステムによって提供されるスレッドに依存する場合があります。スレッドプールベースの実装とステージごとに1つのスレッドの両方が実行可能であり、存在しています。^[3]

協調的マルチタスクに依存する他の戦略も存在します。これは、複数の実行スレッドを必要とせず、したがって追加の CPU コアを必要としません。たとえば、コルーチン ベースのフレームワークを使用したラウンドロビン スケジューラの使用などです。このコンテキストでは、各ステージは独自のコルーチンでインスタンス化され、ラウンド タスクの終了後にスケジューラに制御が戻されます。このアプローチでは、プロセスのステージがタイム スライスを乱用しないように、プロセスのステージを慎重に制御する必要がある場合があります。

パイプライン システムでは通常、一度に 1 つのバッチを実行するシステムよりも多くのリソース (回路要素、処理ユニット、コンピュータ メモリなど) が必要になります。これは、パイプライン システムのステージでそれらのリソースを共有できないことと、要素間でバッファリングや追加の同期ロジックが必要になる可能性があるためです。

さらに、個別の処理要素間でのアイテムの転送により、特にパイプラインが長い場合には、レイテンシが増加する可能性があります。

異なる項目の処理間に依存関係がある場合、特に推測とバックトラック戦略を使用して処理する場合は、パイプライン化の複雑さによる追加のコストが相当なものになる可能性があります。実際、複雑な命令セットにその戦略を実装するコストは、RISCやVLIWなどのコンピューター アーキテクチャを簡素化するためのいくつかの急進的な提案のきっかけとなっています。コンパイラーは、命令パイプラインのパフォーマンスを向上させるためにマシン命令を再配置するタスクも負っています 。

近年、アプリケーションとその基盤となるハードウェアに対する要求が著しく高まっているのは事実です。たとえば、ビッグデータの量と種類を考えると、データを1行ずつ処理する単一ノードのアプリケーションでパイプラインを構築することはもはや現実的ではありません。しかし、 Hadoopや最近ではApache Sparkなどのデータ分析エンジンの登場により、大規模なデータセットを複数の処理ノードに分散できるようになり、アプリケーションは以前考えられていたよりも数百倍も高い効率性を実現できるようになりました。今日では、この方法で分散処理を使用する中級レベルのPCでも、ビッグデータパイプラインの構築と実行を処理できるようになりました。^[4]

• データフロー
• スループット
• 並列処理
• 命令パイプライン
  • 古典的なRISCパイプライン
• グラフィックスパイプライン
• パイプライン（ソフトウェア）
  • パイプライン (Unix)
  • VM 用Hartmann パイプライン
  • MVS 用バッチパイプ
• ジオメトリパイプライン
• XMLパイプライン
• 段階的なイベント駆動型アーキテクチャ

• Perez Garcia、Pablo (2018)。パイプライン DSL プロジェクト用の CI/CD パイプラインを作成するための DSL。Addison- Wesley。ISBN 978-0-134-69147-3。
• 並列コンピューティングにおけるパイプライン処理に関する標準的な議論については、Quinn, Michael J. (2004) 「Parallel Programming in C with MPI and openMP 」を参照してください。アイオワ州デュビューク: McGraw-Hill Professional。ISBN 0072822562。
• Pogonyi, Roland (2021 年 2 月)。「データ パイプラインとは何か?」。2021 年3 月 11 日閲覧。