重なりによる分岐予測の干渉

1レベル予測も2レベル予測も条件分岐命令の下位アドレスビットだけを用いて条件分岐命令を識別するので、上位アドレスが異なるが下位アドレスが一致する複数の条件分岐命令を区別できない。

下位アドレスで数千命令をカバーしていれば、ループ内の条件分岐命令の下位アドレスが一致することは少ないのであるが、ループ内から関数呼び出しがあると、離れたアドレスに飛んでいくので、下位アドレスが一致して重なりが出てしまうというケースが発生する。これらの重なった条件分岐命令が比較的短い期間に実行されると、両者の履歴やカウントが入り混じって干渉してしまい、意図したような予測効果が得られなくなるという問題がある。

キャッシュのように、上位アドレスのタグを設けてタグマッチを行えば、このような重なりを除くことができるが、各エントリが2～4ビットのBHTやPHTに数十ビットのタグを付けるのでは、ハードウェアの増加量が大きく、本末転倒である。また、キャッシュでは別アドレスへのロード、ストアが入り混じると処理結果が誤ってしまうが、分岐予測の場合は、予測ミスが増えて性能が下がるという問題はあるが、処理結果が誤るという重大な問題は発生しない。したがって、タグを設けて厳密に重なりを排除するという構造にはなっていない。

ここで、面白い考え方がある。Intelの「Larrabee」のアーキテクトの一人であるEric Sprangle氏がRoss Technology(SPARCプロセサを開発していた)時代に考案したAgree Predictorというものである。

これまでの説明のように、カウンタをTakenで+1、Not Takenで-1とすると、一方がTakenが多く、もう一方がNot Takenが多いという2つの条件分岐命令の下位アドレスが一致して重なってしまうと、両者の予測がキャンセルしあってしまう。条件分岐1が85%の確率でTaken、条件分岐2が15%の確率でTakenとすると、両方の条件分岐が同方向に行かず、負の干渉が起こる確率は

0.85×0.85+0.15×0.15=0.745

となる。

一方、Agree Predictionでは、両者の分岐方向は確率の高い方と最初から予測(これを静的予測という)されており、これと一致(Agree)したか不一致(Disagree)かでカウンタの+1/-1を行う。このため、両方の条件分岐の一方がAgree、他方がDisagreeとなる確率は

0.85×0.15+0.15×0.85=0.255

であり、本来は関係のない2つの条件分岐命令であるが、影響が逆方向になる重なりの確率が約1/3に減少し、干渉の悪影響が減少する。つまり、Agree Predictorは、重なりを減らすのではなく、重なりはあるが、その影響を減らせばよいという逆転の発想である。

以前述べたがSPARC V9アーキテクチャでは、コンパイラが条件分岐命令に分岐のTaken、Not Taken予測を付けることができるので、コンパイラの静的予測との一致/不一致でカウンタを更新することができる。また、論文では、条件分岐命令に静的予測ビットを持たない命令アーキテクチャの場合は、命令キャッシュなどにビットを追加し、各条件分岐命令の最初の実行時の分岐方向を記憶して静的予測値として使っても効果が得られると書かれている。このSprangle氏のAgree Predictorの論文は1997年6月に開催されたアーキテクチャ関係ではトップレベルの学会であるISCA(International Symposium on Computer Architecture)で発表された。

また、HPのPA-RISCアーキテクチャもコンパイラが条件分岐命令に静的予測を付けられる命令形式を持っており、同年10月のMicroprocessor ForumでHPがPA-8500プロセサを発表した際に、このプロセサにAgree Predictorを使っていることを明らかにした。

この時点でCPUチップは完成かそれに近い状態であったので、当然、 2年位前には着想を得ていたはずであり、どちらが早かったかは定かではない。しかし、Sprangle氏と比べて、HPは外部発表が4カ月遅く、ちゃんとした学会の論文にもなっていないので、Agree Predictorは、歴史的にはSprangle氏の功績ということになる。開発が忙しいからと言って論文を書くのをサボるとこうなるという教訓のような話である。