あなたの質問に答えるには、まず分岐予測がどのように機能するかを理解する必要があると思います。そもそもなぜそのような予測を行うのかを知る必要があることを説明するには. そのためには、最新のプロセッサのパイプラインがどのように機能するかを理解する必要があります。これを説明する最善の方法は、パイプライン化されていない CPU プロセス命令から始めることです。
(あなたがすでに知っていることを私が調べてもご容赦ください。分岐予測に関するあなたの混乱がどこから生じているのかは完全には明らかではありません.)
古い CPU は、多くの単純な最新の CPU と同様に、かなり単純明快な方法で命令を処理します。命令を実行するために必要なアクションを一連のステップに分割します。各命令はこれらのステップを経て実行され、すべてが完了すると次のステップに進みます。たとえば、架空の単純なパイプライン化されていない CPU は、次のような一連の手順に従う場合があります。
- 命令をメモリにフェッチします。
- 命令のオペランドを読み込みます。
- その命令の操作を実行します。
- 結果を書く
この方法で CPU を実装するのは比較的簡単ですが、プロセッサのリソースを非常に非効率的に使用します。CPU が実行と命令のプロセスの 1 つのステップを実行している間、他のステップを実装するために使用されるすべてのシリコンはアイドル状態になります。
最新のパイプライン化されたプロセッサは、命令を実行するために必要な一連のステップを組み立てラインのようなものに変えることで、より効率的にしようとします。命令は、パイプライン化されていない CPU と同様に、一連のステップを通過するか、ステージが呼び出されます。違いは、命令がパイプラインの最初のステージをクリアすると、CPU が別の命令を送信できることです。これにより、複数の命令を同時にパイプラインに入れることができ、うまくいけば、チップのすべての部分を十分に活用できます。命令は依然として多くの異なるステージを通過する必要がありますが、理想的には、命令は次々とパイプラインからすばやく出てきます。パイプライン処理は、命令を最初から最後まで実行する時間を改善するのではなく、命令が完了するまでの時間を短縮します。
さて、これは最新のパイプラインのかなり単純化された説明であり、最新のパイプライン化された CPU の設計を複雑にする多くの問題について説明しています。ただし、分岐予測に関する限り、対処する必要がある複雑な問題は 1 つだけです。それは、分岐命令を実行するときに何をすべきかということです。
まず、分岐命令自体で特別なことをする必要はありません。他のものと同じようにパイプラインに放り込むことができます。最初のステージをクリアすると、CPU は次の命令を送信できますが、そこに問題があります。次の指示は何ですか？これは分岐であるため、2 つの異なる方向に進む可能性があり、分岐命令がパイプラインを通過するまで、CPU はどちらの方向に進むかわかりません。
プロセッサが行う簡単なことは、待機することです。パイプラインが待機している間、他の命令はパイプラインに供給されないため、パイプラインは空になります。分岐命令が (空になった) パイプラインを終了したときにのみ、CPU は命令の挿入を再開できます。その次の命令は、空になったパイプラインのすべてのステージを通過する必要があるため、分岐命令が終了してから次の命令までの間に遅延が生じます。指示します。この場合、命令は、理想的にはパイプラインをすばやく連続して終了しません。
この遅延は、最新のプロセッサでは非常に大きくなる可能性があります。これは、パイプラインのステージ数の関数であり、基本的にステージごとに 1 サイクルです。最新の x86 CPU のほとんどは、パイプラインに約 15 ステージあるため、そのようにブランチを実装するには非常にコストがかかります。非常に短いパイプラインを備えた単純な CPU は、常に待機することでうまくいくかもしれませんが、最新のプロセッサは別のことをしなければなりません。彼らは予測をします。
予測の最も単純な形式は、静的分岐予測です。プロセッサは、分岐命令自体だけを見て、分岐命令が実行されるかどうかを推測します。静的予測の最も単純な形式は、多くの場合、すべての分岐が行われないと仮定することです。より高度な静的予測子は、後方に向かう分岐が取られ、前方に向かう分岐は取られないと仮定します。これは、後方分岐はループであり、ループは通常複数回実行されると仮定します。
静的予測はうまく機能しますが、それでも多くの悪い予測が行われます。ある種の動的分岐予測を採用することで、これを改善できます。これを行うにはさまざまな方法があり、ここで言及するには多すぎますが、それらはすべて、以前のブランチがどのように進んだかの履歴に基づいて推測します。
ただし、CPU は最終的に予測を行い、あたかも正しい推測を行ったかのように処理を進めます。分岐命令がパイプラインに配置されると、実行されると想定される命令の送信が開始されます。これは投機的実行と呼ばれ、このように処理される命令は投機的であるとタグ付けされます。これにより、パイプラインは、元に戻すことができないこれらの命令で何もするべきではないことを認識できます。
分岐命令がパイプラインの最後に到達すると、CPU はその推測が正しかったかどうかを知るようになります。正しい予測を行った場合、何もする必要はありません。前の命令がパイプラインを通過する過程を終了させることができます。正しく推測したため、ブランチに追加コストはかかりません。
間違っていると推測した場合は、投機的に実行された命令が実行した可能性のあるものをすべて元に戻す必要があり、パイプラインをクリアして、実行されるはずだった命令の送信を開始します。これにより、まったく予測を行わなかった場合と同じ遅延が発生します。
「分岐予測子は、それが正しくないかどうかをどのように判断しますか?」という質問に対する答えです。それは、正しい予測を行うかどうかを知らず、気にしないということです。それはただ予測をするだけです。動的分岐予測子の場合、分岐が行われたかどうかは履歴に記録されますが、正しい決定を下したかどうかは記録されません。