「パイプライン」とは、日常生活でよく使用される概念です。たとえば、自動車工場の製造ラインがその例です。エンジンの取付け、ドアの取付け、車輪の取付けのようなそれぞれ専門の業務が、別々の独自のワークステーションによって実行されることがよくあります。ステーションでは、タスクを並列で、異なる車両ごとに実行します。1 台の車で 1 つのタスクが実行されると、次のステーションに移動します。タスクを完了するために必要な時間の違いには、「バッファリング」 (ステーション間のスペースに 1 台以上の車を保持) するか、次のステーションが使用可能になるまで「ストール」 (アップストリーム ステーションを一時的に停止) するか、その両方を実行して対応します。
たとえば、1 台の車を組み立てるのに、タスク A に 20 分、タスク B に 10 分、タスク C に 30 分かかるとします。この場合、3 つのタスクすべてが 1 つのステーションで実行されると、工場は 60 分ごとに 1 台の車を出力することになります。これが、3 つのステーションのパイプライン方式を使用すると、工場は最初の車を 60 分で出力し、その後は 30 分ごとに新しい車を出力します。この例で示すように、パイプライン処理によってレイテンシ (1 つのアイテムがシステム全体を通過する合計時間) が減少することはありませんが、システムのスループット (最初のアイテムの後に新しいアイテムが処理される速度) が増加します。
パイプライン処理のスループットは、最も遅い要素のスループットよりも良くはならないので、プログラマが作業とリソースをステージ間で分割して、すべてのプロセスが同じ時間でタスクを完了できるようにする必要があります。上記の車の組み立ての例で、3 つのタスク A、B、C がそれぞれ 20 分、10 分、30 分ではなく、20 分ずつかかるとすると、レイテンシは 60 分のままですが、新しい車は 30 分ではなく 20 分ごとにできあがります。次の図は、3 台の車の製造を担当する架空の製造ラインを示しています。A、B、C の各タスクに 20 分かかるとすると、直列型製造ラインでは 3 台の車を製造するのに 180 分かかりますが、パイプライン方式の製造ラインにすると、3 台の車を作り出すのにわずか 100 分ですみます。
最初の車の製造にかかる時間は 60 分で、これはパイプラインの「反復レイテンシ」と呼ばれます。最初の車が製造された後、次の 2 台の車の製造にはそれぞれ 20 分しかかかりません。これは、パイプラインの「開始間隔 (II)」と呼ばれます。3 台の車の製造にかかる全体的な時間は 100 分で、この時間はパイプラインの「合計レイテンシ」と呼ばれます。たとえば、レイテンシ = 反復レイテンシ + II * (アイテム数 - 1) となります。このため、II を改善すると、合計レイテンシは改善しますが、反復レイテンシは改善されません。プログラマの視点から見ると、パイプライン パラダイムはデザインの関数とループに適用できます。最初のセットアップ コストの後の理想的なスループットの目標は、II を 1 にすること、たとえば、最初のセットアップ遅延の後、出力がパイプラインの各サイクルで使用可能になるようにすることです。上記の例では、最初のセットアップ遅延が 60 分になった後、20 分ごとに車ができます。
パイプライン処理は、複数レベルの抽象化に適用できる、従来のマイクロレベルのアーキテクチャ最適化です。プロデューサー/コンシューマー パラダイムを使用したタスクレベルのパイプライン処理については、既に説明しました。この同じ概念が命令レベルにも該当します。これは実際には、プロデューサーとコンシューマーのパイプライン (およびストリーム) を満たして、ビジー状態に保つために重要です。プロデューサーとコンシューマーのパイプラインは、各タスクが高いレートでデータを生成/消費するために命令レベルのパイプライン処理 (ILP) が必要な場合にのみ、効率的になります。
パイプライン処理では、同じリソースを使用して同じ関数を徐々に実行するため、各タスクのレイテンシに関する完全な知識が必要となり、スタティック最適化とみなされます。このため、下位レベルの命令パイプライン手法はデータフロー タイプのネットワークには適用できません。このネットワークでは、タスクのレイテンシは入力データの関数であるため、不明にできます。次のセクションでは、さまざまなタイプのタスク並列処理をモデル化するために導入された 3 つの基本的なパラダイムを活用する方法について説明します。