분기 예측: 아직 모르는 실행 경로를 먼저 선택하는 이유
CPU가 조건문의 결과를 확정할 때까지 다음 명령을 가져오지 못하면 긴 파이프라인이 비어 있을 수 있다. 분기 예측은 앞으로 어느 경로로 실행할지 추정해 일을 계속 공급하는 기법이다. 조건 분기의 실행 여부와 목적지 등 필요한 정보를 예측한다. 추정이 맞으면 대기를 줄이고 틀리면 잘못된 경로의 작업을 폐기하고 복구한다.
2비트 포화 카운터는 실제 분기 결과로 상태를 갱신하며, 강한 예측은 한 번의 반대 결과로 즉시 뒤집히지 않는다.
반복문은 일정한 패턴을 만든다
열 번 반복하는 루프의 끝에서 계속 반복할지 검사한다고 하자. 분기는 대부분 반복 경로로 가다가 마지막 한 번 빠져나간다. 항상 같은 경로를 추정하는 단순 정책도 이런 패턴에서는 어느 정도 효과를 낼 수 있다. 실제 CPU는 과거 분기 결과와 실행 문맥을 기록해 동적으로 예측하는 여러 구조를 사용한다.
한 비트 예측기는 직전 결과를 기억하는 모델이다. 루프 종료 때 반복하지 않았다는 결과로 바뀌면, 다음에 루프를 시작할 때 첫 반복을 잘못 예측할 수 있다. 두 비트 포화 카운터는 반복과 비반복에 각각 강한 상태와 약한 상태를 두어 한 번의 예외만으로 방향을 즉시 뒤집지 않게 한다.
두 번의 증거를 기다리는 모델
강하게 반복을 예상하는 상태에서 실제 비반복이 한 번 나오면 약하게 반복을 예상하는 상태로 이동한다. 여전히 다음 방향은 반복으로 예측한다. 또 비반복이 나오면 비반복 쪽으로 이동한다. 반대로 반복 결과가 나오면 카운터는 반복 쪽으로 움직인다. 끝 값에서 더 움직이지 않는 포화 규칙이 있어 상태는 네 개 안에서 유지된다.
이는 교육용 모델이며 현대 예측기를 모두 네 상태로 설명할 수는 없다. 분기들이 공유하는 이전 결과, 긴 이력, 목적지 정보 등 더 복잡한 관계를 이용할 수 있다. CMU의 현대 CPU 수업은 동적 분기 예측과 투기 실행의 관계를 다룬다. 같은 분기도 입력과 실행 문맥에 따라 예측 난도가 달라진다.
틀린 경로의 결과를 확정하지 않는다
예측을 따라 수행한 일은 조건이 검증될 때까지 투기적인 상태다. 오예측이 확인되면 이후 잘못된 경로의 결과를 최종 프로그램 상태로 확정하지 않고 올바른 경로에서 재개한다. 복구 비용은 파이프라인, 분기 해결 시점, 남아 있는 작업에 따라 달라진다. 모든 CPU에 고정된 오예측 사이클 수를 적용할 수 없다.
분기 예측의 성능은 정확도만으로 결정되지 않는다. 잘못 예측하는 빈도와 한 번 틀릴 때의 비용, 예측기 접근 시간, 코드의 분기 빈도를 함께 봐야 한다. 매우 드문 분기의 예측을 개선하는 일보다 자주 실행되는 큰 비용의 분기를 줄이는 일이 더 효과적일 수 있다. 예측 자체가 빠르게 다음 주소를 제공해야 하는 제약도 있다.
개발자는 데이터를 처리하는 방식이나 분기 구조를 바꿔 실행 패턴을 더 규칙적으로 만들 수 있다. 조건 선택을 연산으로 바꾸는 방법도 있지만, 필요 없는 계산과 메모리 접근이 늘어 오히려 느려질 수 있다. 컴파일러도 대상 CPU와 코드 특성에 맞춰 선택하므로 분기를 없애는 것을 무조건적인 목표로 삼지 않는다.
분기 예측은 미래를 정확히 알아내는 기능이 아니라 과거와 현재 정보로 실행 공급의 불확실성을 줄이는 구조다. 반복되는 입력과 불규칙한 입력에서 같은 코드의 성능이 달라지는 이유를 설명해 준다. 예측, 투기 실행, 결과 확정을 구분하면 정확성을 유지하면서도 일을 미리 진행하는 CPU의 원리를 이해할 수 있다.