分岐予測
ニューラル分岐予測(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.
ハイブリッド分岐予測 (hybrid branch prediction) は統合分岐予測 (combined branch prediction) とも呼ばれ、複数の分岐予測機構を実装したものである。最終的な予測は過去にどの予測器が最も成績がよかったかを記憶しているメタ予測器が決定するか、奇数個の予測器を使って多数決で予測を決定するものなどがある。
Scott McFarling は 1993年の論文で統合分岐予測 (Combined branch prediction) を提案した。
SPEC89のベンチマークで、統合分岐予測はほぼ局所分岐予測と同じ成績となる。
gshareのような分岐予測方法では、ひとつの分岐命令に対応するテーブルエントリが複数存在することになる。それは逆に同じエントリで複数の分岐命令が競合することを意味し、結果として分岐予測精度を悪化させる。従って、複数の分岐予測手法を統合する際には、このエントリ競合パターンがそれぞれの手法で異なっているように設計することが重要である。そうすれば、どれかひとつは競合していないエントリで予測することができる確率が高まる。このような考え方で統合された分岐予測をgskew分岐予測と呼ぶ。この名称は skewed cache からの類推から来ている(skewed cache とは連想度が複数のキャッシュについて、ウェイ毎に別のハッシュ関数を用いる手法)。
1960年代から1980年代までマイクロプログラム方式のプロセッサが主流で、1命令の実行に複数サイクルかかるため、分岐予測はそれほど重要ではなかった。しかし IBM 3090 以外にもマイクロプログラム方式で分岐予測を行う設計がいくつか存在した。
Burroughs B4900 はマイクロプログラム方式のCOBOLマシンで、1982年ごろリリースされた。パイプライン化されており、分岐予測も行う。B4900の分岐予測のための履歴情報は、プログラム実行中にメモリ上の命令に書き戻される。B4900では分岐命令の命令コード内の2ビットを分岐予測のための4状態を表すのに使っている。ハードウェアは特定の分岐命令の予測が外れた場合にメモリ上の命令を書き換えて予測状態を更新する。この方式で予測成功率は93%だった。
1989年に発表された VAX 9000 はマイクロプログラム方式でパイプラインを使っており、何らかの分岐予測を行っていた。
最初の商用RISCプロセッサであるMIPS(R2000とR3000)とSPARCは単純な「常に分岐しない」という分岐予測だけをした。これらは分岐遅延スロットを使い、1サイクルに1命令をフェッチするだけだったため、性能損失は全くなかった。後のR4000でも同様の予測方式だったが、分岐命令の評価に4サイクルかかったため分岐が発生すると2サイクルを無駄にすることになった。