분기
예측

분기가 파이프라인을 멈춘다

파이프라인은 매 cycle 다음 명령을 IF로 끌어온다. 그런데 분기는 어디로 갈지를 한참 뒤에야 안다.

if (x) goto L 같은 분기는 조건을 EX에서 계산한다. taken이면 저쪽으로 점프하고, not-taken이면 바로 다음 줄로 간다.
그 답이 나오기 전엔 다음 IF 주소가 정해지지 않는다.

그냥 기다리면 분기마다 파이프라인에 거품(bubble)이 생긴다. EX까지 비워두면 2 cycle을 통째로 날린다.
코드의 5~6명령에 하나꼴로 분기가 나온다. 매번 멈추면 파이프라인의 이득이 거의 사라진다.
그래서 답이 나오기 전에 일단 한쪽을 찍어 명령을 계속 채워 넣는다.

예측, 답 나오기 전에 먼저 찍는다

분기 예측기는 “이 분기는 taken일까 not-taken일까”를 미리 찍는 작은 장치다.

찍은 쪽 명령을 곧바로 파이프라인에 채워 넣는다. EX에서 진짜 방향이 밝혀진다.
맞았으면 멈춤 없이 그대로 흐른다. 예측이 공짜로 떨어진 셈이다.

틀렸으면 잘못 끌어온 명령들을 전부 버린다. 이걸 flush라 한다.
버린 칸만큼 다시 채워야 하니 그게 misprediction penalty다. 여기선 EX 뒤 2칸, 곧 2 cycle이다.
그래서 예측기의 목표는 단순하다. 최대한 자주 맞히는 것이다. 적중률 1%가 곧 버린 cycle이다.

1비트 · 2비트 예측기 · BTB

예측기는 점점 똑똑해진다. 가장 단순한 1비트부터 보자.

1비트는 직전 결과를 그대로 다음 예측으로 쓴다. 지난번 taken이었으면 이번도 taken으로 찍는다.
싸고 단순하지만 약점이 크다. 반복문 끝에서 딱 한 번 not-taken이 끼면, 그 한 번에 예측이 홱 뒤집혀 다음 반복 첫 분기까지 또 틀린다. 한 예외에 두 번 틀리는 셈이다.

2비트는 포화 카운터(0~3)를 둔다. 2 이상이면 taken, 아니면 not-taken으로 예측하고, 결과에 따라 한 칸씩만 오르내린다.
한 번 빗나가도 카운터가 한 칸만 움직여 예측 방향을 바로 안 뒤집는다. 그래서 가끔 끼는 예외에 흔들리지 않는다.

예측은 taken과 not-taken만이 아니다. taken이면 “어디로”도 필요하다.
BTB(Branch Target Buffer)는 분기 주소와 점프 목적지를 적어둔 작은 표다. IF 단계에서 바로 목적지를 꺼내 끊김 없이 그쪽 명령을 끌어온다.
방향은 카운터로, 목적지는 BTB로 잡는다. 둘이 짝을 이뤄야 진짜 예측이 된다.

직접 패턴을 먹여 적중률을 잰다

오른쪽에서 분기 패턴을 골라 1비트와 2비트에 동시에 먹여본다. 반복문, 엇갈림, 뭉치 패턴이 있다.

예측을 먼저 고른 뒤 STEP을 누르면 분기가 하나씩 진행된다. 적중과 miss(flush), 두 예측기의 카운터 변화가 함께 보인다.

“반복문 끝(TTT…NT)” 패턴을 보자. 1비트는 끼어든 NT 한 번에 다음 분기까지 두 번 틀리지만, 2비트는 카운터가 강T에서 한 칸만 내려가 곧장 회복한다.
엇갈림(TNTN)처럼 규칙 없는 분기는 둘 다 무력하다. 예측기가 못 따라잡는 한계도 같이 보인다.
여기서 고른 예측기가 그대로 최종 MyChip의 분기 예측기로 들어간다.

적중률과 penalty, 성능의 큰 변수

분기 예측은 성능에 직결된다. 한 번 틀릴 때마다 파이프라인을 통째로 비우기 때문이다.

miss 한 번은 penalty cycle을 버린다는 뜻이다. 파이프라인이 깊을수록(stage가 많을수록) 분기 결정이 뒤로 밀려 한 번의 miss가 더 비싸진다.
현대 CPU는 파이프라인이 15~20단을 넘기도 한다. miss 하나에 십수 cycle이 날아간다.

그래서 적중률이 95%냐 97%냐가 체감 성능을 가른다. 예측기 한 칸의 정확도가 코어 전체 속도를 좌우한다.
실제 칩의 예측기는 2비트를 넘어 과거 분기 이력(history)과 여러 예측기 조합까지 써서 99%에 육박하는 적중률을 낸다. 출발점은 여기서 본 1비트와 2비트다.