パイプライン処理

ファイル:Pentium4superpipeline.png

Intel Pentium 4 の命令パイプライン

パイプライン処理（パイプラインしょり）とは、コンピュータ等において、処理要素を直列に連結し、ある要素の出力が次の要素の入力となるようにして、並行（必ずしも並列とは限らない）に処理させるという利用技術である。要素間になんらかのバッファを置くことが多い。

コンピュータ関連のパイプラインには、次のようなものがある。

命令パイプライン

プロセッサ内にあり、同じ回路で複数の命令をオーバーラップさせて実行する。回路は一般にステージに分割されており、命令デコード部、演算部、レジスタフェッチ部などがある。各ステージは1度に、ある1つの命令の処理のうち、自分が担当する部分を処理する。

グラフィックスパイプライン

コンピュータグラフィックス、特に3次元コンピュータグラフィックスにおいて必要とされる計算は、最初の三次元幾何の処理から最終結果の表示までが流れ作業で、また必要な計算量が膨大なため高速に行われることから、パイプラインとして扱われる。パーソナルコンピュータではビデオカードのGPUで行われている。

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

スーパースカラやスーパーパイプラインにより、複雑化した命令パイプラインを有効に働かせるためには、命令を並べる順番を工夫し、ハザードによるバブルの発生を回避しなければならない。ループ展開をともなったループの最適化で特に有用で、その手法をソフトウェアパイプラインと言う。

パイプ (コンピュータ)

複数個のプロセスについて、あるプロセスからの出力を別のプロセスの入力につなぐようにし、プロセスを協調して働かせる、というもの。UNIXのそれにより、単純でありながら大いに有用であることが示された。

概念と背景

ライン生産方式などパイプライン的なものは様々なところに存在する。自動車の組み立てを考えてみよう。流れ作業の一工程として、エンジンのシャーシへの設置、フードの設置、車輪の設置があり、この順番で実施されるとする。ラインの各工程には、1台の組み立て中の自動車だけがある。エンジンを設置し終えた自動車は、次にフードの設置工程に移され、エンジン設置用の機械設備は次の自動車に取り掛かることができる。最初の自動車はさらに車輪設置工程に進み、2台目の自動車はフード設置工程に進み、3台目の自動車がエンジン設置工程に進んでくる。エンジン設置に20分かかり、フード設置に5分、車輪設置に10分かかるとすると、一度に1台ずつ組み立てると3台組み立てるのに105分かかる。しかし、ライン生産方式では75分で3台の組み立てが完了する。その後も20分間隔で自動車が組み立てられていく。

コスト、欠点、利点

ライン生産方式の例で示したように、パイプライン処理は単一のデータの処理を高速化するわけではなく、データストリームの処理をする際のシステムのスループットを向上させるだけである。

パイプラインを長くすると、レイテンシは増大し、1つの信号がパイプの先から先まで到達するのに時間がかかるようになる。

パイプライン化されたシステムでは、あるステージが前のステージのリソース（回路、処理装置、メモリなど）を再利用できないため、一般に1つずつ処理するシステムよりも多くのリソースを必要とする。さらに言えば、パイプライン処理によって1つの命令の完了にかかる時間は増大する可能性がある。

設計上の考慮

パイプライン設計では、各ステージを釣り合わせることが重要である。上述の組み立てラインの例で言えば、エンジンの工程も車輪の工程も15分で済めば、スループットはさらに向上する。レイテンシはそれでも35分だが、15分に1台の間隔で自動車を生産できるようになる。

別の設計上の配慮すべき点として、ステージ間の適切なバッファの用意がある。ステージの処理時間が不定の場合や、パイプラインの途中でデータが生成されたり破壊されたりする場合には、バッファが特に重要である。

実装

バッファのある同期パイプライン

一般的なマイクロプロセッサは、クロック同期設計であり、バッファのある同期パイプラインを使っている。この場合のステージ間のバッファを「パイプラインレジスタ」と呼び、全体がクロックによって同期されている。クロックサイクルは、パイプラインの各ステージで最長の時間がかかる部分より長く設定する。それによって、前のステージの結果がパイプラインレジスタに書き込まれてから、次のステージがそれを利用して処理することができる。

バッファのある非同期パイプライン

非同期パイプラインは非同期回路で使う。その場合のパイプラインレジスタは非同期に駆動される。一般にステージ間で要求メッセージと応答メッセージをやり取りして処理を進める。例えば、あるステージで処理が完了したとき、次のステージから要求メッセージが来ていたら、応答メッセージを返し、前のステージには要求メッセージを送る。あるステージが応答メッセージを受け取ったら、入力レジスタから読み込むことができ、処理を開始できる。

