saturating counter predictor: 반복문 끝의 한 번을 얼마나 믿을까
반복문이 계속 돌아가는 동안은 분기가 taken이고, 마지막에만 not-taken이 된다. 직전 결과 하나를 기억하는 예측기는 끝에서 한 번 틀린 뒤 다음 반복문의 첫 진입에서도 틀리기 쉽다. 잠깐의 예외 하나에 예측 방향을 곧바로 뒤집었기 때문이다. saturating counter predictor는 여기에 작지만 유용한 완충을 넣는다.
이 완충은 무조건 정확도를 올리는 장치가 아니다. 한 번의 예외에 흔들리지 않는 성질은 실제 패턴이 바뀌었을 때 반응을 늦추는 성질이기도 하다. 작은 상태기계를 입력 열에 직접 실행하면 이 교환을 확인할 수 있다.
네 상태가 기억하는 방향의 강도
설명을 위해 일반적인 2비트 포화 카운터를 정하자. 값은 0, 1, 2, 3이고 0·1에서는 not-taken, 2·3에서는 taken을 예측한다. 실제 taken이면 한 단계 증가하고, not-taken이면 한 단계 감소한다. 3에서 증가하거나 0에서 감소하면 그 끝값을 유지한다. 예측은 현재 상태로 하고 업데이트는 이번 결과를 안 뒤 수행한다.
값 3은 taken이라는 방향뿐 아니라 그 방향을 한 번의 반대 결과로 버리지 않겠다는 강도까지 담는다. 3에서 not-taken을 관측하면 2로 내려가지만 다음 예측은 여전히 taken이다. 두 번째 not-taken을 관측하면 1이 되어 그다음부터 방향이 바뀐다. 이처럼 상태가 경계를 지나야 출력이 바뀌는 성질을 히스테리시스라고 부른다.
BOOM의 BPD 문서도 2비트 표에서 상위 비트를 예측, 하위 비트를 강도로 설명한다. 다만 실제 BOOM 문서는 SRAM 읽기·쓰기 구조를 위해 약한 상태에서 틀렸을 때 반대쪽 강한 상태로 이동하는 변형도 명시한다. 아래 숫자 예는 먼저 정의한 일반적인 증가·감소 카운터를 따른다. 같은 ‘2비트’ 이름만으로 모든 구현의 상태 전이가 같다고 가정하면 안 된다. BOOM BPD, The Two-bit Counter Tables
반복문 끝의 한 번을 어떻게 견딜까
분기 결과가 T,T,T,N을 반복한다고 하자. 각 반복문이 세 번 계속되고 한 번 빠져나가는 가상의 패턴이며, 분기 하나의 상태에 다른 분기가 끼어들지 않는다고 가정한다. 상태는 다음 조회 전에 갱신되고 충분히 학습한 이후를 비교한다.
1비트 예측기는 N을 본 뒤 다음 예측을 N으로 바꾼다. 그래서 다음 묶음의 첫 T에서 틀리고, 마지막 N에서도 틀린다. 네 번 중 두 번이 틀린다. T 세 번 사이에는 상태가 T여서 맞는다.
2비트 카운터는 첫 T 전에 2 또는 3에 있다. 세 번의 T를 지나면 3이고, 마지막 N에서 틀리며 2가 된다. 다음 묶음의 첫 T는 여전히 T로 예측하여 맞고 다시 3이 된다. 네 번 중 마지막 한 번만 틀린다. 오예측률이 이 모델에서는 50%에서 25%로 줄어든다. 이것은 보편적인 CPU 성능 수치가 아니라 정의한 분기 열의 상태 추적 결과다.
강도가 도움이 된 것은 대부분 T인 패턴에서 고립된 N이 있었기 때문이다. ‘최근 결과를 잘 기억하는가’보다 ‘고립된 반대 결과에 얼마나 반응할 것인가’가 차이를 만든 셈이다.
완충이 오히려 늦추는 경우
이제 T가 끝나고 N이 계속 이어지는 새로운 구간으로 바뀌었다고 하자. 상태 3에서 시작한 2비트 카운터는 첫 N과 둘째 N을 모두 T로 예측한다. 3→2→1로 내려간 뒤 세 번째 N부터 맞힌다. 직전 결과만 쓰는 1비트 방식은 첫 N 이후 곧바로 N으로 바뀐다. 길게 지속되는 경향의 전환에는 강도가 비용이 된다.
교대로 바뀌는 T,N 열은 더 날카로운 반례다. 위 2비트 카운터를 상태 1에서 시작하면 T를 N으로 예측하고 2가 된다. 이어 N을 T로 예측하고 1로 돌아온다. 이 두 상태를 반복하면서 매번 틀린다. 상태 2에서 같은 열을 시작하면 T는 맞고 N은 틀려 절반이 맞는다. 입력 열만 적고 초기 상태를 생략하면 다른 결과를 설명하지 못한다.
분기의 방향이 최근 다른 분기의 결과와 관계를 가지는 경우에도 카운터 하나는 충분하지 않을 수 있다. 같은 상태에 다른 상황들이 섞이면 한 방향으로 강해지는 동안 다른 상황에서는 틀린다. 실제 설계에서는 어떤 PC와 문맥이 어느 카운터를 조회하는지, 다른 분기가 그 상태를 공유하는지까지 봐야 한다. 상태 전이와 표의 주소 선택은 별개의 설계 변수다.
업데이트 시점도 현실의 차이다. 결과가 확정되기 전에 같은 반복문의 다음 분기가 이미 예측될 수 있다. 앞의 즉시 업데이트 모델에서 얻은 오류 횟수를 그대로 긴 파이프라인에 적용할 수는 없다. 초기화와 warm-up 구간도 측정에서 구분해야 한다.
saturating counter predictor의 강점은 모든 패턴을 외우는 데 있지 않다. 한쪽으로 치우친 분기에서 짧은 예외를 견디는 것이다. 네 상태를 실제 결과 열에 한 단계씩 대입해 보면, 그 강점이 생기는 조건과 강도 때문에 놓치는 조건을 함께 볼 수 있다.