命令パイプライン

命令パイプラインは、コンピュータなどのデジタル電子機器で命令スループットを向上させる設計技法の1つで、命令レベルの並列性を高める1技法。

命令パイプラインのあるプロセッサは、命令の処理を独立して実行できる工程に分割する。各工程は、前の工程の出力を自身の入力とし、自身の出力を次の工程の入力とするように相互接続されている。このような構成で各工程を並列化し、全体としての処理時間を大幅に削減する。

1. 概要
-----

基本的な考え方は、コンピュータの命令の処理を一連の独立した工程に分割し、各工程の処理結果を記憶するように構成することである。そうすることで、コンピュータの制御装置は最も時間のかかる工程を基準として命令を演算装置に送り込めるようになり、全工程を一体として処理するよりも高速化できる。パイプラインとは、各工程が同時にデータを運んでいて、各工程が次の工程をパイプのように接続されていることを意味する。

命令パイプラインの起源は、ILLIAC II プロジェクトか IBM Stretch プロジェクトと言われている。IBM Stretch プロジェクトでは、「フェッチ 」、「デコード 」、「実行 」という用語が生まれ、それが一般化した。

最近のCPUは、クロック信号で駆動される。CPU内部には論理回路とメモリがある。クロック信号が入っていくると、フリップフロップが新たな値を受け付け、論理回路でその新たな値のデコードにある程度の時間がかかる。次のクロックパルスが入ってくると、フリップフロップはまた新たな値を受け付け、同様に処理される。論理回路を小さな部分に分割し、それぞれの間にフリップフロップを挟むようにすると、各論理回路が結果を出すのにかかる時間を削減できる。そうすることで、クロック周期も縮小することができる。例えば、RISCのパイプラインは次の5段階に分割されていて、それぞれの間にフリップフロップがある。

命令フェッチ
命令デコードとレジスタフェッチ
実行
メモリアクセス
レジスタへのライトバックプログラマやコンパイラがアセンブリ言語コードを書くとき、前提として命令は書かれた順序通りに逐次的に実行されるものとしている。つまり、ある命令が完了してから次の命令が実行されると仮定している。この仮定は命令パイプラインがある場合は正しくない。このことでプログラムの動作が不正になる場合、そのような状況をパイプラインハザードと呼ぶ。ハザードに対処する方法は様々なものがある。

パイプラインを使わないアーキテクチャでは、CPUの一部が命令を処理している間、他の部分が何もしていないことになり、効率が悪い。命令パイプラインはそのような何もしていない時間やCPUの部分を完全に無くすことはできないが、各部分が同時並列で動作できるようにすることで、プログラムの実行を大幅に高速化する。

だが、全ての命令が前後の命令と独立しているわけではない。単純な命令パイプラインでも、命令の完了までには5段階を要する。最高性能を発揮するには、ある命令が完了しようとしているときに、後続の4つの命令を処理している必要がある。後続の4命令が先頭の命令の結果に依存している場合、パイプライン制御回路は依存関係が解決されるまでパイプラインにストールを挿入したり、クロックサイクルを無駄にさせる必要がある。幸い、フォワーディングなどの技法でストールさせる必要性を大幅に削減できる。1命令の処理にかかる時間が同じ場合、命令パイプラインのあるプロセッサとないプロセッサでは、理論上はパイプラインの段数倍の性能の違いがある。実際には、ほとんどのコードは理想的な実行ができない。

命令パイプラインは1つの命令の完了までの時間を短縮するのではなく、同時に処理する命令数を増やすことで、命令の完了と命令の完了の間の遅延を短縮しスループットを改善する。パイプラインのステージ数を増やせば、同時に処理する命令数が増え、命令の完了と完了の間の遅延時間も短くできる。現在生産されているマイクロプロセッサは最低でも2ステージのパイプラインになっている。Intel Pentium 4 プロセッサは20ステージのパイプラインになっている。

