パイプライン(コンピューティング)

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

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

コンピューター関連のパイプラインは次のとおりです。

一部のオペレーティングシステム[必要な例]は、パイプラインで複数のプログラム実行を文字列化するUNIXライクな構文を提供しますが、後者を真のパイプラインではなく単純なシリアル実行として実装します。つまり、各プログラムが終了するのを待ってから次のプログラムを開始します。 。[要出典]

コンセプトとモチベーション

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

1台の車を組み立てるのに、それぞれ20分、10分、15分かかる3つのタスクが必要だとします。次に、3つのタスクすべてが単一のステーションで実行された場合、工場は45分ごとに1台の車を出力します。3つのステーションのパイプラインを使用することにより、工場は45分で最初の車を出力し、その後20分ごとに新しい車を出力します。

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

設計上の考慮事項

ステージのバランスをとる

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

バッファリング

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

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

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

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

非線形パイプライン

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

アイテム間の依存関係

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

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

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

  • ストール: Aなどの影響を受けるすべてのステージは、依存関係が解決されるまで、つまり、必要な情報が利用可能になるか、必要な状態が達成されるまで停止されます。
  • アイテムの並べ替え:ステージAは、ストールする代わりに、アイテムYを脇に置き、入力ストリーム内で、以前のアイテムとの依存関係が保留されていない後続のアイテムZを探す場合があります。命令パイプラインでは、この手法はアウトオブオーダー実行と呼ばれます。
  • 推測とバックトラック:アイテム間の依存関係の重要な例の1つは、命令パイプラインによる条件付き分岐命令Xの処理です。実行される次の命令Yをフェッチするパイプラインの最初のステージAは、Xがそのオペランドをフェッチし、分岐を実行するかどうかを決定するまで、そのタスクを実行できません。Xのオペランドは、メインメモリからデータをフェッチする前の命令に依存する可能性があるため、これには多くのクロックサイクルがかかる場合があります。
ステージAは、Xが終了するのを待っている間に停止するのではなく、分岐が行われるかどうかを推測し、その推測に基づいて次の命令Yをフェッチします。後で推測が正しくないことが判明した場合(できればまれに)、システムはバックトラックして正しい選択で再開する必要があります。つまり、ステージAおよびその推測に基づいて後続のステージによってマシンの状態に加えられたすべての変更を元に戻し、すでにパイプラインにあるXに続く命令をフラッシュし、ステージAを次のように再起動する必要があります。正しい命令ポインタこの分岐予測戦略は、投機的実行の特殊なケースです。

コストと欠点

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

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

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

新技術

確かに、近年、アプリケーションとその基盤となるハードウェアに対する要求は非常に大きくなっています。たとえば、データを行ごとにトロールする単一ノードアプリケーションを使用してパイプラインを構築することは、ビッグデータの量と種類によってはもはや実現可能ではありません。ただし、 Hadoopや最近のApache Sparkなどのデータ分析エンジンの出現により、大規模なデータセットを複数の処理ノードに分散できるようになり、アプリケーションはこれまで考えられていた数百倍の効率の高さに到達できるようになりました。今日のこの効果は、このように分散処理を使用する中堅PCでさえ、ビッグデータパイプラインの構築と実行を処理できることです。[3]


も参照してください

参考文献

  1. ^ Dativaによって公開されたデータパイプライン開発、2018年5月24日取得
  2. ^ O. Hauck; ソリンA.ハス; M.ガーグ(1999)。二相非同期波動パイプラインとその2D-DCTへの応用セマンティックスカラーpp。219–228。土井10.1109 /ASYNC.1999.761536ISBN 0-7695-0031-5S2CID206515615  _ 2019年9月14日取得
  3. ^ データパイプラインとは何ですか?Data Pipelinesが発行、2021年3月11日取得

参考文献