分岐予測

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

コンピュータ・アーキテクチャにおける分岐予測（ぶんきよそく、Branch Prediction、ブランチプレディクタ）とは、プログラム実行の流れの中で条件分岐命令が分岐するかしないかを予測することにより、パイプライン処理の効果を可能な限り維持し、性能を高めるためのCPU内の機能である。

目次

[編集] 概要

パイプライン処理プロセッサでは、パイプラインを途切れさせないようにするために命令を次々にフェッチする必要がある。しかしプログラムに分岐がある場合は次の命令は未決定のため、本来はフェッチが待たされ、パイプラインの効果が低下し、性能劣化（スループット低下）を招いてしまう。

この性能劣化を減らすため、現代のCPUは多かれ少なかれ分岐予測を行っている。予測が当たった場合はフェッチが有効となりパイプラインの効果が維持でき、予測が外れた場合はフェッチした命令を破棄して正しい分岐先の命令を再フェッチするため性能損失（オーバーヘッド）が発生する。しかし実際のプログラムの大半では、ループ処理や例外処理など各分岐先への分岐比率は偏りが大きいため、分岐予測によるメリットがデメリットを上回ることが多い。つまり分岐予測の的中率は、使用するアプリケーションと、分岐予測に採用した技法次第である。また、どこまで精緻な予測を行うべきかは、デメリット（CPU実装コスト、分岐予測処理のオーバーヘッド）とメリット（期待されるスループット向上）とのバランスとなる。

特にスーパースケーラ型プロセッサでは、パイプラインが複数となり、ある分岐予測結果が他のパイプラインの処理にも影響を及ぼしうるため、分岐予測は複雑となり重要である。

分岐予測は分岐先予測と同じではない。分岐予測は条件分岐で分岐するかどうかを予測するが、分岐先予測は分岐アドレスが実際に決定される前にそれを推察するものである。

歴史的にはパイプラインも分岐予測も、マイクロプログラム方式のCISCプロセッサで生まれ発達した技術であり、RISCを含むマイクロプロセッサでの分岐予測は最初は簡単なものであった。なお「マイクロプログラム方式のプロセッサは分岐予測を必要としなかった」という説があるが間違いである。一般論としてRISCの方がパイプラインの効果が発揮しやすい（逆に言えばパイプラインが乱れると性能劣化が大きい）ため、結果的に分岐予測が重要というだけである。

[編集] 歴史

分岐予測の最初は1961年のIBM 7030(Stretch)と言われ、マイクロプログラム方式でパイプラインを使っている[1]。以後のIBMのメインフレームの上位機種も分岐予測を採用している。

VAX 9000もマイクロプログラム方式でパイプラインを使っていたが、何らかの分岐予測を行っていたと思われる[2]。

最初の商用RISCプロセッサであるMIPSとSPARCは単純な「常に分岐しない]という分岐予測だけをした。これらは分岐遅延スロットを使い、1サイクルに1命令をフェッチするだけだったため、性能損失は全くなかった。後にR4000でも同様の予測方式だったが、分岐命令の評価に4サイクルかかったため分岐が発生すると2サイクルを無駄にすることになった。

分岐予測はインテル Pentium、DEC Alpha 21064、MIPS R8000、IBM POWERのようなパイプライン化されたスーパースケーラプロセッサでは重要な問題となった。これらのプロセッサは単純な1ビットあるいは2レベル分岐予測を使用している。R10000 は2レベル分岐予測を採用した初期のプロセッサのひとつである。

DEC Alpha EV6 [3]は、次ライン分岐予測を基本とし、局所分岐予測と広域分岐予測を 2レベル分岐予測で統合した分岐予測で上書きを行う。Alpha EV8(後に設計段階で開発中止)では分岐予測が失敗した場合に最低でも14サイクルかかった。

AMD K8 は2レベル分岐予測と広域分岐予測を統合しており、統合時の選択には別の2レベル分岐予測を使用している。このプロセッサは、ECCとして使われていた二次キャッシュ内のビット群を分岐予測に代用する。結果として分岐予測テーブルとして大容量を使用可能となり、キャッシュに関してはECCではなくパリティビットを使用することになる。キャッシュエラー（ECCエラーやパリティエラー）が発生したらいずれにしてもそのキャッシュラインを無効化してメモリから読み直すので、この選択は非常に効果的と思われる。

[編集] 技法

[編集] 単純予測