2. 長所と短所
--------

パイプラインはあらゆる状況で有利というわけではなく、短所もある。

パイプラインの長所は次の通りである。

プロセッサのサイクル時間を短縮でき、多くの場合で命令処理レートを向上させる。
加算器や乗算器などの組み合わせ論理回路は回路規模が大きいほど高速化できる。代わりにパイプラインを使うと、回路規模は小さいままで高速化できる。パイプラインの短所は次の通りである。

ハザードが発生するためコストがかかる。パイプラインのないプロセッサは一度に1つの命令しか実行できないため、ハザードが発生せず、制御を単純化でき、安価に製造できる。
命令レイテンシがパイプラインがない場合に比べて若干長くなる。これは、パイプラインが各段の間にフリップフロップを挟んでいるためである。
パイプラインのないプロセッサに比べて性能が予測しにくい。命令パイプラインのあるプロセッサはプログラムによって性能がばらつくためである。

3. 例
----

3.1. 汎用パイプライン
-------------

右図は、一般化した次のような4段のパイプラインを示している。

フェッチ ：読み込み
デコード ：解析、解読
実行 
ライトバック 図の上にある灰色の矩形には実行を待っている命令が並んでいる。下の灰色の矩形には実行が完了した命令が並んでいる。真ん中の矩形がパイプラインを表している。

実行は次のようになる。



3.1.1. バブル
----------

実行中に何らかの中断が発生すると、パイプラインに「バブル 」と呼ばれる何もしない部分が生じる。右の図では、サイクル2で紫の命令のフェッチに遅延が生じ、サイクル3のデコードステージにバブルが生じている。紫より後の命令は全て1クロックサイクルだけ遅延するが、紫の命令より前の命令は普通に処理が続行される。

上の図と比べると、バブルが生じたことによって実行にかかるクロックサイクル数が7から8に増えている。

バブルはストールと似ており、各ステージでは何もしない。ただし、NOP命令をバブルの部分に挟むとバブルを消すことができる。

3.2. 具体例
--------

概念を明確化するため、3ステージの理論的なパイプラインを想定する。

そして、アセンブリ言語の以下のような擬似コードを実行する。

LOAD #40, A ; 40 を A にロード MOVE A, B ; A を B にコピー ADD #20, B ; 20 を B に加算 STORE B, 0x300 ; B をメモリセル 0x300 に格納

以下にその実行過程を示す。

LOAD 命令がメモリからフェッチされる。

LOAD命令を実行し、同時にMOVE命令をメモリからフェッチする。

LOAD命令はStoreステージにあり、その結果はレジスタAに格納される。同時にMOVE命令が実行されようとしている。AからBに内容を移す命令であるため、直前のLOAD命令の完了を待つ必要がある。このときフォワーディングという技法を使う。すなわち、LOAD命令でAに格納すべき値はExecuteステージで既に求められ、ステージ間のフリップフロップにある。そこでMOVE命令はExecuteステージの入力として前の命令のExecuteステージの結果を直接利用する。これがフォワーディングである。

STORE命令がロードされ、MOVE命令は完了するところで、ADD命令を計算中である。ADD命令も同様にフォワーディングによって前の命令のExecuteステージの結果を利用する。

このように続いていく。この例でも明らかなように、命令には別の命令の結果に依存しているものがある。複数の命令がオペランドとしてある位置を参照している場合、それが入力であれ出力であれ、プログラム上の順序と異なる順序で実行すると、上述のようにハザードが発生する。ハザードが発生するのを防ぐ技法や、発生したハザードに対処する技法がいくつか確立されている。

4. 複雑化
------

プロセッサの命令パイプラインは以下のような長さがある。

