분기 예측 (branch prediction)
쉽게 풀면
프로세서는 명령을 여러 단계로 나눠 동시에 처리하는데, 조건문을 만나면 어느 쪽 명령을 가져와야 할지 알 수 없어 멈칫하게 됩니다. 분기 예측기는 과거에 그 조건문이 주로 어느 쪽으로 갔는지 기록해 두었다가 그쪽을 미리 실행합니다. 맞으면 시간을 아끼고 틀리면 해 둔 일을 버리고 다시 시작합니다.
왜 중요한가
파이프라인이 깊어질수록 한 번의 예측 실패로 버려지는 작업이 커지기 때문에, 예측 정확도가 프로세서 성능을 좌우하는 핵심 요소가 되었습니다. 현대 예측기는 90% 후반대의 적중률을 보이며, 이 덕분에 조건문이 많은 일반 프로그램도 빠르게 실행됩니다. 조건 분기를 줄이는 방향의 코드 최적화가 효과를 내는 이유이기도 합니다.
논문에서는 이렇게 쓰입니다
조건의 결과가 규칙적이면 예측이 잘 맞아 같은 코드도 훨씬 빨라진다는 관찰입니다.
조금 더 깊게 보면
가장 단순한 형태는 분기마다 2비트 포화 카운터를 두어 최근 경향을 기억하는 방식이고, 여기에 최근 분기 결과들의 이력을 함께 색인에 쓰는 2단계 적응형 예측기, 서로 다른 이력 길이의 예측기를 경쟁시키는 TAGE 계열로 발전했습니다. 함수 복귀 주소를 위한 별도의 스택 구조도 함께 쓰입니다. 예측 실패 시에는 투기적 실행으로 진행한 결과를 모두 폐기하고 올바른 경로부터 파이프라인을 다시 채우므로 수십 사이클의 손실이 발생합니다.
주의할 점
예측이 틀려도 프로그램의 결과는 항상 올바르며 성능만 손해를 본다는 점이 중요합니다. 다만 예측 실패 시 폐기되는 작업이 캐시에 흔적을 남겨 부채널 공격의 통로가 될 수 있다는 점이 스펙터 취약점으로 드러났습니다.