CPUのさまざまな分岐予測技法について見ていきましょう。

本記事の内容は浦項工科大学校のCSED311の内容に基づき、
授業で扱われなかったいくつかの内容を追加して構成しました。

分岐予測

分岐予測とは、分岐の結果が確定する前に分岐をあらかじめ推測することで、 CPUパイプラインを止めずに命令を取得し続ける技法です。予測しなければならないのは 2つあります。分岐条件を満たしてtakenになるのかnot takenになるのか(方向予測)、そしてtakenであればどこへ飛ぶのか(目標アドレス予測)です。

分岐予測器はIF段階で次のサイクルに取得するアドレスを決定します。このときtakenと not takenのどちらのアドレスを取得するかは、分岐予測の実装に応じたさまざまな最適化手法を用いて決定します。

パイプラインの後半で実際の分岐結果が確認されます。ID段階またはEX段階で、「この命令は分岐であり、実際にはtakenなので目標アドレスへ飛ぶべきだった／not takenなので次の命令を取得すればよい」ということが分かります。

このとき分岐予測と実際の結果を比較します。分岐予測器がIFで選択したアドレスと実際の分岐結果が同じであれば、何事も起こりません。しかしもし分岐予測器が間違っていた場合、その間に誤って取得してしまった命令をパイプラインから無効化し、PCを正しいアドレスに戻して再度取得を始めます。

例えば以下のようなコードがあるとしましょう。

0x1000:  beq  x1, x2, TARGET   # 分岐
0x1004:  add  x3, x4, x5       # 分岐失敗(not taken)時に実行
0x1008:  sub  x6, x7, x8
...
TARGET (0x2000):
0x2000:  or   x9, x10, x11     # 分岐成功(taken)時に実行

CPUが0x1000のbeqをIF段階で取得した瞬間、分岐予測器が動作して「この分岐はnot takenだろう」と予測したと仮定してみましょう。すると次のサイクルでCPUは予測どおり0x1004のaddを取得し、その次には 0x1008のsubを取得します。分岐の結果を待たずにパイプラインが流れ続けます。

数サイクル後、beqがEX段階に到達し、実際の分岐結果が計算されます。

予測成功：実際にもnot takenだった場合、すでに取得して実行中のadd、 subはそのままでよいです。分岐による遅延はまったくありません。
予測失敗：実際にはtakenだった場合、addとsubは実行されてはならない命令です。この2つをパイプラインから無効化(flush)し、PCを0x2000に戻してorから再度取得を始めます。このとき破棄されたサイクル分の 分岐遅延ペナルティ(branch penalty) が発生します。

結局、分岐予測器の目標はこの「予測失敗」の場合を最小化して、パイプラインが止まる回数を減らすことです。

PC + 4予測

PC + 4予測は最も単純な分岐予測方式です。分岐を無条件にnot takenと予測し、分岐命令の次のサイクルにもそのままPC + 4を取得します。別途の予測ハードウェアがまったく不要であるという利点があります。

問題は正確度です。実際のプログラムでは分岐の約60〜70%がtakenであることが知られています。特にループを構成する後方(backward)分岐はほとんど takenだからです。したがってalways not taken予測のper-branch正確度はおおよそ**30〜40%**程度に過ぎません。コイン投げよりも少し悪いわけです。

データハザードがなく、命令の20%が分岐で、分岐の70%程度がtakenであるコードを仮定してみましょう。PC + 4予測はすべての分岐をnot takenと予測するため、takenの分岐でのみ予測が失敗します。したがって全体の命令のうち予測が外れる割合は

$$ P_{\text{miss}} = 0.20 \times 0.70 = 0.14 $$

つまり約14%、裏を返せば予測が当たる確率は約**86%**です。

性能はIPC(Instructions Per Cycle)で測定できます。理想的な場合IPCは 1ですが、予測失敗による平均ストールサイクル分だけ下がります。

$$ \text{IPC} = \frac{1}{1 + P_{\text{miss}} \times \text{penalty}} $$

ここで分岐遅延ペナルティは、分岐がパイプラインのどの段階で決定されるかによって変わります。分岐が決定される段階が後ろに行くほど、その間にIFで取得してしまった命令をより多く捨てなければならないからです。

分岐がMEM段階で決定される場合、IFからMEMまで3サイクルの差があるため、予測が外れると3サイクルを捨てることになります。

$$ \text{IPC}_{\text{MEM}} = \frac{1}{1 + 0.20 \times 0.70 \times 3} = \frac{1}{1.42} \approx 0.70 $$

理想的なIPC 1.0から**30%**も下がった値です。

分岐決定をEX段階に前倒しすれば、ペナルティが2サイクルに減ります。

$$ \text{IPC}_{\text{EX}} = \frac{1}{1 + 0.20 \times 0.70 \times 2} = \frac{1}{1.28} \approx 0.78 $$

MEMに比べて約**11%**改善されます。

ID段階にさらに前倒しすれば、ペナルティが1サイクルまで減ります。

$$ \text{IPC}_{\text{ID}} = \frac{1}{1 + 0.20 \times 0.70 \times 1} = \frac{1}{1.14} \approx 0.88 $$

EXに比べてさらに**13%**改善されます。しかし分岐決定を前倒しするのには限界があります。ID段階で分岐条件を計算するにはレジスタファイルの読み出しと比較ロジックをすべてその段階に詰め込まなければならず、それ以上前倒しするのは事実上不可能です。

そうすると、残る問題は「0.7という外れる確率そのものをどのように減らすか？」になります。つまり予測段階そのものの正確度を上げなければならないという話です。

always taken予測

先の仮定では分岐の70%がtakenでした。であれば、すべての分岐をnot takenではなく takenと予測してみてはどうでしょうか？外れる確率が0.7から0.3に減ります。

$$ P_{\text{miss}}^{\text{taken}} = 0.20 \times 0.30 = 0.06 $$

