FPGA開発日記

カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages , English Version https://fpgadevdiary.hatenadiary.com/

分岐予測実装に関する考察(2. 分岐予測の結果反映と、結果のリプレース)

前回の続き。分岐予測を実行するところまで書いたが、今度は分岐が当たったかどうかを調査しなければならない。

msyksphinz.hatenablog.com

分岐予測の成功条件、分岐予測の更新条件

分岐予測に成功した、というのは何だろうか?

  • 当該命令が「予測した」命令である (PR_EN_x)信号により判別する。
  • 予測した結果と「異なる」
    • 「分岐する」と予測したが「分岐しない」 or 「分岐しない」と予測したが「分岐する」(2.1.)
    • 「分岐する」と予測して正解したが、「分岐先アドレスが異なる」 (2.2.)

2.1. は、通常の比較および相対ジャンプにて発生する条件だ。つまり、飛び先は常に同一であるため、2.2.の「ジャンプ先アドレスが異なる」ということは発生しない。つまり、「分岐する」か「分岐しない」かのどちらかが成否に関係する。これはMIPSRISC-VではBEQ命令やBNE命令などに相当する。

一方で、分岐予測にて分岐すると予測し正解しても、実際には外れている場合がある。それがレジスタ相対ジャンプで、ジャンプしてもレジスタ値が異っていると、常に同一アドレスにジャンプしないのでミスとなる。 これはMIPSRISC-VなどではJALR命令などに相当する。

これらの条件を考えると、分岐予測は分岐の成立不成立のみを考える単純なものではなく、飛び先のアドレスまで考慮しなければならない。 アドレス比較も入るため高速に実行するのはなかなか難しいため、おそらく一般的なCPUではアドレスを削って判定しているだろうと思われる。 例えばテキスト領域に配置してある命令では分岐予測を実行するが、それ以外の場所では常に分岐予測を実行せず、分岐する場合は常にパイプラインフラッシュするなど。 これにより、比較するアドレス範囲を絞ることができ、回路の動作周波数を改善できる可能性がある。

f:id:msyksphinz:20161110011744p:plain

分岐予測テーブルの更新

最後に分岐予測テーブルを更新するのだが、

  • 分岐元のアドレス (次のフェッチでテーブル参照のインデックスに使われる)
  • 分岐先のアドレス (次のフェッチで分岐予測のジャンプ先として使われる)
  • 分岐したか否か (ステートマシンの更新)

の情報が必要だ。これらに基いて、分岐予測のテーブルがアップデートされる。

という訳で、分岐予測について2回に分けてまとめてみたが、これは私の趣味で作っている自作CPUのためのまとめなので、このまとめに基いてバグを潰さなければ。。。

変な方向にジャンプしてしまい今のところ上手く動作してくれない。。。