バッファのある非同期パイプラインを使ったマイクロプロセッサの例としてAMULETがある。

バッファのないパイプライン

ステージ間にバッファのないパイプラインを「ウェーブパイプライン (wave pipeline)」と呼ぶ。その代わり、パイプラインの各ステージのレイテンシが釣り合うように設計されている。したがって、データはパイプライン上を波のように流れ、それぞれの波は可能な限り短く保たれる。

最大処理速度は、データを投入できる間隔で決まる。それより短い間隔でデータを投入すると、波が互いに干渉するように結果が不正になる。

命令パイプライン

テンプレート:Main 以下、CPUの内部処理を説明するため、以下の略語を用いる。

IF (Instruction Fetch)

命令を命令キャッシュから読み出す

ID (Instruction Decode/register read)

制御信号を生成し、レジスタ・ファイルをレジスタ指定子で参照する

EX (EXecution/address calculation)

数値の計算やロード・ストアのデータやアドレス・分岐先の計算を行う

MA (Memory Access)

ロード（メモリの読み出し）・ストア（メモリへの書き込み）を行う

WB (Write Back)

レジスタにデータを書き込む

概要

プロセッサが命令を実行するためには、命令解釈・演算・メモリアクセス等を行う必要があり、各々の処理をこなす回路のユニットが存在するが、1つの命令がこれら全てのステップを終えてから次の命令を実行する方式（逐次実行方式）では命令が現在いるステップ以外のユニットは仕事をしない。

時間	1	2	3	4	5	6	7	8	9	10
命令1	IF	ID	EX	MA	WB
命令2						IF	ID	EX	MA	WB

これらのユニットを有効利用するために、ユニット間にフリップフロップを挿入して分割し、クロック毎に各ユニットが独立して動作できるようにした上で次々に命令を投入・並列実行する方式をパイプライン処理と言う。これにより各ユニットのハードウェア資源を有効に活用することができ、処理速度が向上する。

時間	1	2	3	4	5	6	7	8	9	10
命令1	IF	ID	EX	MA	WB
命令2		IF	ID	EX	MA	WB
命令3			IF	ID	EX	MA	WB
命令4				IF	ID	EX	MA	WB
命令5					IF	ID	EX	MA	WB
命令6						IF	ID	EX	MA	WB

1. 最初のステージで命令を読み込む（フェッチする）。
2. 読み終えたら（ここで1クロックが経過）そのステージは命令を次のステージに移し、次の命令をフェッチする。その間、2番目のステージでは読み込まれた命令のデコードがはじまる。
3. それが終わると（さらに1クロックが経過）すべての命令を次のステージに移し、1番目のステージは次の命令をフェッチ、2番目のステージではデコードを行う。そして3番目のステージでは最初の命令の演算を行う。
4. すべての命令を次のステージに移す。3の行程に加えて4番目のステージでメモリアクセスが行われる。
5. 同様に5番目のステージで最初の命令の結果のストアが行われる。

あとは1 - 5の繰り返しである。

この項では5ステージ構成の基本的なパイプラインの構造をもとに説明するが、最新のCPUでは15ステージを超える多段パイプラインを備えるものもある（スーパーパイプライン）。

ステージ数は多ければ多いほど並列処理できる命令が増えるが、処理結果が反映されるまで時間がかかる（1命令を実行し終わるのに要すクロック数が増えるため）、パイプラインハザードが起こると初期化（やり直し）に時間がかかるというデメリットも持ち合わせている。一方、ステージ数が少ないパイプラインでは処理結果が反映されるまでの時間が短く、パイプラインハザードが起っても初期化が速い。

パイプラインハザード

パイプライン処理を行う場合にも、複数の命令同士が持つ依存関係から命令の投入を中断せざるを得ない状況が生じうるが、これをパイプラインハザードと呼ぶ。ハザードが発生すると処理速度の低下に繋がる。

パイプラインハザードの種類

データ・ハザード

処理するデータの依存関係に起因するハザードである。

時間	1	2	3	4	5	6	7	8	9	10
sub $2, $1, $3	IF	ID	EX	MA	WB
and $4, $2, $5		IF	ID	ID	ID	ID	EX	MA	WB
and $6, $7, $8			IF	IF	IF	IF	ID	EX	MA	WB