しかしここには新たな問題があります。takenと予測するためには分岐の目標アドレスが分かっていなければ次のサイクルにそのアドレスをIFに入れられませんが、 IF段階ではまだ命令を取得する前です。目標アドレスは命令の中にオフセットとしてエンコードされているので、命令をデコードする前にはどこへ飛ぶか分かりません。現在のPCだけでは推測することができないのです。

Branch Target Buffer

BTB(Branch Target Buffer)は、上で挙げたIF段階で現在のPCだけを見て分岐目標アドレスをどうやって知るのかという問題を解決するハードウェアです。

構造はキャッシュに似ています。分岐命令のPCをキーとし、以前に飛んだ目標アドレスを値として保存するテーブルです。分岐が最初に実行されて結果が確認されると、その分岐の PCと目標アドレスをBTBに記録しておきます。次に同じPCから命令を取得するときにBTBを参照すれば、デコードする前に「このアドレスには分岐命令があり、目標アドレスはここだ」ということを即座に知ることができます。

動作の流れを見ると、IF段階で分岐予測器は現在のPCでBTBを参照します。ミスすればこのPCがBTBにないという意味なので、分岐ではないとみなしてPC + 4から次の命令を取得します。ヒットすれば以前にこのPCに分岐があったという意味なので takenと予測し、BTBに保存された目標アドレスから次の命令を取得します。

パイプラインの後半で実際の分岐結果が確認されるとBTBを更新します。新しい分岐が発見されればエントリを追加し、目標アドレスが変わっていれば更新します。

Tagged BTB

BTBはキャッシュと構造が同じであるため、キャッシュと似た方式でインデックスし、同じく衝突問題が発生します。BTBテーブルはサイズが有限であるため、広いPCをすべてインデックスとして使うことはできません。代わりにPCの下位ビットの一部をインデックスとして使い、テーブル項目を見つけます。例えばBTBの項目数が256個であれば、PCの下位8ビットでインデックスして保存します。

問題は、異なる分岐命令が同じインデックスにマッピングされる可能性があるということです。PCが 0x1000の分岐と0x2000の分岐の下位ビットが同じであれば、同一のBTB項目を指します。そうなると一方の目標アドレスが他方を上書きしてしまい、分岐予測器が完全に見当違いのアドレスへジャンプしてしまうことがあります。これは分岐予測が外れるよりも悪い状況であり、まったく分岐ではない命令へジャンプしてCPUが完全に誤ったコードを実行してしまうからです。

Tagged BTBはこの衝突を検知するためにタグを追加します。PCの下位ビットでまずインデックスし、上位ビットをタグとして一緒に保存しておきます。参照時にインデックスで項目を見つけた後、保存されたタグと現在のPCの上位ビットを比較します。タグが一致すれば本物のヒットで、一致しなければ別の分岐がこのスロットを占めているという意味なのでミスとして処理します。

動的分岐予測

これまでは分岐をtakenとnot taken、2つのうちどちらかに固定して予測してきました。このような方式を静的分岐予測 (Static Branch Prediction) と呼びます。一方動的分岐予測 (Dynamic Branch Prediction) は、プログラム実行中に分岐結果の履歴を記録し、その履歴に基づいて次の予測を調整する分岐予測方式です。

静的予測の限界は、1つのプログラムの中に偏向方向がまったく異なる分岐が混在しているという点で明らかになります。例えば同じプログラムの中に以下の2つの分岐があるとしてみましょう。

分岐A (ループバックエッジ)：for (j = 0; j < 10; j++)のような構文の終了分岐。10回中9回taken、約90% taken。
分岐B (エラーチェック)：if (err != 0) { handle(); }のような構文。通常時はエラーがほとんど発生しないので約1% taken。

「常にtaken」と固定予測するとAは90%当たりますがBは1%しか当てられません。逆に「常にnot taken」と固定するとBは99%当たりますがAは10%に止まります。どちらの方向に固定しても、反対側の偏向を持つ分岐をほとんど外してしまうことになります。

統計的に「分岐の60〜70%がtaken」というのは平均にすぎず、実際の個々の分岐はほとんどがほぼ常にtakenかほぼ常にnot takenのどちらかに両極化しています。動的予測器は各分岐が自分の偏向を個別に学習するため、Aはtaken方向へ、Bはnot taken方向へとそれぞれ収束させ、両方とも高い正確度を達成することができます。

Pattern History Table

PHT (Pattern History Table) は簡単な動的分岐予測方法の1つで、分岐アドレスごとにカウンターを保存するテーブルです。 BTBと同様に、分岐PCの下位ビットでインデックスして該当カウンターを読み、カウンター値によってtakenまたはnot takenと予測します。

1ビット予測器

1ビット予測器はPHTの最も単純な形態です。カウンターは0または1の2つの状態を持ちます。前回takenだったなら1、not takenだったなら0を保存し、次回は保存された値のとおりに予測します。問題は予測があまりにも簡単に覆ってしまうことです。10回繰り返すループ文で最後にnot takenで抜け出すとカウンターが0に変わり、ループに再び入ると、not takenと予測してまた外してしまいます。

例えば以下のような入れ子ループを考えてみましょう。

for (int i = 0; i < 1000; i++) {
    for (int j = 0; j < 10; j++) {
        // ...
    }
}

内側ループの終了分岐1つに注目してみます。この分岐は外側ループが1度回るたびに合計10回実行され、そのうち9回はtaken(ループ継続)、最後の1回は not taken(ループ脱出)です。1ビット予測器でこの分岐を予測するとどうなるか見ていきましょう。外側ループに2回目に入った状況を仮定し、PHTの該当カウンターの初期値は直前の外側ループの最後に保存された0(not taken)とします。

反復	カウンター(予測)	実際の結果	当たり?	更新後カウンター
1	0 (N)	T	✗	1
2	1 (T)	T	✓	1
3	1 (T)	T	✓	1
...	...	...	...	...
9	1 (T)	T	✓	1
10	1 (T)	N	✗	0

