分岐先予測
 |
 |
分岐先予測（英: Branch target prediction）とは、CPU内で分岐命令の分岐先アドレスを事前（命令キャッシュから命令をフェッチする前）に予測することである。
分岐先予測と分岐予測は異なる概念である。分岐予測は単に分岐するかしないかを予測することを指す。分岐先予測は、分岐命令を解析して分岐先アドレスが判明する前に、そのアドレスを予測することである。
近年では[いつ?]、命令キャッシュのキャッシュミス時のペナルティが大きくなり、フェッチ幅が大きくなってきている。このため、分岐先の決定がボトルネックになりつつある。このあたりの処理は次のようになる。
- 命令キャッシュがブロック単位で命令列をフェッチする。
- そのブロック内の命令が走査され、分岐を特定する。
- 分岐予測で分岐すると予測されている最初の分岐命令を特定する。
- その分岐命令の分岐先アドレスを計算する。
- そのアドレスを含むブロックを命令キャッシュにフェッチする。
この処理に2サイクルかかるとしたら、分岐すると予測された命令がみつかる度に1サイクルを無駄にしてしまうことになる。一般に10命令に一回分岐すると予測される命令があるとされ、フェッチ帯域幅が実質的に減少することになる。命令キャッシュのレイテンシが大きいマシンでは、さらに損失が大きくなる。これを何とかするため、一部のマシンでは分岐先予測を行う。これは、分岐命令自体のアドレスから分岐先アドレスを予測するものである。このとき、予測アドレスを格納しておく領域をBTB（Branch Target Buffer）と呼ぶ。もっと積極的な予測方法として、現在実行している逐次命令列の先頭アドレスから、次に実行する逐次実行命令列の先頭アドレスを予測する方式もある。
これによって、上記の処理が以下のように削減される。
- 実行する最初の命令のアドレスのハッシュ値を生成
- そのハッシュ値に対応した分岐先予測アドレスのリストをフェッチ
- その中から、分岐予測で分岐すると予測されているアドレスを選択する。
予測器が使うRAMは命令キャッシュの5%から10%のサイズであり、そのフェッチは命令キャッシュのフェッチよりもかなり前に行われる。そのため、分岐先の命令キャッシュへのフェッチを前倒しできる。これでも不十分な場合は、分岐先アドレスのリストを並列処理する場合もある。
外部リンク
[編集]- Radium Software Development
- BTBのエントリ有無を参照した分岐予測器の提案 斉藤史子、山名早人（早稲田大学）2004年3月