27

編集:確かにどのブランチが取られるかを予測することによって、あなたも効果的にターゲット予測を行っているので、私の混乱が生じます??

この質問は、このトピックに関する最初の質問に本質的にリンクしています。

分岐予測と分岐先予測

受け入れられた答えを見る:

無条件分岐、固定対象

  • 無限ループ
  • goto声明
  • breakまたはcontinueステートメント
  • ステートメントの「then」節の終わりif/else(節を飛び越えるためelse)
  • 非仮想関数呼び出し

無条件分岐、可変ターゲット

  • 関数から戻る
  • 仮想関数呼び出し
  • 関数ポインタ呼び出し
  • switchステートメント (ジャンプ テーブルにコンパイルされている場合)

条件分岐、固定対象

  • if声明
  • switchステートメント (一連のif/elseステートメントにコンパイルされている場合)
  • ループ条件テスト
  • &&and||演算子_
  • 三項?:演算子

条件分岐、可変ターゲット

  • 通常の状況では発生する可能性は低くなりますが、コンパイラは上記の 2 つのケースを組み合わせて、最適化として 1 つを合成する場合があります。たとえば、x86 では、テール コールの最適化により、コンパイラがコードif (condition) { obj->VirtualFunctionCall(); }を条件付き間接ジャンプのようにjne *%eax最適化して、関数の最後に表示される場合があります。

次のコードがある場合:

if(something){
    //a
}
else{
    //b
}

(BP = 「分岐予測」および BTP = 「分岐ターゲット予測」)

その非常に明白な BP は、条件を評価するために使用されますsomething。ただし、ブランチで何が起こるかを判断するために BTP も関与しているかどうかを理解しようとしていaます。BTPは、BP の結果に応じて、ブランチa/にあるコードのアドレスも決定しますか?b

このウィキペディアのページ ( http://en.wikipedia.org/wiki/Branch_target_predictor ) でお願いします:

コンピューター アーキテクチャでは、分岐ターゲット プレディクターは、プロセッサの実行ユニットによって分岐命令のターゲットが計算される前に、実行される条件付き分岐または無条件分岐命令のターゲットを予測するプロセッサの一部です。

条件が予測された後、ターゲットを予測するために BTP が使用されることを示唆しています。

1) 誰かが上記を明確にしてくれませんか?

関連する 2 つ目の質問 - BP と BTP は、CPU のフェッチ/デコード/実行/ライトバック パイプラインと対話する方法がどのように異なるのですか? BP はフェッチ段階またはデコード段階から開始しますか? 条件付きコードの実行段階の後、予測が正しかったかどうかを確認し、分岐予測キャッシュを更新できます。

2) フェッチ/デコード/実行/ライトバック CPU ステージに関して、BTP はどのように機能しますか?

4

2 に答える 2

16

BP と BTP は当然密接に関連していますが、明らかに同じものではありません。あなたの最大の混乱は、BTP は特定の分岐のターゲットを予測するので、結果(つまり、次に実行される命令は何か) を教えてくれるという主張から来ていると思います。そうではありません。

ブランチ ターゲットは、このブランチが取得された場合に送信される可能性のあるアドレスです。分岐が行われるかどうかは、まったく別の問題であり、分岐予測子によって対処されます。実際、2 つのユニットは通常、パイプラインの初期段階で連携して動作し、(必要に応じて) 取得/非取得とアドレス予測の両方を生成します。次に、基本的に言う複雑なロジックがあります-それが分岐であり、それが取られると予測される(または無条件である)場合、ターゲットがある場合は(既知または予測されているかどうかにかかわらず)ターゲットにジャンプします。