10回中2回外します。ループ進入時に1回(直前の外側ループ脱出のためにカウンターが0になっていて最初の反復でミス)、ループ脱出時に1回です。正確度は $\frac{8}{10} = 80\%$に留まります。

問題は一度のミスが次の予測まで汚染してしまう点です。10回のうちたった 1回not takenが出ただけなのに、そのせいで次回のループ進入の最初の反復も一緒に外してしまうのです。この問題を解決するために2ビット予測器が登場します。

2ビット予測器

2ビット予測器は1ビット予測器の問題を解決するため、状態を 00(strongly not taken)、01(weakly not taken)、10(weakly taken)、 11(strongly taken) の4つに増やします。予測は上位ビットで決定し、10と11なら taken、00と01ならnot takenです。2ビット予測器は状態遷移方式によって2 種類あります。

2ビット飽和カウンター(Saturation) はtakenならカウンターを1上げ、not takenなら 1下げます。ただし最大の11と最小の00ではこれ以上変化せず飽和します。 strongly taken(11)状態で一度外すとweakly taken(10)へ行きますが、依然として上位ビットが1なのでtakenと予測されます。こうするとループの終わりで一度外れるのに揺らがないので、従来の1ビット予測器の問題が解決されます。

2ビットヒステリシスカウンター(Hysteresis) は状態遷移方式が少し異なります。2ビットを方向ビットと履歴ビットに分けて解釈します。予測は上位の方向ビットが決定し、履歴ビットは「方向ビットを変えるか否か」を判断するときに使われます。

状態遷移規則は3つあります。予測が当たれば履歴ビットを1に設定してstrong 状態になります。予測が外れてstrong(履歴=1)であれば履歴ビットだけを0に下げてweak 状態になります。予測が外れてweak(履歴=0)であれば方向ビットを反転させて履歴ビットを 1に設定します。

飽和カウンターとの違いは反転する瞬間にあります。飽和カウンターでは10(weakly taken)が外れると01(weakly not taken)に行きます。しかしヒステリシスカウンターでは 10(weakly taken)が外れると01(strong not taken)に行き、すぐにstrong状態から始まります。方向を変えるためには2回連続で外さなければならないという点は同じですが、変えた後の確信度が異なるわけです。

実質的には2つの方式の予測正確度の差は大きくないことが知られており、ほとんどの現代CPUは飽和カウンターを使用しています。重要なのは、一度外したからといってすぐに予測を反転させず、2回連続で外したら変えるということです。

先ほど1ビット予測器を分析する際に使った入れ子ループの例を、2ビット飽和カウンターで再び回してみましょう。内側ループの終了分岐が外側ループ1回につき10回実行され、 9回はtaken、1回はnot takenという状況です。

前回の外側ループの最後にカウンター状態がどのように保存されたかから追ってみましょう。 strongly taken(11)状態でループに入り、9回連続で当て、10回目に一度外すとカウンターはweakly taken(10)に下がり、そこで外側ループを脱出します。つまりPHTに残る状態は10です。

さて、外側ループが再び回ってきて内側ループに再進入します。

反復	状態(予測)	実際	当たり?	更新後
1	10 (T)	T	✓	11
2	11 (T)	T	✓	11
3	11 (T)	T	✓	11
...	...	...	...	...
9	11 (T)	T	✓	11
10	11 (T)	N	✗	10

10回中わずか1回しか外しません。1ビット予測器ではループ脱出(10回目の反復)とループ再進入(1回目の反復)の両方で外していましたが、2ビット予測器は脱出1回の誤答で11 → 10へ下がるだけで上位ビットが依然として1なので、再進入時に依然としてtakenと予測します。

Global Path History

2ビットState Machineベースの分岐予測は、PHTのサイズが十分であるという仮定のもとで90%前後の正確度を持つことが知られています。残りの10%未満は複雑なパターンの分岐です。以前に説明したアムダールの法則によれば、この部分を改善しても全体の CPU速度は大きく変わらなさそうです。10%未満を改善しても全体の速度に与える影響はわずかなはずですから。

しかし現代のCPUは上記の分岐予測器よりも複雑でより正確な分岐予測技法を使用します。より複雑な回路を入れれば費用が大きく増えるはずなのに、なぜわずかな正確度を上げるためにここまでするのでしょうか？

その理由は、CPUのパイプラインが深くなるにつれ、予測失敗ペナルティがはるかに大きくなったからです。5段パイプラインで分岐予測の正確度を1%程度上げたときの影響はわずかです。分岐予測に失敗しても飛ばすサイクルはせいぜい数サイクル程度だからです。しかし10段、20段以上の現代CPUでは、一度の分岐予測失敗が数十サイクルを無駄にしてしまうため、分岐予測の正確度を1%上げることの価値がより大きくなります。

現代CPUで使われる分岐予測方式の中で代表的なものがGlobal Path Historyです。分岐予測器でPHTをインデックスする際、最近の分岐の結果だけでなく分岐のアドレス情報まで一緒に使う方式です。

なぜ周辺の分岐の結果が役に立つのか、簡単な例を1つ見てみましょう。以下のように 互いに相関関係を持つ3つの分岐が1つのプログラムにあるとしてみましょう。

if (x == 0) { ... }            // B1
if (y == 0) { ... }            // B2
if (x == 0 && y == 0) { ... }  // B3

B3の結果は完全に決定的です。B1とB2が両方ともtakenだったらB3も必ず taken、そうでなければ必ずnot takenです。理論上100%当てられる分岐です。

ところが先ほど見た2ビットPHTがB3だけを単独で見るとどうなるでしょうか？プログラム実行中に(x, y)の値が毎回変わるので、B3の結果はこの予測器から見ると takenとnot takenが無作為に混ざって入ってくるように見えます。カウンターは常に揺らぎ、正確度はよくても(x, y) = (0, 0)となる比率に収束するだけです。B3 そのもののPCだけを見ている限り、この相関関係を捉える方法はありません。

