命令パイプライン
命令パイプライン（めいれいパイプライン、英: Instruction pipeline）は、コンピュータなどのデジタル電子機器で命令スループット（単位時間当たりに実行できる命令数）を向上させる設計技法の1つで、命令レベルの並列性を高める1技法。
命令パイプラインのあるプロセッサは、命令の処理を独立して実行できる工程（ステージ）に分割する。各工程は、前の工程の出力を自身の入力とし、自身の出力を次の工程の入力とするように相互接続されている。このような構成で各工程を並列化し、全体としての処理時間を大幅に削減する。
概要
編集基本的な考え方は、コンピュータの命令の処理を一連の独立した工程に分割し、各工程の処理結果を記憶するように構成することである。そうすることで、コンピュータの制御装置は最も時間のかかる工程を基準として命令を演算装置に送り込めるようになり、全工程を一体として処理するよりも高速化できる。パイプラインとは、各工程が同時にデータを運んでいて、各工程が次の工程をパイプのように接続されていることを意味する。
命令パイプラインの起源は、ILLIAC II プロジェクトまたは IBM Stretch プロジェクトにあると言われている。IBM Stretch プロジェクトでは、「フェッチ (fetch)」、「デコード (decode)」、「実行 (execute)」という用語が生まれ、それが一般化した。
最近のCPUは、クロック信号で駆動される。CPU内部には論理回路とメモリ（フリップフロップ）が存在する。クロック信号が入ってくると、フリップフロップが新たな値を受け付け、論理回路でその新たな値のデコードに一定の時間がかかる。次のクロックパルスが入ってくると、フリップフロップは再び新たな値を受け付け、同様に処理が進む。論理回路を小さな部分に分割し、それぞれの間にフリップフロップを挟むことで、各論理回路が結果を出すのにかかる時間を削減できる。これにより、クロック周期も短縮できる。例えば、RISCのパイプラインは次の5段階に分割されており、それぞれの間にフリップフロップがある。
- 命令フェッチ
- 命令デコードとレジスタフェッチ
- 実行
- メモリアクセス
- レジスタへのライトバック
プログラマやコンパイラがアセンブリ言語コードを書くとき、前提として命令は書かれた順序通りに逐次的に実行されるものと仮定している。つまり、ある命令が完了してから次の命令が実行されると考えている。しかし、命令パイプラインがある場合、この仮定は正しくないことがある。このため、プログラムの動作が不正になる場合がある。このような状況をパイプラインハザードと呼ぶ。ハザードには、データハザード、制御ハザード、構造ハザードの3種類があり、それぞれに対処する方法が異なる。
- データハザード
- データハザードは、命令がデータの読み書きに依存している場合に発生する問題である。具体的には、ある命令が次の命令に必要なデータをまだ生成していない状態で次の命令が実行されるときに起こる。これにより、次の命令が正しいデータを使えないため、プログラムの結果が予期しないものになる。データハザードには、読み取り後書き込みハザード（Read After Write）、書き込み後読み取りハザード（Write After Read）、書き込み後書き込みハザード（Write After Write）の3種類がある。
- 制御ハザード
- 制御ハザードは、分岐命令やジャンプ命令がパイプラインの流れに影響を与える場合に発生する問題である。分岐命令が実行されると、プログラムの実行経路が変わる可能性があるため、その後の命令がどこで実行されるかを予測する必要がある。分岐命令が解決されるまで、パイプラインは正しい命令を実行できないことがあり、これが制御ハザードとなる。制御ハザードに対処するためには、分岐予測や分岐遅延スロットなどの技術が用いられる。
- 構造ハザード
- 構造ハザードは、パイプライン内の複数の命令が同じハードウェアリソースを必要とする場合に発生する問題である。例えば、複数の命令が同時にメモリへのアクセスを必要とする場合などがこれに該当する。ハードウェアリソースが1つしかないとき、同時に要求された場合にはリソースの競合が生じる。これが構造ハザードであり、リソースの競合を解決するためには、ハードウェアのリソースを増やすか、命令の実行を遅延させる必要がある。
命令パイプラインは1つの命令の完了までの時間を短縮するのではなく、同時に処理する命令数を増やすことで、命令の完了と命令の完了の間の遅延を短縮しスループットを改善する。パイプラインのステージ数（段数）を増やせば、同時に処理する命令数が増え、命令の完了と完了の間の遅延時間も短くできる。現在生産されているマイクロプロセッサは最低でも2ステージのパイプラインを持つ（Atmel AVR や PIC は2段のパイプラインである）。Intel Pentium 4 プロセッサは20ステージのパイプラインを持つ。
長所と短所
編集パイプラインはあらゆる状況で有利というわけではなく、短所もある。
パイプラインの長所は次の通りである。
- プロセッサのサイクル時間を短縮でき、多くの場合で命令処理レートを向上させる。
- 加算器や乗算器などの組み合わせ論理回路は回路規模が大きいほど高速化できる。代わりにパイプラインを使うと、回路規模は小さいままで高速化できる。
パイプラインの短所は次の通りである。
- ハザードが発生するためコストがかかる。パイプラインのないプロセッサは一度に1つの命令しか実行できないため、ハザードが発生せず、制御を単純化でき、安価に製造できる。
- 命令レイテンシ（1命令の実行にかかる時間）がパイプラインがない場合に比べて若干長くなる。これは、パイプラインが各段の間にフリップフロップを挟んでいるためである。
- パイプラインのないプロセッサに比べて性能が予測しにくい。命令パイプラインのあるプロセッサはプログラム（命令の並び方）によって性能がばらつくためである。
例
編集汎用パイプライン
編集
右図は、一般化した次のような4段のパイプラインを示している。
- フェッチ (Fetch)：読み込み
- デコード (Decode)：解析、解読
- 実行 (Execute)
- ライトバック (Write-back)
図の上にある灰色の矩形には実行を待っている命令が並んでいる。下の灰色の矩形には実行が完了した命令が並んでいる。真ん中の矩形がパイプラインを表している。
実行は次のようになる。
| 時間（クロック） | 実行内容 |
|---|---|
| 0 | 4つの命令が実行されるのを待っている。 |
| 1 |
|
| 2 |
|
| 3 |
|
| 4 |
|
| 5 |
|
| 6 |
|
| 7 |
|
| 8 |
|
| 9 | 全命令を実行した。 |
バブル
編集
実行中に何らかの中断が発生すると、パイプラインに「バブル (bubble)」と呼ばれる何もしない部分が生じる。右の図では、サイクル2で紫の命令のフェッチに遅延が生じ、サイクル3のデコードステージにバブルが生じている。紫より後の命令は全て1クロックサイクルだけ遅延するが、紫の命令より前の命令は普通に処理が続行される。
上の図と比べると、バブルが生じたことによって実行にかかるクロックサイクル数が7から8に増えている。
バブルはストールと似ており、各ステージでは何もしない。ただし、NOP命令をバブルの部分に挟むとバブルを消すことができる。
具体例
編集概念を明確化するため、3ステージの理論的なパイプラインを想定する。
| ステージ | 意味 |
|---|---|
| Load | 命令をメモリから読み込む。 |
| Execute | 命令を実行する。 |
| Store | 結果をメモリやレジスタに格納する。 |
そして、アセンブリ言語の以下のような擬似コードを実行する。
LOAD #40, A ; 40 を A にロード
MOVE A, B ; A を B にコピー
ADD #20, B ; 20 を B に加算
STORE B, 0x300 ; B をメモリセル 0x300 に格納
以下にその実行過程を示す。
| Load | Execute | Store |
|---|---|---|
| LOAD |
LOAD 命令がメモリからフェッチされる。
| Load | Execute | Store |
|---|---|---|
| MOVE | LOAD |
LOAD命令を実行し、同時にMOVE命令をメモリからフェッチする。
| Load | Execute | Store |
|---|---|---|
| ADD | MOVE | LOAD |
LOAD命令はStoreステージにあり、その結果（40という数値）はレジスタAに格納される。同時にMOVE命令が実行されようとしている。AからBに内容を移す命令であるため、直前のLOAD命令の完了を待つ必要がある。このときフォワーディングという技法を使う。すなわち、LOAD命令でAに格納すべき値はExecuteステージで既に求められ、ステージ間のフリップフロップにある。そこでMOVE命令はExecuteステージの入力として前の命令のExecuteステージの結果を直接利用する。これがフォワーディングである。
| Load | Execute | Store |
|---|---|---|
| STORE | ADD | MOVE |
STORE命令がロードされ、MOVE命令は完了するところで、ADD命令を計算中である。ADD命令も同様にフォワーディングによって前の命令のExecuteステージの結果を利用する。
このように続いていく。この例でも明らかなように、命令には別の命令の結果に依存しているものがある。複数の命令がオペランドとしてある位置（メモリ、レジスタ）を参照している場合、それが入力であれ出力であれ、プログラム上の順序と異なる順序で実行すると、上述のようにハザードが発生する。ハザードが発生するのを防ぐ技法や、発生したハザードに対処する技法がいくつか確立されている。
複雑化
編集プロセッサの命令パイプラインは以下のような長さがある。
- インテル P6マイクロアーキテクチャ（Pentium III） - 11段
- インテル NetBurstマイクロアーキテクチャ（Pentium 4） - 20段、Prescottは31段
- インテル P6マイクロアーキテクチャ Yonah （Intel Core） - 13段
- インテル Coreマイクロアーキテクチャ Merom （Intel Core 2） - 14段
- インテル Nehalemマイクロアーキテクチャ（第1世代Core i） - 16段
- インテル Sandy Bridgeマイクロアーキテクチャ（第2世代Core i） - 16段、μOp Cacheアクセス時は18段
- ARM Cortex-A5 - 9段
- ARM Cortex-A8 - 13段
- ARM Cortex-A9 - 9〜12段
- ARM Cortex-A15 - 15段（整数）、24段（浮動小数点数やNEON）
- Xelerator X10q - 1000段以上[1]。
パイプラインステージが少ない実装では、一つのステージに一つの実行ユニットが対応しているが、一つの実行ユニットを細分化して次々に命令を送り込むスーパーパイプラインがある。たとえば、前節で示した3段のパイプラインそれぞれを2つに分割して6段として、Loadステージに注目すると、命令が供給されたらそれを途中までロードして次のLoadステージに供給する。同時に次の命令をロードする。その間、ふたつ目のLoadでは最初のLoadの続きを実行している。結果的に、2つの命令が同時にロードされていることになる。
パイプラインが長くなると、プログラム上の分岐が発生したときに不利であり、パイプライン全体をフラッシュする必要があるが、分岐予測によってある程度対処できる。分岐予測が不十分であれば、状況は悪化する。高性能計算などの特定分野では、滅多に分岐しないプログラムを書くことができ、パイプラインが長いほど性能向上が期待できる。分岐が頻繁に発生する場合、最も分岐しそうな方向の命令をパイプラインに供給することで、分岐予測の失敗によるパイプラインのフラッシュで生じる性能損失を低減できる。gcov などを使ってコード網羅率を分析する技法により、個々の条件分岐がどういう頻度で分岐するかを調べることができるが、そのような分析は最適化の最後の手段である。
実行コードに多数の条件分岐命令があると、パイプラインによるスループット向上は望めない。プロセッサが次に実行すべき命令を知ることができないため、条件分岐命令を実行して分岐先が決まるまで、パイプラインは空（バブル）になる。分岐先の計算が完了すると、次に実行すべき命令が決まり、パイプラインが再び機能するようになる。極端な場合、パイプラインの1ステージ以外全てのステージが空（バブル）になるなら、パイプラインのないプロセッサと性能に大差ない状況になり、むしろパイプラインのないプロセッサよりも性能は低下する（ステージ間のオーバーヘッドがあるため）。
命令パイプラインでは、プロセッサが読み込んだ命令は即座に実行されるわけではない。そのため、その時点のプログラムカウンタに非常に近い命令を書き換えても、既にその命令がプロセッサ内に取り込まれていて、効果を発揮しないことがある。キャッシュメモリがこの現象をさらに悪化させる。ただし、これが問題になるのは自己書き換えコードだけである。
歴史
編集1961年のIBM 7030(Stretch)は、マイクロプログラム方式でパイプラインと分岐予測を使用している[2]。以後のメインフレームの大半でも使用されている。
1970年代に、ベクトル計算機にはじまる、今日の高性能計算に直接つながるマシンの開発が始まった。ハイエンドの高性能計算マシンでは、特別な設備やコア冷却を必要とした。初期の代表的なスーパーコンピュータにはCDC社の CDC 6600 や CDC 7600 があるが、その中心的な設計者のシーモア・クレイは後に CDC を辞めてクレイ社を設立した。クレイは X-MP 系列のスーパーコンピュータを開発し、乗算と加減算の両方にパイプラインを使用した。後に Star Technologies 社がパイプラインを別レベルの並列処理に使用した。これはいくつかのパイプライン化された機能が並列的に稼働するもので、同社技術者の Roger Chen が開発した。
現在ではパイプラインは、パーソナルコンピュータ用の大多数のマイクロプロセッサをはじめ、組込み用プロセッサですら一部（特殊な割込み応答性能を要求される場合など）を除き使われている。
関連項目
編集脚注
編集- ^ Best Extrime Processor: Xelerated X10q at Microprocessor Report
- ^ IBM Stretch (7030) -- Aggressive Uniprocessor Parallelism