分岐予測

分岐命令の動作を踏まえて分岐予測が導入されるまでの背景や、分岐予測の動作を記載する。

分岐予測が導入されるまでの背景

マイコンを動かすソフトウェアの中には、条件（データの値など）によって途中で処理を変える分岐命令があります（分岐命令の一例…データが0なら後続の命令を処理し、データが1なら外部デバイスにデータ転送するプログラムにジャンプする）。

　Label0:
　　…
　　LD　r2, 0x0(r3)
　　BEQ　r2, r4, Label1　//r2とr4（1が入っている）が等しければLabel1へ
　　…
　　J　　Label0

　Label1:　//外部デバイスにデータ転送
　　…

最近のマイコンは高速に動作させるため、命令キャッシュやデータキャッシュを持ち、アウトオブオーダー実行を採用し、パイプライン（命令フェッチ、実行、メモリ書き込みなどの各ステージ）が細分化されている（昔のパイプラインは5ステージ程度、今は10ステージ程度）。
このとき、分岐命令の判断結果を待つと、待った分だけ何も命令を処理できない時間が生じるので、マイコン性能に影響を及ぼす。

分岐予測の動作

上記のような分岐命令による悪影響をできるだけ改善するため、分岐命令が入る命令キャッシュに分岐予測テーブルを設置する。
基本的な分岐予測テーブルは下図の通り。命令キャッシュのindexが付与された各ライン毎に「2bitの分岐予測テーブル」がある。なお、「2bitの分岐予測テーブル」は、各ラインに格納できる分岐命令の個数分ある。例えば、各ラインに4個の分岐命令を格納できる命令キャッシュの場合、各ラインに「2bitの分岐予測テーブル」は4個あり（図では、各ラインに「2bitの分岐予測テーブル」が1個で、すみません）、4個が分岐命令に合わせて独立して動作している。
分岐予測の初期値は「分岐しない（強）」で始まり、分岐予測ミスすれば、「分岐しない（弱）」というように予測が変化する。分岐予測は2bitなので、

　「分岐しない（11…強）」　初期値
　　　　↓　↑
　「分岐しない（10…弱）」
　　　　↓　↑
　「分岐する（01…弱）」
　　　　↓　↑
　「分岐する（00…強）」

のような4つの予測を持つことになる。これらの予測をもとに分岐命令の処理を進め、できるだけマイコンが何も処理しない時間を作らないようにしている。
しかし、分岐予測はあくまで予測なので、予測が外れれば、予測に従って実行した処理は破棄して（レジスタの値やプログラムカウンタなどを元に戻して）、正しい処理を行うという、マイコンにとっては非常に忙しい状態になります。

図．命令キャッシュと分岐予測テーブル