2016/11/09 図に誤りあり。一部差し替えました。
CPUにおける分岐予測といえば、複数命令を同時発行させる現代のCPUにおいて不可欠な技術であり、投機実行の技術を支える重要な高速化技法であるが、だいたいのの解説書の場合、以下のような記述で説明がなされている。
以下の図はComputer Architecture Quantitative Approach, Fifth Editionより抜粋
- 作者: David A. Patterson
- 出版社/メーカー: Morgan Kaufmann
- 発売日: 2011/09/30
- メディア: ペーパーバック
- 購入: 1人 クリック: 4回
- この商品を含むブログ (2件) を見る
この図では、ステージ名がかろうじて書いてあるが、じゃあ実際にどうやって実装すれば良いんだろう?考えてみると、いろいろ複雑だ。
- 分岐予測はどのステージで実行する? ** それに伴い、どの段階で命令フェッチを分岐予測に沿って変更すれば良い?
- 分岐予測が当たったかどうかは、どのステージで判定すれば良い? ** 判定基準は?
- 複数命令幅を同時にフェッチしてくるようなスーパスケーラのプロセッサでは、どのように実現すれば良い?
これらのことを考えながら、さらにどのような信号を定義するか、またどのような制御を組むかを考えなければならない。
分岐予測はどのステージで実行する?
分岐予測は、
- 予測元となるプログラムアドレス
- 予測先となるプログラムアドレス
の組で実現される。この予測元となるプログラムアドレスは、IFUつまり命令フェッチユニットから情報が得られる。 このプログラムアドレスは、例えばAXIなどで命令ワード幅以上の命令をフェッチしてくる場合は、複数のアドレスから調査する必要がある。
MIPSで0x1fc0_0000から命令を128ビット幅でフェッチしてきた場合、128ビット幅、つまり命令4つ分(0x1fc0_0000, 0x1fc0_0004, 0x1fc0_0008, 0x1fc0_000c)で分岐予測すべきアドレスが無いか、調査する必要がある。
分岐予測の結果、得られる情報は?
分岐予測テーブルで、当該プログラムアドレスで分岐予測をすべきか調査した結果、ある命令で分岐予測できるということが分かった場合、情報を取得する。
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を実行する