パイプライン処理

出典: フリー百科事典『ウィキペディア（Wikipedia）』

パイプライン処理（パイプラインしょり）とは、コンピュータ等の高速化技術の一つである。

以下、CPUの内部処理を説明するため、以下の略語を用いる。

IF (Instruction Fetch)

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

ID (Instruction Decode/register read)

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

EX (EXecution/address calculation)

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

MA (Memory Acess)

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

WB (Write Back)

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

目次 1 概要 2 パイプラインハザード 2.1 パイプラインハザードの種類 2.1.1 データ・ハザード 2.1.2 構造ハザード 2.1.3 制御ハザード 3 その他の応用例 4 ソフトウェア 5 関連項目

[編集] 概要

プロセッサが命令を実行するためには、命令解釈・演算・メモリアクセス等を行う必要があり、各々の処理をこなす回路のユニットが存在するが、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では20ステージを超える多段パイプラインを備えるものもある（スーパーパイプライン）。

ステージ数は多ければ多いほど並列処理できる命令が増えるが、処理結果が反映されるまで時間がかかる（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なキューを使って、ロックをかけずに、キューの読み書きをすることも多い。

[編集] 関連項目

• スーパースケーラ