Global Path History予測器は、最近実行された分岐いくつかのtaken/not taken 結果をGHR(Global History Register) に入れておきます。名前の通りプログラム全体で共有される(global)唯一のレジスタで、分岐結果が出るたびに1ビットずつシフトして最新のN個の結果を保持します。例えば 2ビットGHRがあれば、B3に到達した時点のGHRは直前の2つの分岐(B1、B2)の結果を持っています。

直前 (B1, B2)	GHR	実際のB3の結果
(T, T) — `x=0, y=0`	`11`	T
(T, N) — `x=0, y≠0`	`10`	N
(N, T) — `x≠0, y=0`	`01`	N
(N, N) — `x≠0, y≠0`	`00`	N

このGHR値をB3のPCと混ぜてPHTをインデックスすると、4つのケースがそれぞれ異なるPHT項目にマッピングされます。各項目は自分のGHR状況におけるB3の結果だけを学習するので、(T, T)の項目は常にtakenに収束し、残りの3つの項目は常にnot takenに収束します。B3単独で見ると結果が無作為に見えていたものが、GHRで区別してやると各「文脈」の中で完璧な決定的パターンになるわけです。こうするとB3の正確度は100%に近づきます。

一般化すると、Global Path Historyは1つの分岐の結果が周辺の分岐と相関関係を持つとき、その相関関係をPHTのインデックスに溶け込ませることで、単一の2ビット予測器では捉えられなかったパターンまで学習できるようにしてくれます。

GShare Branch Predictor

先ほどの説明で「GHR値をB3のPCと混ぜてPHTをインデックスする」と大雑把に述べましたが、この「混ぜる」を具体的にどう行うかが実は残された課題です。この部分に対する最も簡単で広く使われている答えが、1993年にScott McFarlingが提案したGShare 予測器です。

まずなぜGHRかPCのどちらか1つだけを使ってはいけないのかから押さえておく必要があります。PHTを GHRだけでインデックスすると、PCがまったく異なる2つの分岐であっても、たまたまGHRが同じになる瞬間に到達すると、同じPHT項目を共有することになります。互いに無関係な分岐が同じカウンターを奪い合って予測を壊してしまうaliasing(エイリアシング) が激しく発生します。逆にPCだけを使うと、先ほど見た普通のPHTとまったく同じになり、周辺の分岐との相関関係をまったく捉えられません。

ではPCとGHRを連結するのはどうでしょうか？例えばPCの下位6ビットと6ビット GHRを連結して12ビットのインデックスを作ると、PHTの項目数は$2^{12} = 4096$個になります。すべての(PC, GHR)の組み合わせがそれぞれ独立した項目を持つことになりエイリアシングは解決されますが、今度はPHTのサイズが2つのビット幅の積の分だけ大きくならなければなりません。しかも実際のプログラムで使われる(PC, GHR)の組み合わせはそのうちのごく一部だけであり、ほとんどの項目はプログラム全体で一度も触れられず無駄になります。

GShareのアイデアは単純です。PCとGHRをXORしてインデックスすることです。

$$ \text{index} = \text{PC}[n-1:0] \oplus \text{GHR}[n-1:0] $$

PHTが$2^{12}$項目なら、PCの下位12ビットと12ビットGHRをXORして12ビットインデックスを得ます。テーブルサイズは$2^{12}$のまま変わりませんが、インデックスの中にPCと GHRの情報が両方溶け込んでいます。連結のようにテーブルを大きくせずに 2つの情報を両方活用できるわけです。

もちろんGShareも完璧ではありません。互いに異なる2つの(PC, GHR)の組がXOR 結果としては同じになることがあるからです。例えばPC = 0x100, GHR = 0x010と PC = 0x010, GHR = 0x100はXORが同じく0x110になってしまいます。このような破壊的衝突(destructive aliasing)をさらに減らすため、後にBi-Mode、Agree Predictor、TAGEのようなより精巧な予測器が登場することになります。しかしGShareは「PC ⊕ GHR」という一行のアイデアだけでGlobal Path Historyの利点をほとんど得られる方式であるため、1993年以降長い間事実上の標準として使われ、今でも新しい予測器を評価する際の基準線として頻繁に登場します。

Two-Level Branch Predictors

より一般的には、分岐予測器を1つのフレームワークとして定義することもあります。このフレームワークは1991–92年にYeh and Pattが Two-Level Adaptive Branch Predictionという名前で整理し、以後商用CPUの分岐予測器はほぼすべてこの枠組みの中で少しずつ変形される形で発展してきました。

名前の「Two-Level」は予測が2段階の保存構造を経て下されるという意味です。1段階目はBHR(Branch History Register) で、最新の分岐結果をビット列で記録するレジスタです。先ほど見たGHRはこのBHRを全体で1つだけ持つ特殊なケースでしたが、Two-Levelフレームワークでは後述するように分岐ごとまたは集合ごとにBHRを持つこともできるため、より一般的な名前であるBHRと呼ばれます。 2段階目はPHTで、1段階目の履歴値をインデックスとして参照する2ビット飽和カウンターテーブルです。

ここで面白い点は、1段階目と2段階目のそれぞれをどのように構成するかにいくつかの選択肢があることです。各段階についてYeh and Pattは3つの選択肢を提示しました。

