分岐ミス予測（ぶんきよそく）

分岐ミス予測とは

分岐ミス予測（Branch Prediction）は、現代のCPUにおける性能向上のための重要な技術の一つである。CPUはプログラムの命令を順番に実行するが、条件分岐命令（if文など）に遭遇すると、どの命令を実行すべきか判断する必要が生じる。この判断を待っていると、CPUのパイプラインが停止し、処理効率が低下する。そこで、分岐ミス予測は、過去の分岐の傾向やプログラムの構造などを分析し、分岐が「taken（分岐する）」か「not taken（分岐しない）」かを事前に予測する。

分岐ミス予測の仕組み

分岐ミス予測には様々な手法が存在する。単純なものとしては、過去に分岐がtakenされた回数が多い場合は、今回もtakenされると予測する「ヒストリーテーブル」がある。より高度なものとしては、分岐命令のアドレスや周辺の命令列などを考慮し、複雑なパターンを学習する「パターンヒストリーテーブル」や、「パーセプトロン」などの機械学習を用いた予測器などが存在する。

分岐ミスが発生した場合

分岐ミス予測が外れた場合（分岐ミス）、CPUは誤って実行した命令を破棄し、正しい命令をフェッチして実行する必要がある。この処理には時間がかかり、CPUの性能低下を引き起こす。これを「分岐ペナルティ」と呼ぶ。分岐ペナルティを最小限に抑えるために、分岐ミス予測の精度向上が常に追求されている。

分岐ミス予測の重要性

分岐ミス予測は、特に複雑なプログラムやループ処理が多いプログラムにおいて、性能に大きな影響を与える。分岐ミス予測の精度が向上することで、CPUはより効率的に命令を実行できるようになり、プログラムの実行速度が向上する。現代の高性能CPUでは、分岐ミス予測の精度が90%を超えることも珍しくない。