SPARCとMIPS（最初の2つの商用RISCアーキテクチャ）で初期に実施された分岐予測は単純なものだった。それは、常に分岐しないと予測して命令順に実行を行おうとするものである。実際に分岐すると判明した時点（分岐命令の解釈フェーズ）で不連続なアドレスへの分岐を準備する。

これらのCPUはデコード段階で分岐命令を評価し、1サイクルで命令をフェッチする。従って分岐アドレスの命令をフェッチするには2サイクルかかり、その間にどうしても分岐命令の次の命令をフェッチしてしまう。これを有効利用するために、これらのアーキテクチャでは分岐遅延スロットを定義した。

[編集] 静的予測

静的予測方式では、プログラムの流れる方向とは逆行する分岐命令をループの最後にある分岐と見なして、分岐する（可能性大）と予測する。逆にプログラムの流れる方向に分岐する命令はループからの脱出や例外的な処理と見なして、分岐しない（可能性大）と予測する。

この方式では、ループ実行の最後の分岐（つまりループの正常な終了）で予測を誤る。

静的予測は、動的分岐予測を使用するプロセッサの予備の技術（動的予測のためのどのような情報もない時の予備手段）として使われる。モトローラMPC7450 (G4e)とインテルPentium 4はこの技術を使っている[4]。

また、静的予測方式には、何らかの静的な分岐予測情報（分岐命令に付与されたヒントビット等）に基づいて、分岐する／分岐しないを予測する方式もある。

[編集] 次ライン予測

いくつかのスーパースケーラプロセッサ (MIPS R8000, DEC Alpha EV6/EV8) では、一次命令キャッシュの各ライン毎に次に実行すべきキャッシュラインへのポインタを持つ。この次ライン予測は分岐予測だけでなく分岐先予測も兼ねているので、他の分岐予測方式と単純に比較することはできない。

次ライン予測は位置合わせされた命令グループ（2個、4個、8個の命令）を示すので、分岐先は通常その先頭の命令ではない。単純に分岐先が一様に分布すると仮定すれば、使われない命令の平均は、0.5個、1.5個、3.5個となる。また、分岐命令もキャッシュラインの最後とは限らないので、こちらも使われない命令として0.5個、1.5個、3.5個が捨てられる。

一般に命令はキャッシュライン単位にキャッシュに取り込まれるが、次ライン予測が特殊なのは、予測結果に従って次ラインの先頭からフェッチし、分岐命令の評価結果に従って、フェッチ済みの命令を捨てることにある。

[編集] 2レベル分岐予測

2レベル分岐予測は2ビットの飽和カウンターのテーブルを持ち、そのテーブルは命令アドレスの最下位桁ビット群によってインデックス付けされる。命令キャッシュとは異なり、2レベル分岐予測のテーブルはタグを持っていない。従ってテーブルの各エントリーは異なる複数の分岐命令に対応する可能性がある(これを分岐妨害とか分岐の別名と呼ぶ)。複数の分岐命令に対応したカウンターは正しい予測をしない。各カウンターは以下のような4つの状態を表す。

  • 0b11：分岐する（可能性大）：Strongly taken
  • 0b10：分岐する（可能性小）：Weakly taken
  • 0b01：分岐しない（可能性小）：Weakly not taken
  • 0b00：分岐しない（可能性大）：Strongly not taken

分岐命令が評価される際に対応するカウンターが更新される。分岐しない場合、対応するカウンターはデクリメントされ、「分岐しない（可能性大）」の方向に状態が移行する。

2ビット方式の利点は、1ビット方式よりも予測の誤りが少なくなることである。

1ビット方式では、２度目以降のループ処理では、ループの最初回と最後回の分岐時に予測を誤る。 2ビット方式では、２度目以降のループ処理では、ループの最後回の分岐時にだけ予測を誤る。

ほとんど常に分岐する命令で分岐しない場合、1ビット方式では2回誤予測する（一度分岐しなかった場合に1ビット方式では「分岐しない」とされてしまうため）が、2ビット方式では誤予測は1回である（ただし、Weakly（可能性小）の際の動作によって性能が変化する）。

全ての分岐命令がそれぞれ独立したカウンターに対応している場合、SPEC89のベンチマークを実行したときの2レベル予測の予測性能は最終的に93.5%となる（一般に分岐予測は繰り返し実行されることを前提としており、あるプログラムを実行開始した直後の予測成功確率はもっと低い）。

