webdevqa.jp.net

インテルがここ数年で静的分岐予測メカニズムを変更したのはなぜですか?

から ここ インテルが近年いくつかの静的分岐予測メカニズムを実装したことを私は知っています:

  • 80486年齢:常に取られていない

  • Pentium4の年齢:後方撮影/前方未取得

  • Ivy BridgeやHaswellなどの新しいCPUは、ますます無形になっています。 Matt Gの実験はこちら を参照してください。

そして、Intel Document内で見つけた最新の資料は、約10年前に書かれたものであるため、Intelはこれ以上話したくないようです。

静的分岐予測は動的よりも(はるかに?)重要ではないことを私は知っていますが、かなりの数の状況では、CPUが完全に失われ、プログラマー(コンパイラーを使用)が通常最良のガイドです。もちろん、これらの状況は通常、パフォーマンスのボトルネックではありません。ブランチが頻繁に実行されると、動的予測子がそれをキャプチャするためです。

Intelはドキュメント内で動的予測メカニズムを明確に記述しなくなったため、GCCのbuiltin_expect()は、ホットパスからありそうもないブランチを削除する以外に何もできません。

私はCPUの設計に精通しておらず、Intelが静的予測子に現在使用しているメカニズムを正確に理解していませんが、動的予測子が失敗したときに行く予定のCPUを明確に文書化することがIntelにとって最善のメカニズムであると感じています。 、フォワードまたはバックワード」。通常、プログラマーがその時点での最良のガイドであるためです。

更新:
あなたが言及したトピックは、私の知識を徐々に超えていることがわかりました。ここには、動的予測メカニズムとCPU内部の詳細が含まれていますが、2、3日以内に学習することはできません。だから私はあなたの議論を一時的にやめて充電させてください。
ここではどんな答えでも歓迎します、多分もっと多くの人々を助けるでしょう

10
weiweishuo

静的予測が現代の設計で好まれない主な理由は、おそらく存在すらしないという点で、静的予測パイプラインで遅すぎる動的予測と比較してです。基本的な問題は、分岐の方向とターゲットの場所を知ってからフェッチする必要があることですが、静的な予測はしか行えません。 )afterデコード(フェッチ後に発生)。

さらに詳細に...

CPUパイプライン

簡単に言うと、実行中にメモリから命令をfetchdecodeそれらの命令、そしてexecuteそれらを実行する必要があります。1。高性能CPUでは、これらのステージはpipelinedになります。つまり、これらはすべて並行して実行されますが、任意の時点で異なる命令が実行されます。これについて少し読むことができます ウィキペディアで ですが、最近のCPUはより複雑で、一般的にはより多くのステージがあることに注意してください。

複雑からデコードまでの可変長命令セットを備えた最新のx86では、命令のフェッチとデコードに単純に関与する多くのパイプライン「ステージ」が存在する可能性があり、おそらく半ダース以上です。このような命令も スーパースカラー であり、一度に複数の命令を実行できます。これは、最高の効率で実行する場合、フェッチ、デコード、実行などのさまざまな段階で、多くの命令が実行されることを意味します。

フェッチのリダイレクト

取得されたブランチの効果は、パイプラインの最初の部分全体(通常はフロントエンドと呼ばれます)で感じられます。新しいアドレスにジャンプするときは、その新しいアドレスからフェッチしてデコードする必要があります。その新しいアドレスなどから。取得したブランチはリダイレクトフェッチである必要があると言います。これにより、効率的に実行するために分岐予測が使用できる情報に特定の制限が課せられます。

静的予測がどのように機能するかを検討してください。命令を調べ、それがブランチである場合は、ターゲットを比較して、「前方」か「後方」かを確認します。これはすべて、主に発生する必要がありますafterデコードが発生したのは、実際の命令がわかっているときだからです。ただし、分岐が検出され、取得されると予測される場合(たとえば、後方ジャンプ)、予測子はフェッチをリダイレクトする必要があります。これは、多くのパイプラインステージより前です。命令Nをデコードした後、フェッチがリダイレクトされるまでに、間違った(取得されていない)パスでフェッチおよびデコードされた後続の命令がすでに多数あります。それらは捨てられなければなりません。 bubbleがフロントエンドに導入されていると言います。

これらすべての結果として、静的予測が100%正確であっても、フロントエンドのパイプライン処理が無効になるため、分岐の場合は非常に非効率的です。フェッチとデコードの終了の間に6つのパイプラインステージがある場合、すべての分岐がパイプラインで6サイクルのバブルを引き起こし、予測自体と不良パス命令のフラッシュには「ゼロサイクル」がかかるという寛大な仮定があります。