Global (G/g)：プログラム全体で共有されるただ1つの構造を置きます。 1段階目なら全体BHR 1個、2段階目なら全体PHT 1個です。ハードウェア資源が最も少なくて済み、分岐同士の相関関係を自然に捉えることができます。その代わり互いに無関係な分岐が同じ構造を共有することで生じるエイリアシング問題が大きくなります。
Per-address (P/p)：分岐PCごとに自分専用の構造を置きます。1段階目なら分岐PCごとに別々のBHRを、2段階目なら分岐PCごとに別々のPHTを置く方式です。各分岐が自分の履歴とパターンを独立に学習するのでエイリアシングはほとんどありませんが、必要なエントリ数が分岐数だけ増えるのでハードウェア費用が大きくなります。
Per-set (S/s)：分岐をいくつかのグループ(集合)に分け、グループ単位で構造を置きます。一般的にはPCの一部のビットで集合番号を決め、同じ集合に属する分岐が1つのBHRまたはPHTを共有します。GlobalとPer-address の中間点で、ハードウェア費用を適度に下げつつエイリアシングもある程度減らす折衷案です。

Yeh and Pattはこの組み合わせを3文字表記のXAYとして整理しました。最初の文字大文字は1段階目の構成方式(G/P/S)、真ん中のAは「Adaptive」の固定文字、最後の小文字は2段階目の構成方式(g/p/s)を意味します。1段階 3通り × 2段階3通りで計9通りの組み合わせが可能です。

名称	1段階 (BHR)	2段階 (PHT)	説明
GAg	全体BHR 1個	全体PHT 1個	最も単純な形態。履歴値のみでPHTをインデックス。
GAs	全体BHR 1個	集合別PHT	全体履歴 + 集合単位で分けたPHTから1つを選んでインデックス。
GAp	全体BHR 1個	分岐別PHT	PCでPHTを選び、その中で履歴でインデックス。
SAg	集合別BHR	全体PHT 1個	集合別履歴を1つの全体パターンテーブルから参照。
SAs	集合別BHR	集合別PHT	両方とも集合単位。GlobalとPer-addressの中間の折衷。
SAp	集合別BHR	分岐別PHT	履歴は集合別、パターンテーブルは分岐別。
PAg	分岐別BHR	全体PHT 1個	分岐自身の履歴を全体パターンテーブルから参照。
PAs	分岐別BHR	集合別PHT	履歴は分岐別、パターンテーブルは集合単位で共有。
PAp	分岐別BHR	分岐別PHT	両方とも分岐別。正確度は最も高いがハードウェア費用も最も大きい。

Tournament Predictor

ここまでに見た予測器はすべて「1つの予測方式」を選び、プログラム全体の分岐をその方式で予測します。しかし実際のプログラムの分岐は性格がまちまちであり、ある分岐はローカル履歴(自分自身の過去の結果)が最大の手がかりになり、別の分岐は周辺分岐との相関関係(グローバル履歴)が核心になります。例えば先ほど見た入れ子ループの終了分岐は自分自身の過去のパターンがそのまま繰り返されるのでローカル予測器が有利で、B3のような相関関係分岐は直前の分岐の結果が決定的なのでグローバル予測器が有利です。

であればこの2つを両方とも動かしておき、分岐ごとによりよく当たる方を選んで使ったら どうでしょうか？このアイデアの実装で最も有名なものがDEC Alpha 21264(1998) のTournament Predictorです。Scott McFarlingが1993年の技術報告書で提案したcombined predictor構造を実際の商用CPUに初めて採用した例で、長い間分岐予測の教科書の代表例として引用されてきました。

21264の予測器は3つのサブテーブルで構成されます。

Local Predictor (PAp構造)：分岐PCごとに10ビットのローカル履歴を保持する 1024エントリのBHRテーブルと、その履歴でインデックスされる1024エントリ3ビットカウンターPHTを置きます。自分自身の過去のパターンが鮮明な分岐に強いです。
Global Predictor：12ビットの全体履歴レジスタを置き、この値で 4096エントリ2ビットカウンターPHTをインデックスします。相関関係ベースの分岐に強いです。
Choice Predictor：名前のとおりどの予測器を信じるかを予測する予測器です。全体履歴でインデックスされる4096エントリ2ビットカウンターテーブルで、各カウンター値は「今の状況ではlocalが当たる可能性が高いか、 globalが当たる可能性が高いか」について学習された答えです。

毎分岐ごとに3つのテーブルが同時に参照されます。LocalとGlobalがそれぞれ taken/not takenの予測を出し、Choiceがそのうちの1つを「より信頼できる方」として指名するとその結果を最終予測として使います。分岐結果が確定するとlocalと global予測器それぞれのカウンターは通常通り更新されます。Choice予測器のほうは少し特別に動作します。2つの予測器のうち片方だけが当てたときにだけchoice カウンターを動かし、当てた方へ傾けます。両方とも当たった場合や両方とも外した場合はchoiceを触らず、この場合はどちら側がより良いかについての情報が事実上ないからです。

こうすることで21264は分岐の性格に応じて動的に最も適した予測器を選んで使います。純粋なPApまたは純粋なgshareのどちらか一方だけを使うよりも正確度が目に見えて高く、当時のベンチマークで約**90–100%**程度の予測正確度を示しました。以降登場した多くの高性能CPUは形は違っても、この 複数の予測器 + chooserのアイデアをそのまま継承していきます。

その他の分岐予測技法

これまで説明したBTBとPHTベースの予測器は、条件分岐の方向(taken/not taken)と目標アドレスを予測する一般的な方法でした。しかし実際のCPUはそれ以外にも特定の状況に特化した技法をいくつか一緒に使います。この節ではそのうちよく言及されるいくつかを簡単に見ていきます。

Return Address Stack

関数の返り(return)命令は、これまで説明したBTBだけではうまく予測できません。同じreturn命令(=同じPC)が実行されるたびに戻り先が変わるからです。fooという関数が互いに異なる数十か所から呼び出されると、その関数のreturn命令は呼び出し地点に応じて数十個の異なる目標アドレスを持たなければなりません。BTBは「このPCは前回どこへ飛んだか」だけを記憶するので、呼び出し地点が変わるたびに予測が外れることになります。

Return Address Stack(RAS) は、この問題を解決するためにCPUの中に置く小さなハードウェアLIFOスタックです。動作は単純です。call(関数呼び出し) 命令に出会うと次の命令のアドレス(PC + 4)をRASにpushし、return命令に出会うとRASからpopした値を予測目標アドレスとして使用します。

