FPGA開発日記

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

UCBのAdvanced Computer Architectureの講義資料を読む(9. 分岐予測)

CPU コンピュータアーキテクチャ

コンピュータアーキテクチャの論文を読んでいたのだが、どうもよく知らない項目がある。 よく考えてみたらコンピュータアーキテクチャの最新トレンドも含め最近勉強量が不足していたので、ここらへんでもう一度復習しておきたい。 せっかくなので海外の大学の講義資料を読んでみよう。

  • Advanced Computer Architecture

https://www.ece.ucsb.edu/~strukov/ece154BSpring2018/home.htm

目次

Advanced Computer Architecture

5. 制御ハザードの処理

もっとも単純な制御ハザードの解決方法は、分岐のターゲットアドレスが解決するまでストールを挿入すること。しかし、こうしてしまうと動的スケジューリングに大きな影響が発生してしまう。とりあえずはループアンローリングを行うことで性能の低下を防ぐことができる。

別の方法としては、「遅延分岐」を挿入するという方法がある。分岐命令を実行した後に、1命令だけ遅延分岐命令を挿入することでストールを隠蔽する。MIPSは遅延分岐を採用しており、分岐命令を実行してもすぐにジャンプせず、後続の1命令を実行すことで分岐の遅延を隠蔽する。

もう一つの方法としては性的に分岐方向を予測するというもの。分岐を動的に予測するのではなく、

  • 常にTaken/Not Takenとして予測する （予測が外れたときに復帰する機能が必要となる）
  • よりより良い性能を得るためにプロファイリングを実行し、明示的に分岐方向を命令に埋め込む。

動的分岐予測

実行中に分岐方向を予測する方式。

  • 1ビットか2ビットの分岐予測
    • 各分岐命令において、Taken/Not Takenを予測する。もし分岐予測の結果が外れていれば、分岐方向を変える。
  • 相関分岐予測・2レベル分岐予測
    • 2ビットの分岐予測器をもっており、過去の$n$ビットの分岐の結果から次の分岐を予測する。
  • 局所分岐予測器
    • 各分岐に対して2ビットの分岐予測器をもっており、過去の$n$回の分岐結果を組み合わせて次の分岐を予測する。
  • トーナメント分岐予測
    • 相関分岐予測と局所分岐予測を組み合わせる。

分岐の履歴を保存するためにBHT（Branch History Table）を使用する。PCの下位のビットを使用して、1ビット値を格納する。過去の$n$回のビットがTaken/Not Takenなのかを格納している。このBHTではすべてのアドレスをチェックしない。

1ビットのBHTでは、2回の分岐予測ミスが発生する可能性がある。

ループの最後に、これまでのループ判定とは異なる結果が発生することで分岐予測ミスが発生する。そして次に同じループに入った時に、再びループ判定で分岐予測ミスを発生させてしまう。

そこで、2ビットの分岐予測を導入する。

f:id:msyksphinz:20200319234838p:plain

2ビットの分岐予測器を使用して、BHT内に2ビット分岐予測器を格納しておく。分岐命令のフェッチ時にBHTを使用して分岐予測を行う。分岐命令が完了した時点で、BHT内の当該分岐命令のテーブルをアップデートする。

f:id:msyksphinz:20200319234829p:plain

もう一つの方法は、分岐予測ミスが2回発生すると分岐の予測を変更する方式である。

f:id:msyksphinz:20200319234811p:plain

相関分岐予測

以下のようなプログラムを考える。B3は、B1とB2が成立する場合には必ず成立する。過去の分岐命令の情報に基づいて分岐予測を行う。

現在の分岐命令の動作は、過去に実行した分岐命令の結果に基づいているケースがある。過去の4つの分岐命令を使用して現在の分岐予測を実行する。

(2, 2)分岐予測器は、2ビットのグローバル分岐予測と、2ビットのローカル分岐予測を使用する。

f:id:msyksphinz:20200319234748p:plain:w300

それぞれの分岐予測器の精度

f:id:msyksphinz:20200319234737p:plain

グローバル分岐予測とローカル分岐予測について

  • グローバル分岐予測。BHRとPHTを使用して分岐を予測する。BHR（Branch History Register）、PHT（Pattern History Table）を使用する。
f:id:msyksphinz:20200319234715p:plain
  • ローカル分岐予測。BHT（Branch History Table）を使用する。PCのビットを元にしてエントリを選択する。
f:id:msyksphinz:20200319234701p:plain

トーナメント分岐予測

相関分岐予測は、2ビットのローカル分岐予測が重要な分岐で失敗する場合に、グローバルな情報を挿入することで性能を向上させる。一方でトーナメント分岐予測は2つの分岐予測を使用する。

  • グローバル情報を使用する分岐予測器
  • ローカル情報を使用する分岐予測器

正しい分岐予測を選択して、正しく分岐することが目的。

f:id:msyksphinz:20200319234650p:plain

分岐予測の精度。トーナメント分岐予測に対するローカル分岐予測の予測精度

f:id:msyksphinz:20200319234640p:plain

分岐予測精度

f:id:msyksphinz:20200319234618p:plain

分岐予測精度とサイズ

f:id:msyksphinz:20200319234601p:plain

BHT : 分岐アドレスを格納するためのテーブル

Branch Targett Buffer（BTB）：分岐命令のジャンプ先のアドレスを保存する。分岐命令のアドレスをマッチさせる必要性がある。そうでなければ誤った分岐アドレスを選択してしまう。

f:id:msyksphinz:20200319234545p:plain

BHTの選択フローは以下のようになる。

f:id:msyksphinz:20200319234535p:plain

関数呼び出しのためぬ分岐予測：Return Address Stack

戻り先の関数をスタックに格納しておく。

f:id:msyksphinz:20200319234518p:plain