コンピュータアーキテクチャの話 (174) 分岐先アドレスを予測する

　分岐先予測

　分岐予測は条件分岐が成立するか不成立かを予測するものであるが、分岐が起こる場合には、分岐命令を実行して分岐先のアドレスを計算し、分岐先の命令をフェッチして来なければならない。ということで、分岐方向を予測するだけでなく、分岐が起こる場合は、分岐先のアドレスを予測することができれば、分岐先の命令を早くフェッチすることが可能となり性能を向上させることができる。

　図7.6 Branch Target Address Cacheの構造

　分岐先アドレスを予測するには、図7.6のような分岐命令の分岐先のアドレスを格納するキャッシュ(Branch Target Address Cache:BTAC)を設けて、分岐予測機構と並列にアクセスする。BTACは、命令アドレスをインデックスとしてアクセスするキャッシュであるが、命令が条件分岐命令であり、かつ、条件分岐がTakenの場合だけ、その分岐先アドレスを記憶しておく。このキャッシュはBTACあるいは、BTB(Branch Target Buffer)と呼ばれる。そして、分岐予測を行うのと並行してこのキャッシュをアクセスし、分岐命令の実行を待たずにBTACから読まれたアドレスを次の命令アドレスとして命令フェッチを開始する。

　レジスタの内容をアドレスとして分岐を行う場合は、分岐先は可変であるが、一般にプログラムの中に現れる条件分岐命令の分岐先は命令アドレスからのオフセットで記述されており、分岐先のアドレスは毎回一定であるので、BTACの内容は書き換える必要はない。(ただし、BTACのエントリ数は1024～8192程度であり、キャッシュラインの競合によって追い出されることはあるし、レジスタ間接分岐の場合は分岐先アドレスが変わる)。したがって、予測が正しく、かつ、BTACにヒットした場合は、高い確率で正しい分岐先のアドレスが得られる。

　BTACは分岐先アドレスの予測値を与えるだけであり、予測エラーがあっても処理を誤ることは無いが、 BTACをアクセスすると常に何らかのアドレスが出てきてしまうので、タグマッチを行わないと、無駄な命令フェッチが多くなってしまう。図7.6のようにタグマッチを行いBTACにヒットした場合は、条件分岐命令はTakenとみなして分岐先アドレスの予測値を得て、分岐先の命令フェッチを開始するという構造が使われるケースが多い。ただし、この場合、命令やデータキャッシュのような完全な一致は必須ではなく、重なりを減らせば十分である。このため、すべての上位アドレスを使ったタグマッチではなく、上位アドレスの一部やハッシュを使ってビット数を圧縮したタグマッチが用いられる。

　プログラムの中には分岐先がプログラムカウンタの値(=命令アドレス)からのオフセットで決まる分岐命令だけでなく、レジスタに格納された値が分岐先となるレジスタ間接分岐も存在する。このレジスタ間接分岐の場合は、レジスタを読まないと分岐先のアドレスは得られないので、命令のデコード時点では分岐先の予測が難しい。

　しかし、レジスタ間接分岐が使われる典型的なケースは、関数(FORTRANではサブルーチン)からの戻りのケースである。関数の呼び出し時にCall命令を実行すると、Call命令の次の命令の番地を特定のレジスタに書き込んで関数の先頭に分岐し、関数の処理を終わると、Return命令でこのレジスタの内容を分岐先アドレスとしてレジスタ間接分岐を行うと、Call命令の次の命令に戻って実行が継続されることになる。

　一般的には、この関数呼び出しと復帰のシーケンスはペアになっており、かつ、呼び出しと復帰に用いる命令が決まっているので、呼び出し時に戻りアドレスを専用のスタックにプッシュし、復帰時にスタックをポップしてやれば、復帰アドレスを格納したレジスタの内容を読まなくても正しい戻り先アドレスが得られる。このようなスタックを「Return Address Stack(リターンアドレススタック)」といい、最近のプロセサでは一般的に実装されている。

　しかし、メインプログラムから関数Aを呼び出し、関数Aから関数Bを呼び出すというケースで、関数Bでエラーを検出した場合などが典型的であるが、呼び出し階層をすっ飛ばしてメインプログラムに直接リターンするようなケースもあり、そのような場合にはプッシュとポップのペア関係が崩れてしまうので、予測が誤ってしまう。

　また、Javaなどの最近のオブジェクト指向言語では、レジスタ間接分岐が多く、これまで述べてきた機構だけでは、予測が困難になってきているという問題もあり、リターンアドレススタックですべてのレジスタ間接分岐の予測ができるというわけではない。

　以上、述べたように、複数の命令を同時発行するスーパスカラプロセサでは分岐方向の確定を待って次の命令のフェッチを始めるのでは、長いストールが発生して性能が上がらないため、分岐予測という機構が導入され、大きな性能改善を実現した。そして、予測精度を改善してさらに性能を向上させるために、どんどんと複雑な予測機構が実装されるようになってきた。

　しかし、分岐予測機構の高度化による性能向上は飽和する傾向にあり、それを実装するためのチップ面積や消費電力の負担がメリットを上回るようになってきている。また、予測が成功すれば良いのであるが、失敗した場合は、本来は実行する必要のない命令を実行し、分岐方向が確定した時点で、それらの命令の結果を捨てて、正しい方向の命令を実行することになる。この誤った方向の命令の実行に使われたエネルギーは無駄なエネルギーであり消費電力を増大させる。このため、予測の難しい(成功率の低い)条件分岐命令を無理に予測せず、マルチスレッド方式で、別スレッドの確実に実行される命令を実行するなど、電力あたりの処理命令数を増加させるという考え方も出てきており、マルチスレッドのプロセサ全体として性能と電力効率を改善する方向が研究されている。