ここで1つ疑問が生じます。IF段階ではまだ命令をデコードしていないのに、今取得しているPCがreturnなのか一般的な分岐なのかをどうやって知ってRASと BTBのどちらを使うか決めるのでしょうか？答えはBTBエントリに分岐タイプ情報まで一緒に保存しておくということです。分岐が最初に実行されてデコードされる際に conditional / call / returnなどのタイプがBTBに一緒に記録され、次回同じPCをフェッチする際にBTBヒットが「これはreturnだ」と知らせてくれると、その瞬間目標アドレスをBTBの代わりにRASからpopして使うという方式です。つまりRASとBTBは「どちらか 1つを選ぶ」関係ではなく、BTBがタイプディスパッチャの役割を果たし、それに応じて RASが動員される構造です。

RASは通常8〜32エントリ程度の小さな循環バッファとして実装されるため、再帰がその深さを越えると最も古いエントリが上書きされてオーバーフローが起きます。このときオーバーフロー区間のreturnはRASから誤ったアドレスを得て予測が外れますが、再帰がある程度解けて再びRASの深さの内側に戻るとそれ以降のreturnは正常に復旧します。重要なのは、これはあくまで 性能損失であって正確性の問題ではないという点です。実際のreturn アドレスはメモリのスタックフレームにそのまま保存されていて、EX段階で実際の目標アドレスが確認された瞬間パイプラインを空にして正しい場所へジャンプするだけで、プログラムが見当違いの場所へ戻ってしまうことはありません。現代CPUはほぼ例外なくこの RAS構造を標準で搭載しています。

Trace Cache

Trace Cacheは厳密に言えば分岐予測技法ではなく命令フェッチパスの最適化です。しかし分岐処理性能に直接的な影響を与えるため、頻繁に一緒に言及されます。

一般的なI-cacheは命令をアドレス順に保存します。そのためtaken 分岐に出会うと目標アドレスへジャンプした後、次のキャッシュラインを新たに読み込まなければ ならず、1サイクルで複数の基本ブロックを跨いで命令を取得するのが困難です。パイプラインが深く、1サイクルに多くの命令をフェッチしなければならない高性能CPUではこれがボトルネックになります。

Trace Cacheは代わりに実行順に命令を保存します。プログラムが実際に実行した経路(taken分岐に沿ってつながる基本ブロックの連なり)を1つの「trace」としてまとめてキャッシュに保存しておき、次回同じ経路に出会うと複数の基本ブロックに跨る命令を一度にフェッチできるようにします。さらに命令があらかじめデコードされた形で保存されているため、デコード段階の負担も軽減されます。

Intel Pentium 4(NetBurstマイクロアーキテクチャ, 2000) がこの方式を代表的に採用しましたが、命令の重複保存による低い密度と高い電力消費のため、 Core 2では廃止されます。以後IntelはSandy Bridge(2011)から似たアイデアをはるかに小規模のµop Cacheの形で復活させ、今日まで使われています。

TAGE

TAGE(TAgged GEometric history length predictor)はAndré Seznecが 2006年に発表した予測器で、現在まで知られている最も正確な分岐予測方式の中の 1つであり、Intel Haswell(2013)以降のプロセッサ、AMD Zen系、Apple Siliconなどほとんどの現代高性能CPUが変形された形態で採用しています。

核心のアイデアは、短い履歴で予測される分岐と非常に長い履歴が必要な分岐が1つのプログラムに混在しているということです。大多数の分岐は数ビットの履歴だけでも正確に予測されますが、少数の厄介な分岐は数十〜数百ビットに及ぶ長い履歴があってはじめてパターンが現れます。かといってすべての分岐に数百ビットの履歴を付ければテーブルが巨大になり、エイリアシングが激しくなります。

TAGEはこの問題を指数関数的に増加する履歴長を持つ複数のテーブルで解決します。例えば履歴長が0、4、10、25、64、160 ビットの6つのテーブルを置き、各テーブルは自分の履歴長でインデックスされます。キャッシュのtagのように各エントリにタグを付けて「このエントリが本当にこの分岐とこの履歴に対するものなのか」を検証します。

予測時にはすべてのテーブルを同時に参照した後、タグが一致するテーブルの中で最も長い履歴を使うものの予測を最終結果として使います。タグが1つも合わなければ最も短い履歴(基本のbimodal)で代替します。こうすると短い履歴で十分な分岐は短いテーブルで処理され、長い履歴が必要な厄介な分岐は長いテーブルでタグが一致したときそちらの予測に従います。テーブル数は対数的にしか大きくならないのに扱える履歴の範囲は幾何的に広がるのがこの構造の強みです。

TAGEはいくつもの分岐予測コンペ(Championship Branch Prediction Workshop)で長い間1位を占め、後続の変形であるTAGE-SC-L、TAGE-GSCなどが続々と提案されています。

Perceptron Predictor

Perceptron PredictorはJiménezとLinが2001年に提案した、分岐予測を 機械学習問題として捉えるアプローチです。パーセプトロン(1950年代のニューラルネットワークの祖先)は入力ベクトルと重みベクトルの内積を計算し、符号に応じて二値分類を下す最も単純な線形分類器ですが、この構造をそのまま分岐予測に持ち込んだものです。

各分岐は自分専用の重みベクトルを持ちます。入力はグローバル履歴レジスタの各ビット(+1または-1と解釈)で、重みは小さな整数(例えば-127〜127 の範囲)として保存されます。予測は重みと履歴ビットを内積して合計が正なら taken、負ならnot takenと決定します。分岐結果が確認されると外れたか確信が足りなかった場合のみ、各重みを該当する履歴ビットの方向へ少しずつ動かして学習させます。