ブランチタイプリストで自分自身を引用したように-ブランチが取得されることを予測する必要があるかどうか(条件付きかどうか)、およびブランチがターゲットを予測する必要があるかどうか(それは直接/固定ターゲットですか?)どちらも適用可能であり、それぞれが他に関係なく双方向に進む可能性があるため、リストした 4 つの選択肢が提供されます。

  • 理論的には、無条件の直接分岐は予測を必要としません。CPU フロント エンドは単にターゲットを読み取り、分岐を「取得」します (新しいアドレスからパイプライン コードを供給します)。ただし、最新の CPU は、分岐をデコードし、そこにエンコードされたターゲットを識別するのに依然として時間がかかるため、分岐予測子 (通常はパイプの先頭にあります) でのストールを回避するために、そのアドレスも予測する必要があります。ただし、予測の確認は簡単なので (デコード直後)、予測ミスのペナルティはそれほど高くありません。コード キャッシュや tlb ミスが原因でまだ停止する可能性がありますが、それ以外は最速です (ただし、最も弱いと言う人もいるかもしれません)。

  • 条件付き直接分岐は、デコード後にターゲットを認識します (ただし、その前にそれを予測する必要があります)。パイプ。これは、以前の命令に依存する可能性があり、条件の原因が判明するまで停止する可能性があります。したがって、ターゲットと方向の 2 つの予測が行われます (方向がフォールスルーの場合はターゲットは必要ありません) が、方向の解像度の方がリスクが高くなります。分岐予測子 (実際、最新の CPU には通常複数あります) は、知識に基づいた推測を行い、そこからフェッチを続けます。いくつかの研究が行われており、主にアカデミーで、両方のパスをフェッチして実行しようとすると(ただし、通常は数命令ごとに分岐があるため、これは指数関数的に爆発する可能性があることがすぐにわかります。通常、予測が難しいものに予約されています)。もう 1 つの一般的なオプションは、2 つのパスを「予測」することです (「a」に注意してください..)。つまり、パイプラインにいくつかのビットを送信して、どのパスであるかをマークし、解決策がわかったら間違ったパスを簡単にフラッシュできるようにします。これは、言語構造のためにデータフロー マシンで非常に一般的ですが、これはまったく新しい問題です。解決策がわかれば、間違ったパスを簡単にフラッシュできます。これは、言語構造のためにデータフロー マシンで非常に一般的ですが、これはまったく新しい問題です。解決策がわかれば、間違ったパスを簡単にフラッシュできます。これは、言語構造のためにデータフロー マシンで非常に一般的ですが、これはまったく新しい問題です。

  • ret無条件の間接分岐 - これらは両方とも一般的 (たとえば、すべて) であり、予測が難しいため厄介です。前のケースではブランチの解決は単純でしたが (そして常にいくつかのヒューリスティックまたはパターン推測に頼ることができました)、これは実際のアドレスを提供する必要があるため、おそらくこの特定のターゲットでこの特定のブランチに数回アクセスする必要があります。 BTP はそこでパターンを学習します。

  • 条件付き間接分岐 - 運が悪かったので、両方の予測が必要です...

したがって、決定は直交していますが、それは予測子がそうでなければならないという意味ではありません。分岐履歴の単一の「ストリーム」があることに注意してください。そのため、いくつかのテーブルまたはロジックを共有して、何らかの方法で予測子を関連付けることがおそらく有効です。設計上の決定がどの程度正確であり、実際のハードウェアの実装に依存するため、Intel/AMD がどのようにそれを行うかについて詳細を知ることはおそらくないでしょうが、そのトピックに関する学術研究はたくさんあります。

2 番目の質問については、少し大まかですが、実際の CPU の正確な詳細をすべて把握することはできませんが、あちこちでヒントを得ることができます。たとえば、このHaswell レビューの図を参照してください(どこかの前にここに現れたかもしれません) :

ハスウェルのブロック図

この図ですべてがわかるわけではありません、明らかに BP/BTP の入力、またはそれらの区別さえ欠落しています (それ自体が、おそらく一緒に構築されていることをすでに示しています) が、これが明らかにパイプラインの最初で最も重要な部分であることを示しています. フェッチ/デコード/... パイプライン (または代替の uop-cache パイプライン) にフィードする前に、次の命令ポインターを予測する必要があります。これはおそらく、次にどの命令を実行するかを考えることによって、CPU がすべてのサイクルを開始することを意味します (そうです、実際にはすべてが並行して行われますが、パイプラインを段階的なプロセスと考えるのに役立ちます)。彼が私たちが前回どこにいたかを知っているとしましょう。したがって、それは非分岐命令 (ああ、しかし可変長についてはどうですか.. このユニットが解決する必要がある別の複雑さ)、または分岐のいずれかです。

私が「推測」と書いたことに注意してください - 図が真実を語っている場合、デコード段階は本当に遠くにあり、この時点ではそれが分岐であることさえ知りません. あなたの質問に答えるために-このBP / BTPユニットは実行/ WBユニットと通信する必要があるため、条件付き分岐の結果を知ることができ、デコードユニットを使用して、現在決定されている命令が分岐であり、そのタイプを知ることができますつまり、フェッチのさまざまなパイプラインを使用して、出力をフィードします。他のユニットとのさらなる関係があると推測しています(たとえば、一部の設計では、ターゲットの予測に基づいてコードのプリフェッチを送信することを決定する場合があります..)。

于 2014-03-22T22:29:16.153 に答える