分岐予測

分岐予測は、パイプライン化されたプロセッサが、分岐が解決される前にその結果とターゲットを推測することを可能にし、これによりストールすることなく、可能性の高いパスに沿って命令のフェッチと実行を継続できます。

Definition

分岐予測は、条件分岐が実行されるかどうか、およびその分岐先を予測するマイクロアーキテクチャ技術であり、プロセッサが予測されたパスに沿って命令を投機的にフェッチおよび実行し、予測が誤っていた場合にはその作業を破棄することを可能にします。

Scope

このトピックでは、制御フローを予測するための技術、すなわち静的予測、分岐履歴に基づく動的予測（1ビットおよび2ビットカウンタ、相関予測器、トーナメント予測器）、分岐ターゲットバッファ、および誤予測のコストについて扱います。予測がどのようにして深いパイプラインと投機的実行を可能にするかについても説明します。より広範な投機的実行機構と回復（アウトオブオーダー実行）、および基本的な制御ハザード自体（パイプライン処理とハザード）は対象外とします。

Core questions

• 分岐はなぜ深いパイプラインをストールさせるのか、そして予測はどのように役立つのか？
• 動的予測器はどのように分岐履歴を使用して精度を向上させるのか？
• 分岐ターゲットバッファとは何か、そしてそれは何を提供するのか？
• 誤予測のペナルティは何か、そしてそれはどのように回復されるのか？

Key concepts

• 静的予測 vs 動的予測
• 1ビットおよび2ビット飽和カウンタ
• 分岐履歴と相関
• トーナメント予測器
• 分岐ターゲットバッファ
• 誤予測ペナルティ
• 投機的フェッチ

Key theories

履歴に基づく動的予測

分岐の結果は、それ自身の過去の挙動や他の分岐の過去の挙動と高い相関があります。飽和カウンタに履歴を記録し、ローカル履歴とグローバル履歴を組み合わせる予測器（相関予測器やトーナメント予測器）は、非常に高い精度を達成します。

Mechanisms

予測器は、分岐の方向を推測するために履歴を参照し、そのターゲットを推測するために分岐ターゲットバッファを参照することで、フロントエンドが投機的にフェッチを継続できるようにします。2ビット飽和カウンタは、分岐ごとの最近の結果を追跡します。相関予測器はグローバル履歴を追加します。トーナメント予測器は、ローカルスキームとグローバルスキームの間で動的に選択します。誤予測が発生した場合、投機的な命令は破棄され、正しいアドレスからフェッチが再開されますが、これはパイプラインの深さに比例するペナルティを伴います。

Clinical relevance

正確な分岐予測は、現代の深く、幅の広いパイプラインにとって不可欠です。誤予測が多くのサイクルを要するため、高い性能を維持するには95%を超える精度の予測器が必要です。分岐予測構造は、その投機的動作がSpectreのような過渡的実行攻撃の基盤となるため、セキュリティ上も重要になっています。

History

単純な静的予測器と1ビット動的予測器は、2ビット飽和カウンタに取って代わられ、その後1990年代初頭には相関予測器と2レベル適応予測器が登場し、高性能コアではトーナメント予測器やニューラルスタイルの予測器が採用されるようになりました。パイプラインが深くなるにつれて、誤予測ペナルティを許容範囲に抑えるために、予測器の洗練度もそれに応じて向上しました。

Key figures

• James E. Smith
• Yale Patt
• Tse-Yu Yeh
• John L. Hennessy

Seminal works

• hennessy2019
• patterson2020

Frequently asked questions

分岐が誤予測された場合、何が起こるのか？

プロセッサは誤ったパス上の命令を投機的にフェッチし、部分的に実行しています。誤予測を検出すると、その投機的な作業を破棄（スカッシュ）し、正しいターゲットからフェッチを再開します。この際、パイプラインの深さにほぼ比例するペナルティが発生します。

現代の分岐予測器の精度はどのくらいか？

現代の動的予測器は、ローカルおよびグローバルな分岐履歴を組み合わせることで、一般的なワークロードにおいて通常95%を超える精度を達成します。この高い精度が、深く、幅の広いパイプラインを価値あるものにしています。なぜなら、各誤予測は投機的な作業の多くのサイクルを無駄にするからです。