救助への動的予測

ただし、最新のx86 CPUは、サイクルごとに最大1で分岐を実行できます。これは、完全に予測された静的実行の場合でも、制限をはるかに上回ります。これを実現するために、予測子は通常、デコード後に利用可能な情報を使用できません。サイクルごとにフェッチをリダイレクトし、最後の予測から1サイクルのレイテンシで使用可能な入力のみを使用できる必要があります。基本的に、これは、予測子が基本的に、次のサイクルの予測の入力として独自の出力のみを使用する自己完結型のプロセスであることを意味します。

これは、ほとんどのCPUの動的予測子です。次のサイクルからどこにフェッチするかを予測し、その予測に基づいて、その後のサイクルからどこにフェッチするかを予測します。デコードされた命令に関する情報は使用せず、ブランチの過去の動作のみを使用します。最終的には、ブランチのactual方向に関するフィードバックを実行ユニットから取得し、それに基づいて予測を更新しますが、これはすべて本質的に非同期で行われ、関連する命令が予測子を通過してから何サイクルも経過します。 。

合計する

これらはすべて、静的予測の有用性を損なうのに役立ちます。

まず、予測が遅すぎるため、完全に機能している場合でも、最新のIntelではブランチを取得するために6〜8サイクルのバブルが発生することを意味します(実際、これらはIntelのいわゆる「フロントエンドレストラン」からの観測値です)。これにより、予測を行うための費用便益方程式が劇的に変化します。フェッチして予測を行う前に動的予測子がある場合、多かれ少なかれ何らかの予測を行いたいと思うでしょう。それが51%の精度でさえあれば、おそらく報われるでしょう。

ただし、静的予測の場合、「実行された」予測を行う場合は、高精度である必要があります。たとえば、16サイクルの「完全な誤予測」コストに対して、8サイクルのフロントエンドレストランのコストを考えてみます。あるプログラムで、コールドバックワードブランチが取られない場合の2倍の頻度で取られるとしましょう。これは、(常に「予測」するデフォルトの戦略と比較して)逆方向に正しく予測する静的分岐予測の勝利となるはずです。2 取られていない)?

そんなに早くない! 8サイクルのリステアコストと16サイクルの完全な誤予測コストを想定すると、10.67サイクルの同じ混合コストになります。これは、8サイクルのバブルであるが、正しく予測された場合でも、フォールスルーの場合、静的予測なしの場合に対応するコストはありません。

それに加えて、静的予測がない場合は、静的予測の残りの半分がすでに正しくなっています(フォワードブランチが実行されない場合)。静的予測の効用は、想像するほど大きくありません。

なぜ今変更するのですか?おそらく、パイプラインのフロントエンド部分が他の部分と比較して長くなっているため、または動的予測子のパフォーマンスとメモリが増加しているため、静的予測に適格なコールドブランチが少なくなっているためです。静的予測子のパフォーマンスを向上させることは、ループ(後方取得ルールの理由)が動的予測子によってより頻繁に記憶されるため、コールドブランチの後方取得予測が弱くなることも意味します。

動的予測リソースの保存