インテル P6マイクロアーキテクチャ - 11段
インテル NetBurstマイクロアーキテクチャ - 20段、Prescottは31段
インテル P6マイクロアーキテクチャ Yonah - 13段
インテル Coreマイクロアーキテクチャ Merom - 14段
インテル Nehalemマイクロアーキテクチャ - 16段
インテル Sandy Bridgeマイクロアーキテクチャ - 16段、μOp Cacheアクセス時は18段
ARM Cortex-A5 - 9段
ARM Cortex-A8 - 13段
ARM Cortex-A9 - 9〜12段
ARM Cortex-A15 - 15段、24段
Xelerator X10q - 1000段以上。パイプラインステージが少ない実装では、一つのステージに一つの実行ユニットが対応しているが、一つの実行ユニットを細分化して次々に命令を送り込むスーパーパイプラインがある。たとえば、前節で示した3段のパイプラインそれぞれを2つに分割して6段として、Loadステージに注目すると、命令が供給されたらそれを途中までロードして次のLoadステージに供給する。同時に次の命令をロードする。その間、ふたつ目のLoadでは最初のLoadの続きを実行している。結果的に、2つの命令が同時にロードされていることになる。

パイプラインが長くなると、プログラム上の分岐が発生したときに不利であり、パイプライン全体をフラッシュする必要があるが、分岐予測によってある程度対処できる。分岐予測が不十分であれば、状況は悪化する。高性能計算などの特定分野では、滅多に分岐しないプログラムを書くことができ、パイプラインが長いほど性能向上が期待できる。分岐が頻繁に発生する場合、最も分岐しそうな方向の命令をパイプラインに供給することで、分岐予測の失敗によるパイプラインのフラッシュで生じる性能損失を低減できる。gcov などを使ってコード網羅率を分析する技法により、個々の条件分岐がどういう頻度で分岐するかを調べることができるが、そのような分析は最適化の最後の手段である。

実行コードに多数の条件分岐命令があると、パイプラインによるスループット向上は望めない。プロセッサが次に実行すべき命令を知ることができないため、条件分岐命令を実行して分岐先が決まるまで、パイプラインは空になる。分岐先の計算が完了すると、次に実行すべき命令が決まり、パイプラインが再び機能するようになる。極端な場合、パイプラインの1ステージ以外全てのステージが空になるなら、パイプラインのないプロセッサと性能に大差ない状況になり、むしろパイプラインのないプロセッサよりも性能は低下する。

命令パイプラインでは、プロセッサが読み込んだ命令は即座に実行されるわけではない。そのため、その時点のプログラムカウンタに非常に近い命令を書き換えても、既にその命令がプロセッサ内に取り込まれていて、効果を発揮しないことがある。キャッシュメモリがこの現象をさらに悪化させる。ただし、これが問題になるのは自己書き換えコードだけである。

5. 歴史
-----

1961年のIBM 7030は、マイクロプログラム方式でパイプラインと分岐予測を使用している。以後のメインフレームの大半でも使用されている。

1970年代に、ベクトル計算機にはじまる、今日の高性能計算に直接つながるマシンの開発が始まった。ハイエンドの高性能計算マシンでは、特別な設備やコア冷却を必要とした。初期の代表的なスーパーコンピュータにはCDC社の CDC 6600 や CDC 7600 があるが、その中心的な設計者のシーモア・クレイは後に CDC を辞めてクレイ社を設立した。クレイは X-MP 系列のスーパーコンピュータを開発し、乗算と加減算の両方にパイプラインを使用した。後に Star Technologies 社がパイプラインを別レベルの並列処理に使用した。これはいくつかのパイプライン化された機能が並列的に稼働するもので、同社技術者の Roger Chen が開発した。

現在ではパイプラインは、パーソナルコンピュータ用の大多数のマイクロプロセッサをはじめ、組込み用プロセッサですら一部を除き使われている。

6. 関連項目
-------

命令レジスタ
パイプライン処理
並列コンピューティング
分岐遅延スロット

7. 脚注
-----

8. 外部リンク
--------

[1]
[2]
[3]