branch-prediction - 分岐予測データはどこにどのように保存されますか?

Question

私はいつも、予測データがどこにどのように保存されているのか疑問に思っていましたか? 制限はありますか？最近のブランチだけですか？私は主に Intel のアーキテクチャに関心がありますが、アーキテクチャについて学べることは何でも歓迎します。

Answer 1

プロセッサの内部のどこか。正確に何が行われるかは、プロセッサによって異なります。

非常に単純なケースでは、4096 ビットの分岐予測データを取得できます。次に、分岐ごとに、分岐のアドレスの最後の 12 ビットを取得します。これにより、4096 の異なる値が得られ、それを分岐予測データのインデックスとして取得します。また、データは 1 ビットしかないため、最後の分岐が行われたかどうかを保存するだけです。

メリットは非常に安いことです。欠点は、正確に 4096 バイト離れた 2 つのブランチがテーブル内の同じエントリを使用することです。したがって、コードでこれら 2 つの分岐が常に実行され、1 つが常に実行され、もう 1 つが実行されない場合、分岐予測はかなり悪くなります。

一部のプロセッサは、「強い取得」、「取得」、「取得されていない」、「強い取得されていない」を意味するブランチごとに 2 ビットを使用します。分岐が行われるたびに、予測は「強く行われる」方向に移動し、分岐が行われない場合は「強く行われない」方向に移動します。これは、まれな例外を除いて分岐が通常行われる場合にうまく機能します。

一部のプロセッサは、分岐アドレスの最後の 12 ビット以上を使用するだけでなく、最後の 4 つの分岐が行われたかどうかにかかわらず混合します。コードがあるとしましょう

if (x >= 0) { ... } 
if (x <= 0) { ... }

x が 0 になることはめったにありませんが、非常にランダムに正または負になります。その場合、最初の分岐を予測するのは困難ですが、最初の分岐が実行された後に 2 番目の分岐が実行されることはなく、最初の分岐が実行されない場合は常に実行されます。この情報を混合することで、2 番目の分岐の分岐予測テーブルの 2 つのエントリを使い果たしますが、2 番目の分岐の予測は、分岐がランダムに行われるかどうかに関係なく、非常に正確になります。

分岐予測テーブルの同じエントリが複数の分岐に使用されるという問題が常に発生します。あなたはそれと一緒に住んでいます。(これを処理するために巧妙なことをすると、非常に多くのストレージが必要になります。分岐予測ごとに 1 または 2 ビットを使用しているため、非常に少ないストレージで大規模なテーブルを作成できます)。