この変更は、動的予測との相互作用が原因である可能性もあります。動的予測子の1つの設計では、分岐予測リソースをまったく使用せず、分岐が取得されることが観察されません。このようなブランチは一般的であるため、これにより多くの履歴テーブルと [〜#〜] btb [〜#〜] スペースを節約できます。ただし、このようなスキームは、後方分岐が取得されたと予測する静的予測子と矛盾します。後方分岐が取得されない場合は、静的予測子がこの分岐を取得して、取得されたと予測して、混乱させることは望ましくありません。取得されていないブランチのリソースを節約する戦略。


1 ...そして、retire、them-のようなことも行いますが、実行後に何が起こるかは、ここでの目的にとってはほとんど重要ではありません。

2 ここでは、「予測」を皮肉の引用符で囲んでいます。これは、ある意味では予測すらしていないためです。逆の予測がない場合のフェッチとデコードのデフォルトの動作は、取得されないためです。そうでない場合は、このようになります。静的予測を入力すると、動的予測子はそれ以外のことを教えてくれません。

10
BeeOnRope

インテル最適化マニュアルのセクション3.4.1.3で説明されている静的分岐予測は次のとおりです。

  • 取られる無条件の分岐を予測します。
  • 条件付きフォワードブランチが実行されないことを予測します。
  • 実行される条件付き後方分岐を予測します。
  • 間接分岐が行われないことを予測します。

コンパイラはそれに応じてコードを整理できます。同じセクションで次のように述べています。

Intel Coreマイクロアーキテクチャは、静的予測ヒューリスティックを使用しません。ただし、Intel 64およびIA-32プロセッサ間で一貫性を維持するには、ソフトウェアは静的予測ヒューリスティックをデフォルトとして維持する必要があります。

このステートメントは、セクション3.4.1.3が何年も更新されていないことを示しています。

動的予測子がフェッチされたバイト間に分岐命令があることを予測できなかった場合、またはバッファにミスがあった場合、他に意味のある選択肢がないため、フェッチユニットは順番にフェッチを続行し、静的予測を効果的に行います。取られていない。

ただし、命令キューユニットで、フェッチされたバイトストリームに条件付きまたは間接分岐命令があることが判明した場合は、この時点で、NotTakenよりも優れている可能性のある静的予測を行うことが理にかなっています。特に、条件付きの直接後方分岐の予測。これにより、特にフロントエンドのパフォーマンスが非常に重要になるため、動的予測子とNot-Takenフェッチユニットの障害によるペナルティを減らすことができます。私の知る限り、最適化マニュアルには、IQUにそのような静的予測子があり、最新のプロセッサに適用されるという明確な記述はありません。ただし、他の answer で説明しているように、一部のパフォーマンスカウンターの説明は、IQUにそのような静的予測子が存在する可能性があることを示唆しているようです。

全体として、これはIntelがもはや文書化していない実装の詳細だと思います。

コンパイラ支援の動的分岐予測技術は存在し、あなたが提案したように非常に役立つ可能性がありますが、現在のIntelプロセッサでは使用されていません。

5
Hadi Brais

私の理解では、現在の設計では、最新のTAGEブランチ方向予測子は、最近のブランチの取得済み/未取得の履歴を使用して、常にエントリにインデックスを付けます。 (これにより、単一のブランチの状態が多くの内部状態に広がる可能性があり、10要素のBubbleSortのような非常に複雑なパターンを予測できるようになります。)

CPUはエイリアシングを検出しようとはせず、検出した予測を使用して、条件分岐の取得/非取得を決定します。つまり、分岐方向の予測は常に動的であり、静的ではありません。

ただし、フロントエンドがストールしないようにするには、ブランチをデコードする前にターゲット予測が必要です。エイリアス化された他のブランチのターゲットが有用である可能性が低いため、通常、ブランチターゲットバッファはタグ付けされます。

@ Paul A Claytonが指摘 のように、BTBミスにより、CPUは、動的に取得された/取得されなかった予測子で見つかったものではなく、静的予測を使用することを決定できます。動的予測子を測定静的予測に十分な頻度でミスさせるのははるかに難しいことがわかっているかもしれません。

(私は物事を歪めているかもしれません。現代のTAGE予測子は、間接ブランチの複雑なパターンも予測できるため、取得/非取得の観点から予測しようとしているかどうかはわかりません。または、最初のステップが常に次のアドレスを予測しようとする場合、それが次の命令であるかどうかに関係なく、 X86 64ビットモードでのインデックス付きブランチオーバーヘッド 。)


正しく予測された場合でも、取得されなかったブランチの方がわずかに安価です。これは、フロントエンドが同じサイクルでuopキャッシュから前後の命令をより簡単にフェッチできるためです。(Sandybridgeファミリーのuopキャッシュは not トレースキャッシュです。uop-cache行は、x86マシンコードの連続ブロックからのみuopをキャッシュできます。)ハイスループットコード、取得されたブランチは、フロントエンドのマイナーなボトルネックになる可能性があります。また、通常、コードをより多くのL1iおよびuop-cache行に分散させます。


間接分岐の場合、「デフォルト」の分岐ターゲットアドレスは引き続き次の命令であるため、誤推測を防ぐためにud2またはjmp raxの後に何かを置くと便利です(特に非コード)、次の命令として実際の分岐ターゲットの1つを単純に配置できない場合。 (特に最も一般的なものです。)


分岐予測は、CPUベンダーが詳細を公開していない一種の「秘密のソース」です。

Intelは、実際には命令スループット/レイテンシ/実行ポート情報を(IACAおよび一部のドキュメントを通じて)公開していますが、実験的にテストするのはかなり簡単です( https://agner.org/optimize/ および- http://instlatx64.atw.hu/ 完了しました)そのため、Intelが望んでいたとしてもその秘密を守ることができたわけではありません。

分岐予測の成功率は、パフォーマンスカウンターを使用して簡単に測定できますが、なぜある特定の分岐が誤って予測されたか、特定の実行で予測されなかったかを知ることは非常に困難です。コードをrdtscまたはrdpmcなどでインストルメント化しない限り、1つのブランチを1回実行するだけでも測定は困難です。

4
Peter Cordes