このような場合、2つ目の命令で用いられている変数$2は、1つ目の命令で演算の対象になっているため、1つ目の命令の処理が全て終わらなければ正しい結果を返すことができない。そのため、直前の命令が全て終了するまでパイプラインを止める必要が発生し、これをデータ・ハザードという。レジスタが問題になる場合はWB→IDで、メモリの場合はMA→MAという関係で発生する。

データ・ハザードを防止するためには、プログラムをコンパイルする際などに、プログラムの内容に影響のない範囲でCPUに送る命令の順序を調整して、データ・ハザードが起きにくいようにする必要がある。また、ハードウェアによって、データを書き込むのと同時にパイプラインに投入することによってデータ・ハザードを軽減する方法もある。

構造ハザード

ハードウェア的な資源の競合に起因するハザードである。

時間	1	2	3	4	5	6	7	8
命令1	IF	ID	EX	MA	WB
命令2		IF	ID	EX	MA	WB
命令3			IF	ID	EX	MA	WB
命令4				IF	ID	EX	MA	WB

WBとIDは、同一の部品（ハードウェア資源）を要求するため、資源の競合が発生してしまう。これが構造ハザードである。WBとIDを同時に実行することで発生する。通常構造ハザードは、関係するWBとIDの両ステージとも、比較的処理に要する時間が短いステージであるため、一つの時間単位をさらに2つに分けて、その前半にWB、後半にIDを実行することでハザードの発生を回避している。

制御ハザード（分岐ハザード）

制御の依存に起因するハザードである。

時間	1	2	3	4	5	6	7	8	9
beq $1, $2, label	IF	ID	EX	MA	WB
and $4, $2, $5					IF	ID	EX	MA	WB

分岐命令がある場合、結果によって次に実行するべき命令がわからないため、パイプラインを止めて次に実行すべき命令が判明するのを待たなければならない。これを制御ハザード、または分岐ハザードという。MA→IFのステージに関係する。

制御ハザードは、分岐命令がある限り逃れることのできないハザードである。しかし、その影響を小さくすることはできる。その方法が分岐予測である。現在のCPUでは、分岐命令があった場合、その結果がどちらかであると仮定（予測）して、以降の命令をあらかじめ実行しておく、という動作をしている。この場合、予測が当たっていればパイプラインのストール（停止）が実質的にないのと同じように実行できる。しかし予測が外れていた場合、先に演算していた内容を全て破棄して分岐命令の直後から演算をやり直さなければ行けないため、大幅なペナルティが発生することになる。

初期の分岐予測機能付きCPUでは分岐命令を常に条件式の結果がYESであると仮定して分岐予測を行っていたが、後に以前の結果を記憶しておいて、それを元に分岐予測をする方式に改められ、さらに、記憶に2ビットを与え、同じ結果が2回続けば予測先を変更するように改められた。現在においても分岐予測の精度向上は重要な課題の一つであり、各社ともに常に分岐予測の精度を向上させるための研究が進められている。

その他の応用例

時間的に隣り合うサイクルのステージが互いに独立した実装方式を採用した例としてimagination社のMetaがある。Metaは、最大で4つまでのハードウェアスレッドを実現している。4つの独立したプログラムカウンタを保持、時間的に隣り合うサイクルのステージに依存関係がないため、分岐命令実行ペナルティも存在しない。

ソフトウェアのアーキテクチャ

ソフトウェアに、パイプライン的な処理のパターンがある。スレッドを使うパターンに見られる。

一般に、オブジェクト指向の場合、情報が発生する側から情報を受け取る側に情報を渡すときは、Observer パターンを使う。パイプライン処理をオブジェクト指向で実装する場合も、普通のメソッド呼び出しではなく、Observer パターンで前のスレッドからデータを受け取り、受け取った側のスレッドでキューにデータをためる、というのが基本形の実装方法である。

前のスレッドと後ろのスレッドでスレッドの競合を避けるために、キューにロックをかけてからキューの読み書きをするのではなく、Lock-freeなキューを使って、ロックをかけずに、キューの読み書きをすることも多い。

関連項目

• スーパースケーラ
• スループット
• 並列コンピューティング
• 命令パイプライン
• グラフィックスパイプライン
• パイプ (コンピュータ)
• ジオメトリエンジン

参考文献

• "Parallel Programming in C with MPI and OpenMP" by Michael J. Quinn,McGraw-Hill Professional, 2004ar:أنابيب التجزئة