この方式の最大の強みは、非常に長い履歴を線形のコストで使えるという点です。従来のPHT方式は履歴が$n$ビットだとテーブルが$2^n$必要であるのに対し、パーセプトロンは重みが$n$個だけで済むため、数百ビットの履歴も現実的にサポートされます。おかげで長い範囲の相関関係が必要な分岐で際立ってよく動作します。

弱点も明確です。パーセプトロンは線形分類器なので、XORのような線形分離不可能な(linearly inseparable)パターンは学習できません。例えば「直前の 2つの分岐が互いに異なる結果だったときtaken、同じ結果だったときnot taken」のようなパターンは単一のパーセプトロンでは正確に予測されません。

AMD Bulldozer(2011) がこの方式を商用CPUに初めて採用したと知られており、以後AMD Piledriver、Jaguar系などが変形された形態で使用しました。 AMD ZenからはTAGE系へ移行する流れですが、perceptronは依然としてハイブリッド予測器の一構成要素として活用される場合が多いです。

コンパイラの分岐最適化

ここまで見てきたのはハードウェアがランタイムに動的に分岐を予測する方法でした。しかし分岐予測性能を引き上げるもう1つの軸はコンパイラです。コンパイラはソースコードの構造と静的解析の結果、あるいはプロファイル情報を活用して分岐自体を減らしたり、予測器に有利なコード配置を作ったり、さらには分岐を完全に消してしまったりもします。

If-conversion

予測がいくら正確であっても、外れる可能性そのものを0にすることはできません。であれば「予測しなくてもよいように」分岐自体を消してしまってはどうでしょうか？これが If-conversion(またはプレディケーション / predication)のアイデアです。コンパイラが条件分岐を条件付き命令(predicated instruction) に変換して、結果として両方の経路のコードを両方とも実行しつつ条件に合った側の結果だけをレジスタに反映させる方式です。

例えば次のコードを見てみましょう。

if (a > 0) x = y + 1;
else       x = y - 1;

通常のコンパイルではa > 0の比較結果で条件分岐を出し、2つの経路のうち 1つだけを実行します。If-conversionを適用するとおおよそ次のように変わります。

cmp  a, 0
(p1) x = y + 1   ; p1が真のときだけコミット
(p2) x = y - 1   ; p2が真のときだけコミット

分岐なく2つの命令が両方とも実行されますが、結果はpredicateビットに応じて片方だけがレジスタに反映されます。分岐が完全になくなったので予測失敗という概念がないわけです。その代わり両方の経路を常に実行するので作業量が増え、経路が長かったり不均衡だったりするとかえって損です。そのためif-conversionは主に短くて均衡の取れた分岐に選択的に適用されます。

ARM(ARM32以前の命令セットはほぼすべての命令が条件付きでした)、 Intel Itanium(IA-64の全面プレディケーション)、そしてGPU(すべてのwarp内分岐をプレディケーションで処理)がこの技法を積極的に使った代表例です。 x86/x86-64は全面プレディケーションはありませんが、cmovのような制限的な条件付き移動命令を通じて類似の最適化を部分的にサポートします。例えば次のコードはx86-64で分岐なしにcmovでコンパイルされる場合が多いです。

int max(int a, int b) {
    return (a > b) ? a : b;
}

cmp  edi, esi
cmovg eax, edi    ; a > bならeaxにaを入れる
cmovle eax, esi   ; そうでなければeaxにbを入れる

静的分岐ヒント (Static Branch Hints)

開発者が特定の分岐の偏向方向を既に知っている場合、その情報をコンパイラに直接教えることができます。GCC/Clangの__builtin_expectが代表的です。 Linuxカーネルで広く使われるlikely() / unlikely()マクロはこのビルトインをラップしたものです。

#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

void process(int *p) {
    if (unlikely(p == NULL)) {
        handle_error();
        return;
    }
    // ... 通常処理 ...
}

このヒントがあるとコンパイラは通常処理経路をfall-through(分岐なしにそのまま続く経路)に配置し、稀なエラー処理経路を関数の後ろや別のセクションへ追いやってジャンプするようにコードを再配置します。CPUから見ると稀にしか使われないエラーコードがI-cacheやBTBを汚染しなくなり、頻繁に使われる正常経路は straight-line codeとして維持されてフェッチ効率が上がります。

C++20からは標準として[[likely]] / [[unlikely]]属性が追加され、ビルトインなしでも同じ最適化を要求できるようになりました。

if (value < 0) [[unlikely]] {
    throw std::invalid_argument("negative");
}

Rustは長い間#[cold]属性を慣用句として使ってきました。稀な経路を別の関数へ切り出して#[cold]を付けると、コンパイラがその呼び出し地点をunlikelyとみなしてコードを再配置します。

#[cold]
#[inline(never)]
fn handle_error() -> ! {
    panic!("invalid input");
}

fn process(p: Option<&i32>) {
    let Some(v) = p else { handle_error() };
    // ... 通常処理 ...
}

Rust 1.83からはstd::hint::likely / std::hint::unlikelyがstableに昇格し、C++20と似た感覚で使うこともできます。ただしコミュニティでは依然として#[cold]関数パターンのほうが広く使われています。

Profile-Guided Optimization (PGO)

開発者が手動でヒントを付けることには限界があります。数十万個の分岐 1つ1つにlikely/unlikelyを付けるわけにもいきませんし、実際には人が推測した偏向が実行統計と食い違うケースも多いです。

PGO(Profile-Guided Optimization) は、この問題を実際のプロファイル測定で解決します。通常2段階で動作します。

Instrumented build：コンパイラが各分岐ごとにカウンターを挿入したバイナリを作ります。これを代表的なワークロードで実行して「どの分岐がどれほど頻繁に takenとなるか」に関する統計を収集します。
Optimized build：収集したプロファイルを再びコンパイラに入力として渡し、 測定された偏向方向に合わせてコードを再配置します。ホットな経路をstraight-lineに展開し、稀な経路を後ろへ送り、インライン化の判断もプロファイルを基準に調整します。

