FPGA開発日記

FPGAというより、コンピュータアーキテクチャかもね! カテゴリ別記事インデックス https://sites.google.com/site/fpgadevelopindex/

分岐予測実装に関する考察(1. 分岐予測する場所と、フェッチラインの考察)

2016/11/09 図に誤りあり。一部差し替えました。

CPUにおける分岐予測といえば、複数命令を同時発行させる現代のCPUにおいて不可欠な技術であり、投機実行の技術を支える重要な高速化技法であるが、だいたいのの解説書の場合、以下のような記述で説明がなされている。

以下の図はComputer Architecture Quantitative Approach, Fifth Editionより抜粋

f:id:msyksphinz:20161109015633p:plain

Computer Architecture, Fifth Edition: A Quantitative Approach (The Morgan Kaufmann Series in Computer Architecture and Design)

Computer Architecture, Fifth Edition: A Quantitative Approach (The Morgan Kaufmann Series in Computer Architecture and Design)

この図では、ステージ名がかろうじて書いてあるが、じゃあ実際にどうやって実装すれば良いんだろう?考えてみると、いろいろ複雑だ。

  • 分岐予測はどのステージで実行する? ** それに伴い、どの段階で命令フェッチを分岐予測に沿って変更すれば良い?
  • 分岐予測が当たったかどうかは、どのステージで判定すれば良い? ** 判定基準は?
  • 複数命令幅を同時にフェッチしてくるようなスーパスケーラのプロセッサでは、どのように実現すれば良い?

これらのことを考えながら、さらにどのような信号を定義するか、またどのような制御を組むかを考えなければならない。

分岐予測はどのステージで実行する?

分岐予測は、

  1. 予測元となるプログラムアドレス
  2. 予測先となるプログラムアドレス

の組で実現される。この予測元となるプログラムアドレスは、IFUつまり命令フェッチユニットから情報が得られる。 このプログラムアドレスは、例えばAXIなどで命令ワード幅以上の命令をフェッチしてくる場合は、複数のアドレスから調査する必要がある。

MIPSで0x1fc0_0000から命令を128ビット幅でフェッチしてきた場合、128ビット幅、つまり命令4つ分(0x1fc0_0000, 0x1fc0_0004, 0x1fc0_0008, 0x1fc0_000c)で分岐予測すべきアドレスが無いか、調査する必要がある。

f:id:msyksphinz:20161109021318p:plain

分岐予測の結果、得られる情報は?

分岐予測テーブルで、当該プログラムアドレスで分岐予測をすべきか調査した結果、ある命令で分岐予測できるということが分かった場合、情報を取得する。

  • PC_PR_EN_x (0<=x<4) : PC=A+x*4で分岐予測の履歴があり、分岐予測できる。
  • PC_PR_TAKEN_x (0<=x<4) : PC=A+x*4で分岐予測可能であり、かつ「分岐する」という予測である

この2つの情報が得られる訳だ。

分岐予測の結果、どのフェッチラインを破棄すべき?

そして、PC_PR_TAKENが1である場合、実際に分岐予測を実行する。ここで分岐元プログラムアドレスがA+0x8, 分岐先プログラムアドレスがB+0x04(Bが128ビットアラインとする)である場合、

  • A+0x00, A+0x04, A+0x08までは実行する
  • A+0x0c は破棄する

また分岐先プログラムアドレスBが128ビットアラインとは限らないため、最初の数ワードはフェッチする必要が無いかもしれない。この場合も、一応128ビット幅でフェッチしておいて、仕様しない場所の命令は無効化しておく必要がある。

つまり今回の場合は、

  • B+0x0は破棄する
  • B+0x04, B+0x08, B+0x0cを実行する

f:id:msyksphinz:20161109022131p:plain

f:id:msyksphinz:20161109084015p:plain