분기 예측

분기 예측(영어: branch prediction)은 다음 실행될 조건문이 어떤 곳으로 분기할 것인지를 확실히 알게 되기 전에 미리 추측하는 CPU 기술이다. 분기 예측기(branch predictor)는 분기 예측을 수행하는 디지털 회로를 가리킨다. 분기 예측을 수행하는 목적은, 명령어 파이프라인이 일시적으로 정지되지 않도록 하는 것이다. 최신 x86 아키텍처와 같이 많은 수의 파이프라인을 사용하는 구조에서 분기 예측기는 전체적인 성능을 크게 향상시킬 수 있다.

4단계 파이프라인의 예.

조건 분기 명령이 명령어 파이프라인에 입력되면, 조건 분기의 다음 명령은 둘 중 하나로 정해진다. 만약 파이프라인이 조건 값의 계산이 끝날 때까지 대기한다면, 조건 분기 명령이 전체 파이프라인을 통과할 때까지 다음 명령은 파이프라인에서 수행되지 못하고 대기하게 될 것이다. 분기 예측기는 이런 낭비를 막기 위해 단순한 알고리즘에 따라 다음 명령을 미리 추론한 후 미리 실행시킨다. 만약 분기 예측기의 예측이 맞으면 파이프라인은 낭비 없이 계속 수행되며, 예측이 틀릴 경우 미리 실행되던 명령이 파이프라인에서 모두 취소되고 올바른 명령이 다시 실행된다.

분기 예측기가 올바른 예측에 실패하면 파이프라인의 개수 만큼의 클럭 주기가 낭비된다. 복잡한 파이프라인 구조를 가진 현대 아키텍처에서는, 분기 예측기가 실패하면 10-20 클럭 주기가 낭비된다.

조건 분기문이 처음 파이프라인에 들어왔을 때 활용할 수 있는 정보는 많지 않다. 분기 예측기는 해당 조건 분기문이 분기한 이력이나 루프 구조, 함수 구조 등의 정보를 바탕으로 다음 분기를 예측한다.