GCCでは-fprofile-generate → 実行 → -fprofile-useの順で、Clangでは -fprofile-instr-generate → -fprofile-instr-useでPGOを適用します。大規模なサーバーコードでは数%から10%以上の性能向上が観察されることもあります。 Google、Facebookのような会社は社内インフラのほとんどをPGOでビルドしており、最近は LLVMのAutoFDOのようにサンプリングプロファイラ(perf)で得たデータをそのままPGOに使用する方式も広く使われています。

ブロック再配置 (Basic Block Placement)

PGOや静的ヒントが与える偏向情報を実際に活用する最も重要な最適化の中の 1つがブロック再配置です。コンパイラは関数内の基本ブロックを実行頻度に応じて配置順を変えます。

int f(int x) {
    if (x < 0) {
        return -1;          // 稀な経路
    }
    return compute(x);      // 頻繁に使われる経路
}

基本ブロックがソース順に配置されると、x >= 0の普通のケースで「条件分岐 → taken → 目標アドレスへジャンプ」が必要になります。コンパイラが頻繁な経路をfall-throughとして配置すると、これを「条件分岐 → not taken → そのまま次の命令を実行」に変えることができます。taken分岐がnot taken分岐よりフェッチの面で少し高価なため、この小さな差が積み重なると無視できなくなります。

さらにコンパイラは非常に稀な経路(例外処理、エラーログ、coldな初期化) を関数の外の.text.coldのような別のセクションへ移動させることもあります。こうすると I-cacheにはhot経路だけが載り、稀に使われるコードは完全に別のページへ分離されてcacheとTLBの負担を大きく減らすことができます。

Itaniumの`brp`とTAR

さらに一歩進んで、Intel Itanium(IA-64) は「コード配置」をISAレベルの命令へ拡張し、コンパイラが分岐予測器に直接ヒントを打ち込む専用命令を提供しました。Itaniumが掲げたEPIC(Explicitly Parallel Instruction Computing) 哲学、すなわち「ハードウェアが動的に判断することをコンパイラが可能な限り静的に担う」という方向とつながる機能です。

brp (Branch Predict) は分岐予測器をあらかじめ準備させる命令です。「これからこのPCに分岐が来て、その目標アドレスはここで、方向はこちらだ」をハードウェアにあらかじめ知らせ、CPUが実際の分岐命令に出会う前にBTBと予測カウンターの状態を整えておくようにします。一種のソフトウェア主導の分岐予測プリフェッチというわけです。

brp.sptk  target_addr, clr       # まもなくtarget_addrへ向かう分岐が来る
                                 # strongly takenで予測するよう要求
...
// (複数の命令の後)
br.cond   target_addr            # 実際の分岐 — すでに予測器が準備されている

一般的なハードウェア予測器は同じ分岐を2回目に出会ったときからまともに予測できますが、brpを使うと初回の実行すらもすでに予測が準備された状態で当てることができるという点が核心的な違いです。

TAR (Target Address Register) は間接分岐のための仕組みです。Itaniumの間接分岐はジャンプの目標を一般レジスタではなく専用のBranch Register(b0〜b7)から読み込みますが、この構造の上に別の目標アドレスレジスタとその内容をあらかじめ予測器に結びつけておく仕組みが乗せられています。コンパイラが間接分岐の目標アドレスを非常に早い時点でTARに載せておくと、後で実際のbr.callのような命令が実行されるときに予測器がすでに目標を知っておりミスプレディクションなしに飛ぶことができます。仮想関数呼び出しや関数ポインタ呼び出しのように一般的なBTBでは予測が難しい分岐で有用です。

ItaniumのbrpとTARは**「ハードウェア予測器が学習するまで待たずに、コンパイラがあらかじめ答えを入れておこう」** というアプローチです。理論的には非常に強力ですが、実際にはコンパイラが分岐の動作を十分に正確に予測してヒントを付けること自体が難しく、Itanium自体の商業的失敗と共に主流からは姿を消しました。それでもISAに分岐予測ヒントを直接入れるというアイデア自体はその後、いくつかの研究プロセッサや一部の組み込みISAに影響を残しました。

ループアンローリング (Loop Unrolling)

ループの終了分岐は反復回数だけ頻繁に実行されます。ループアンローリングはループ本体を複数回展開して反復回数そのものを減らす最適化です。

// 元の形
for (int i = 0; i < n; i++) {
    sum += a[i];
}

// 4倍アンロール
for (int i = 0; i < n; i += 4) {
    sum += a[i];
    sum += a[i+1];
    sum += a[i+2];
    sum += a[i+3];
}

分岐予測の観点からの利益は2つあります。第一に、終了分岐の実行回数が nからn/4に減り、分岐命令そのもののコストが減ります。第二に、ループ本体が大きくなることで命令レベル並列性(ILP) をより多く確保でき、OoOエンジンが仕事をよりうまくこなせるようになります。欠点はコードサイズが大きくなってI-cacheへの圧力が増えることで、コンパイラはアンロール回数を慎重に決定します。

関数インライン化 (Function Inlining)

callとreturn命令そのものも分岐です。RASのおかげで予測正確度は高いですが、命令数が増え、レジスタの保存/復元オーバーヘッドも発生します。関数インライン化は小さな関数の本体を呼び出し地点に直接挿入してcall/returnのペアを完全に除去します。

static inline int square(int x) { return x * x; }

int sum_of_squares(int a, int b) {
    return square(a) + square(b);
    // インライン化後: return (a * a) + (b * b);
}

呼び出しオーバーヘッドが消えるだけでなく、インライン化されたコードが呼び出しコンテキスト内の定数や型情報と組み合わさって追加最適化の機会を開いてくれる効果のほうが大きいです。コンパイラは関数サイズ、呼び出し頻度、再帰の有無などを考慮してインライン化するか否かを決定し、PGO情報があればはるかに積極的にインライン化を行います。

CPUの分岐予測