2レベルカウンターテーブルが命令アドレスのビット群によってインデックス付けされるため、これをキャッシュ化して命令フェッチと同時にテーブルの内容も取ってくることが可能である。さらにコンパイル時の予測値を実行ファイルに格納すれば、最初の実行のときからある程度の正しい予測を行うことが可能となる。

[編集] 局所分岐予測

2レベル分岐予測はすべてのループの終了を誤予測する。毎回ループ回数が同じになる傾向があるループについては、もっとよい予測方法が存在する。

局所分岐予測では2つのテーブルを使用する。ひとつは局所分岐履歴テーブルである。これは、分岐命令のアドレスの最下位桁ビット群によってインデックス付けされ、最近の n回の分岐命令実行の履歴（分岐したかしないか）を記録する。

もうひとつのテーブルはパターン履歴テーブルである。2レベル予測のように、このテーブルは2レベルカウンターから構成される。ただしそのインデックスは上記の局所分岐履歴テーブルから生成される。分岐を予測するために分岐履歴を参照し、その内容から 2レベルカウンターを参照して予測を行う。

SPEC89のベンチマークで、非常に大型の局所分岐予測を行うと正しい予測は最終的に97.1%となる。

局所分岐予測は2つのテーブル参照をしなければならないため、2レベル分岐予測よりも重い。高速さを求めた実装では、2レベルカウンターを別途用意して2レベル分岐予測と組み合わせて使用する。これらのテーブルは冗長ではなく、各カウンターはひとつの分岐命令のふるまいを格納することを前提としている。

[編集] 広域分岐予測

広域分岐予測は多くの分岐命令のふるまいが最近の他の分岐命令のふるまいと強く相関するという事実を利用する。ひとつのシフトレジスタで最近実行した分岐命令のふるまいの履歴を保持し、この内容を2レベルカウンターテーブルへのインデックス値として使用する。この方式自体はテーブルが大きければ2レベル分岐予測よりよい結果を示すが、局所分岐予測には敵わない。

ひとつのシフトレジスタではなく、命令アドレスの数ビットをインデックスとしたシフトレジスタのテーブルを使う方式を gselect分岐予測と呼ぶ。gselectはテーブルの小さい局所分岐予測よりもよい結果を示し、局所分岐予測はテーブルが1Kバイト以上になってもあまり予測結果が向上しない。

分岐命令アドレスを広域履歴とXORすると gselect よりも若干効率がよくなる。これをgshareと呼び、テーブルサイズが 256バイト以上ならばgselectよりもよい結果となる。

SPEC89のベンチマークで、非常に大型のgshare分岐予測値を実施すると、正しい予測は最終的に96.6%となる（大型の局所分岐予測よりほんの少し悪い）。

gselectとgshareは分岐命令当たりのテーブル参照が一回で済むので、局所分岐予測よりも軽い。2レベル分岐予測と併用してテーブル参照と命令フェッチを並行して行うこともできる。

[編集] 統合分岐予測

Scott McFarling は 1993年の論文で統合分岐予測 (Combined branch prediction) を提案した[5]。この方式は2レベル分岐予測と同じくらい正確で、広域分岐予測と同じくらい高速である。

統合分岐予測は並列に3つの予測値を使う。それは 2レベル分岐予測とgshare分岐予測と、分岐命令毎にその二つのどちらを選択するかを示す2レベルカウンターテーブルを使った予測である。最後のものを選択分岐予測と呼び、このテーブルのインデックスは命令アドレスの最上位桁ビット群を使用する。このテーブルは2レベル分岐予測とgshare分岐予測が食い違ったときに更新され、どちらが正しかったかを示す。

SPEC89のベンチマークで、統合分岐予測はほぼ局所分岐予測と同じ成績となる。

分岐予測を統合する他の方法として、例えば3種類の分岐予測を使って多数決を行うことが考えられる。実際、インテルはそのような方式を採用している。

gshareのような分岐予測方法では、ひとつの分岐命令に対応するテーブルエントリが複数存在することになる。それは逆に同じエントリで複数の分岐命令が競合することを意味し、結果として分岐予測精度を悪化させる。従って、複数の分岐予測手法を統合する際には、このエントリ競合パターンがそれぞれの手法で異なっているように設計することが重要である。そうすれば、どれかひとつは競合していないエントリで予測することができる確率が高まる。このような考え方で統合された分岐予測をgskew分岐予測と呼ぶ。この名称はskewed cacheからの類推から来ている（skewed cacheとは連想度が複数のキャッシュについて、ウェイ毎に別のハッシュ関数を用いる手法）。

