分岐予測【branch prediction】

概要

分岐予測（branch prediction）とは、CPU(マイクロプロセッサ)の高速化手法の一つで、実行中のプログラムに現れた分岐命令によって命令の流れがいずれに分岐するかを予測し、パイプライン処理の効率を高める仕組み。

パイプライン処理では前の命令が終わる前に次の命令の実行を始めることで実行効率を高めるが、条件分岐命令が存在する場合、その次にどの命令を実行するかは条件の評価が行われるまで確定しないため、パイプラインに投入する命令列に空白が生じてしまう。

分岐予測は分岐が行われるか否かを過去の履歴などから予測し、予測に基づいて次に実行されると思われる命令を投機的にパイプラインへ投入し始める（投機的実行）。予測が当たればパイプラインに空白を空けずに効率よく処理を進めることができ、外れた場合は処理途中の命令群は破棄され、正しい分岐先の命令列が改めて実行される。

予測手法には様々なものが提唱されているが、正答率を向上させようとすると複雑な処理が必要となり、回路規模や予測自体にかかる時間も増大する。その分だけ予測が成功した際に得られるメリットを打ち消してしまうというジレンマがある。

(2024.1.15更新)