[編集] 合意予測

パターン履歴テーブルの中で破壊的なエントリ競合を減らす別の技術として「合意予測 (agree predictor)」がある。2レベル分岐予測や分岐命令にヒントビットを付与することで若干静的な予測を基本として行う。そして、別の分岐予測機構（例えばgskew）でも予測を行うが、それは分岐するかしないかではなく、基本の予測に合意するかしないかを予測する。

意図しているのは、gskew分岐予測による予測に対して静的なバイアスを与えることである。容量の小さいパターン履歴テーブルでの競合を削減するのに有効であるが、基本となる静的予測の精度に性能が依存する。

合意予測は統合分岐予測と組み合わせるとうまく機能する。というのも統合分岐予測では一般に2レベル分岐予測を内包しており、それを基本の予測として使用できるからである。ただし分岐する/しないの傾向が特にない分岐命令についてはうまく機能しない（基本の予測結果が一定しないため）。従って、合意予測は3種類の分岐予測の組合せの一部として使用するのが最善である。

[編集] 分岐予測の上書き

EV6とEV8コアは、高速な（1サイクル動作の）次ライン分岐予測を実施している。しかし次ライン分岐予測は大雑把であり、命令単位での予測はコストが高くつく。そこでこれらのプロセッサでは2サイクルかかる別の分岐予測機構を用意し、次ライン分岐予測の結果を上書きするようになっている。これによって最悪でも1命令だけフェッチした命令を捨てるだけでよくなり、性能が向上する。

4命令以上を同時にフェッチすると、複数の分岐命令が含まれる可能性がある。そのため、上書きに際しては次の命令が分岐するかしないかを予測する必要がある。通常、分岐命令を評価して分岐アドレスを求める。

[編集] ニューラル分岐予測

ニューラル分岐予測（Neural Branch Prediciton）は、ルーマニアの Lucian Vintan が論文 "Towards a High Performance Neural Branch Predictor" で最初に提唱した (Proceedings of The International Joint Conference on Neural Networks - IJCNN '99, Washington DC, USA, 1999)。その後、アメリカのラトガース大学で Daniel Jimenez が研究を進めた。2001年、ハードウェア実装が可能な最初のパーセプトロン予測器 (perceptron predictor) が登場した。

ニューラル分岐予測の主な利点は、線形なリソース量の増大だけで長い履歴を扱える点である。古典的な分岐予測では、履歴量の増大はリソース量の指数関数的増大を招いていた。Jimenez は McFarling の統合分岐予測に対して 5.7% の向上が得られたことを報告している。

パーセプトロン分岐予測の問題は、レイテンシが大きいことである。様々な技法を凝らして高速化しても、深いパイプラインを持つマイクロアーキテクチャのクロックに比較すると、計算レイテンシが長い。インテルの Pentium 4 のパイプラインは20ステージであり、研究者は高速化の追求によって最高 52 ステージまで細分化が進むだろうと予測している[6]。

レイテンシを低減するため、Jimenez は2003年に fast-path neural predictor を提案した。これは、分岐命令のアドレスではなく、分岐経路によって重み付けする方式である。他にも同様の方式を提案している者が何人もいる（A. Seznec、M. Monchiero、Tarjan & Skadron、V. Desmet、Akkary et al など）。

ニューラル分岐予測はかなり見込みがあると考えられている。最先端の分岐予測機構の多くは、パーセプトロン分岐予測器を用いている（インテルの "Championship Branch Prediction Competition"[7] を参照）。インテルは既に IA-64 シミュレータにこのアイデアを実装している。

[編集] 脚注

  1. ^ IBM Stretch (7030) -- Aggressive Uniprocessor Parallelism
  2. ^ Micro-architecture of the VAX 9000
  3. ^ Design Tradeoffs for the Alpha EV8 Conditional Branch Predictor
  4. ^ ArsTechnica article on the Pentium 4.
  5. ^ Combining Branch Predictors - McFarling - 1993
  6. ^ Increasing processor performance by implementing deeper pipelines. Eric Sprangle, Doug Carmean.
  7. ^ http://camino.rutgers.edu/cbp2/

[編集] 外部リンク

"http://ja.wikipedia.org/wiki/%E5%88%86%E5%B2%90%E4%BA%88%E6%B8%AC" より作成