CPU의 다양한 분기 예측 기법에 대해 알아보겠습니다.

본 글의 내용은 포항공과대학교의 CSED311의 내용을 기반으로
수업에서 다루지 않은 몇몇 내용을 추가하여 구성하였습니다.

분기 예측

분기 예측은 분기 결과가 결정되기 전에 분기를 미리 추측하여 CPU 파이프라인을 멈추지 않고 계속 명령어를 가져오는 기법입니다. 예측해야 할 것은 두 가지 입니다. 분기가 분기 조건을 만족하는 taken인지 not taken인지(방향 예측), 그리고 taken이면 어디로 뛰는지(목표 주소 예측)입니다.

분기 예측기는 IF 단계에서 다음 사이클에 가져올 주소를 결정합니다. 이때 taken과 not taken 중 어떤 주소를 가져올지는 분기 예측의 구현에 따라 다양한 최적화 방법을 이용하여 결정합니다.

파이프라인 후반부에서 실제 분기 결과가 확인됩니다. ID 또는 EX 단계에서, "이 명령어는 분기였고, 실제로는 taken이어서 목표 주소로 뛰었어야 한다/not taken이어서 다음 명령어를 가져오면 된다"라는 걸 알게 됩니다.

이때 분기 예측과 실제 결과를 비교합니다. 분기 예측기가 IF에서 선택한 주소와 실제 분기 결과가 같으면 아무 일도 일어나지 않습니다. 하지만 만약 분기 예측기가 틀렸다면, 그 사이에 잘못 가져온 명령어들을 파이프라인에서 무효화하고, PC를 올바른 주소로 되돌려서 다시 가져오기 시작합니다.

예를 들어 아래와 같은 코드가 있다고 합시다.

0x1000:  beq  x1, x2, TARGET   # 분기
0x1004:  add  x3, x4, x5       # 분기 실패(not taken) 시 실행
0x1008:  sub  x6, x7, x8
...
TARGET (0x2000):
0x2000:  or   x9, x10, x11     # 분기 성공(taken) 시 실행

CPU가 0x1000의 beq를 IF 단계에서 가져오는 순간, 분기 예측기가 동작하여 "이 분기는 not taken일 것이다"라고 예측했다고 가정해 봅시다. 그러면 다음 사이클에 CPU는 예측한 대로 0x1004의 add를 가져오고, 그 다음에는 0x1008의 sub를 가져옵니다. 분기 결과를 기다리지 않고 파이프라인이 계속 흘러갑니다.

몇 사이클 뒤, beq가 EX 단계에 도달하여 실제 분기 결과가 계산됩니다.

• 예측 성공: 실제로도 not taken이라면, 이미 가져와서 실행 중인 add, sub는 그대로 두면 됩니다. 분기로 인한 지연이 전혀 없습니다.
• 예측 실패: 실제로는 taken이었다면, add와 sub는 실행되면 안 되는 명령어입니다. 이 둘을 파이프라인에서 무효화(flush)하고, PC를 0x2000으로 되돌려 or부터 다시 가져오기 시작합니다. 이때 버려진 사이클만큼 분기 지연 페널티(branch penalty) 가 발생합니다.

결국 분기 예측기의 목표는 이 "예측 실패" 경우를 최소화하여 파이프라인이 멈추는 횟수를 줄이는 것입니다.

PC + 4 예측

PC + 4 예측은 가장 단순한 분기 예측 방식입니다. 분기를 무조건 not taken으로 예측하여, 분기 명령어 다음 사이클에도 그냥 PC + 4를 가져옵니다. 별도의 예측 하드웨어가 전혀 필요 없다는 장점이 있습니다.

문제는 정확도입니다. 실제 프로그램에서 분기의 약 60~70%가 taken인 것으로 알려져 있습니다. 특히 루프를 구성하는 역방향(backward) 분기는 거의 대부분 taken이기 때문입니다. 따라서 always not taken 예측의 per-branch 정확도는 대략 30~40% 수준에 불과합니다. 동전 던지기보다도 조금 나쁜 셈이죠.

데이터 해저드가 없고, 명령어의 20%가 분기, 분기의 70% 정도가 taken인 코드를 가정해 봅시다. PC + 4 예측은 모든 분기를 not taken으로 예측하므로, taken인 분기에서만 예측이 실패합니다. 따라서 전체 명령어 중 예측이 틀리는 비율은

$$ P_{\text{miss}} = 0.20 \times 0.70 = 0.14 $$

즉 약 14%, 뒤집어 말하면 예측이 맞을 확률은 약 86% 입니다.

성능은 IPC(Instructions Per Cycle)로 측정할 수 있습니다. 이상적인 경우 IPC는 1이고, 예측 실패로 인한 평균 스톨 사이클만큼 떨어집니다.

$$ \text{IPC} = \frac{1}{1 + P_{\text{miss}} \times \text{penalty}} $$

여기서 분기 지연 패널티는 분기가 파이프라인 어느 단계에서 결정되는지에 따라 달라집니다. 분기가 결정되는 단계가 뒤로 갈수록 그 사이에 IF로 가져와 버린 명령어들을 더 많이 버려야 하기 때문입니다.

분기가 MEM 단계에서 결정되는 경우, IF부터 MEM까지 3 사이클 차이이므로 예측이 틀리면 3 사이클을 버리게 됩니다.

$$ \text{IPC}_{\text{MEM}} = \frac{1}{1 + 0.20 \times 0.70 \times 3} = \frac{1}{1.42} \approx 0.70 $$

이상적 IPC 1.0에서 30% 나 떨어진 값입니다.

분기 결정을 EX 단계로 앞당기면 페널티가 2 사이클로 줄어듭니다.

$$ \text{IPC}_{\text{EX}} = \frac{1}{1 + 0.20 \times 0.70 \times 2} = \frac{1}{1.28} \approx 0.78 $$

MEM 대비 약 11% 개선됩니다.

ID 단계로 더 앞당기면 페널티가 1 사이클까지 줄어듭니다.

$$ \text{IPC}_{\text{ID}} = \frac{1}{1 + 0.20 \times 0.70 \times 1} = \frac{1}{1.14} \approx 0.88 $$

EX 대비 또 13% 가 개선됩니다. 하지만 분기 결정을 앞당기는 데에는 한계가 있습니다. ID 단계에서 분기 조건을 계산하려면 레지스터 파일 읽기와 비교 로직을 모두 해당 단계에 욱여넣어야 하며, 그 이상 앞당기는 것은 사실상 불가능합니다.

그러면 이제 남은 질문은 "0.7이라는 틀릴 확률 자체를 어떻게 줄일까?"로 바뀝니다. 즉, 예측 단계 자체의 정확도를 올려야 한다는 이야기입니다.

always taken 예측

앞선 가정에서 분기의 70%가 taken이었습니다. 그렇다면 모든 분기를 not taken이 아니라 taken으로 예측하면 어떨까요? 틀릴 확률이 0.7에서 0.3으로 줄어듭니다.

$$ P_{\text{miss}}^{\text{taken}} = 0.20 \times 0.30 = 0.06 $$

하지만 여기에는 새로운 문제가 있습니다. taken으로 예측하려면 분기의 목표 주소를 알아야 다음 사이클에 그 주소를 IF로 넣을 수 있는데, IF 단계에서는 아직 명령어를 가져오기 전입니다. 목표 주소는 명령어 안에 오프셋으로 인코딩되어 있으므로, 명령어를 디코드하기 전에는 어디로 뛸지 알 수 없습니다. 현재 PC만으로는 추측할 수가 없는 것입니다.

Branch Target Buffer

BTB(Branch Target Buffer)는 위에서 제기된 IF 단계에서 현재 PC만 보고 분기 목표 주소를 어떻게 아느냐는 문제를 해결하는 하드웨어입니다.

구조는 캐시와 비슷합니다. 분기 명령어의 PC를 키로, 이전에 뛰었던 목표 주소를 값으로 저장하는 테이블입니다. 분기가 처음 실행되어 결과가 확인되면, 그 분기의 PC와 목표 주소를 BTB에 기록해둡니다. 다음에 같은 PC에서 명령어를 가져올 때 BTB를 조회하면, 디코드하기 전에 "이 주소에는 분기 명령어가 있었고, 목표 주소는 여기다"를 바로 알 수 있습니다.

동작 과정을 보면, IF 단계에서 분기 예측기는 현재 PC로 BTB를 조회합니다. 미스하면 이 PC가 BTB에 없다는 뜻이니까, 분기가 아닌 것으로 간주하고 PC + 4에서 다음 명령어를 가져옵니다. 히트하면 이전에 이 PC에 분기가 있었다는 뜻이므로 taken으로 예측하고 BTB에 저장된 목표 주소에서 다음 명령어를 가져옵니다.

파이프라인 후반부에서 실제 분기 결과가 확인되면 BTB를 갱신합니다. 새로운 분기가 발견되면 항목을 추가하고 목표 주소가 바뀌었으면 갱신합니다.

Tagged BTB

BTB는 캐시와 구조가 동일하기 때문에, 캐시와 비슷한 방식으로 인덱싱하고, 동일하게 충돌 문제가 발생합니다. BTB 테이블은 크기가 유한하기 때문에 넓은 PC를 전부 인덱스로 사용할 수 없습니다. 대신 PC의 하위 비트 일부를 인덱스로 사용하여 테이블 항목을 찾습니다. 예를 들어 BTB의 항목 크기가 256개이면 PC의 하위 8비트로 인덱싱하여 저장합니다.

문제는 서로 다른 분기 명령어가 같은 인덱스에 매핑될 수 있다는 것입니다. PC가 0x1000인 분기와 0x2000인 분기가 하위 비트가 같으면 동일한 BTB 항목을 가리킵니다. 이러면 한쪽의 목표 주소가 다른 쪽을 덮어써서, 분기 예측기가 완전히 엉뚱한 주소로 점프해 버릴 수 있습니다. 이는 분기 예측이 틀리는 것보다 더 나쁜 상황인데, 아예 분기가 아닌 명령어로 점프해버려서 CPU가 완전히 잘못된 코드를 실행하기 때문입니다.

Tagged BTB는 이 충돌을 감지하기 위해 태그를 추가합니다. PC의 하위 비트로 먼저 인덱싱하고, 상위 비트를 태그로 함께 저장해둡니다. 조회할 때 인덱스로 항목을 찾은 뒤, 저장된 태그와 현재 PC의 상위 비트를 비교합니다. 태그가 일치하면 진짜 히트이고, 불일치하면 다른 분기가 이 슬롯을 차지하고 있다는 뜻이므로 미스로 처리합니다.

동적 분기 예측

지금까지는 분기를 taken과 not taken, 두 가지 중 하나로 고정하여 예측했습니다. 이러한 방식을 정적 분기 예측 (Static Branch Prediction) 이라고 합니다. 반면 동적 분기 예측 (Dynamic Branch Prediction) 은 프로그램 실행 중에 분기 결과 이력을 기록하고, 그 이력을 바탕으로 다음 예측을 조정하는 분기 예측 방식입니다.

정적 예측의 한계는 한 프로그램 안에 편향 방향이 전혀 다른 분기들이 섞여 있다는 점에서 드러납니다. 예를 들어 같은 프로그램 안에 다음 두 분기가 있다고 해 봅시다.

• 분기 A (루프 백에지): for (j = 0; j < 10; j++) 같은 구문의 종료 분기. 10번 중 9번 taken, 약 90% taken.
• 분기 B (에러 체크): if (err != 0) { handle(); } 같은 구문. 평상시에는 에러가 거의 발생하지 않으므로 약 1% taken.

"항상 taken"으로 고정 예측하면 A는 90% 맞지만 B는 1% 밖에 못 맞힙니다. 거꾸로 "항상 not taken"으로 고정하면 B는 99% 맞지만 A는 10%에 그칩니다. 어느 방향으로 고정하든 반대쪽 편향을 가진 분기를 거의 다 틀리게 됩니다.

통계적으로 "분기의 60~70%가 taken"이라는 건 평균일 뿐이고, 실제 개별 분기들은 대부분 거의 항상 taken이거나 거의 항상 not taken인 쪽으로 양극화되어 있습니다. 동적 예측기는 각 분기가 자신의 편향을 개별적으로 학습하기 때문에, A는 taken 방향으로 B는 not taken 방향으로 각자 수렴시켜 양쪽 다 높은 정확도를 달성할 수 있습니다.

Pattern History Table

PHT (Pattern History Table) 는 간단한 동적 분기 예측 방법 중 하나로, 분기 주소별로 카운터를 저장하는 테이블입니다. BTB와 동일하게, 분기 PC의 하위 비트로 인덱싱해서 해당 카운터를 읽고, 카운터 값에 따라 taken 혹은 not taken으로 예측합니다.

1비트 예측기

1비트 예측기는 PHT의 가장 단순한 형태입니다. 카운터는 0 혹은 1, 두 가지 상태를 가집니다. 지난번에 taken이었으면 1, not taken이었으면 0을 저장하고 다음에는 저장된 값 그대로 예측합니다. 문제는 예측이 너무 쉽게 뒤집힌다는 것입니다. 10번 반복하는 루프문에서 마지막에 not taken으로 빠져나가면 카운터가 0으로 바뀌고, 루프에 다시 진입하면 not taken으로 예측해서 또 틀립니다.

예를 들어 아래와 같은 중첩 루프를 생각해 봅시다.

for (int i = 0; i < 1000; i++) {
    for (int j = 0; j < 10; j++) {
        // ...
    }
}

안쪽 루프의 종료 분기 하나에 집중해 보겠습니다. 이 분기는 바깥 루프가 한 번 돌 때마다 총 10번 실행되고, 그중 9번은 taken(루프 계속), 마지막 1번은 not taken(루프 탈출)입니다. 1비트 예측기로 이 분기를 예측하면 어떻게 되는지 살펴보죠. 바깥 루프를 두 번째로 진입한 상황을 가정하고, PHT의 해당 카운터 초기값은 직전 바깥 루프 끝에 저장된 0(not taken)이라고 합시다.

10번 중 2번을 틀립니다. 루프 진입 시 한 번(직전 바깥 루프 탈출 때문에 카운터가 0이라 첫 반복에서 미스), 루프 탈출 시 한 번입니다. 정확도는 $\frac{8}{10} = 80\%$ 에 머뭅니다.

문제는 한 번의 실수가 다음 예측까지 오염시킨다는 점입니다. 10번 중 단 한 번 not taken이 나왔을 뿐인데, 그 때문에 다음번 루프 진입의 첫 반복도 같이 틀리게 되는 것이죠. 이 문제를 해결하기 위해 2비트 예측기가 등장합니다.

2비트 예측기

2비트 예측기는 1비트 예측기의 문제를 해결하기 위해 상태를 00(strongly not taken), 01(weakly not taken), 10(weakly taken), 11(strongly taken) 4개로 늘립니다. 예측은 상위 비트로 결정하고, 10과 11이면 taken, 00과 01이면 not taken입니다. 2비트 예측기는 상태 전이 방식에 따라 두 종류가 있습니다.

2비트 포화 카운터(Saturation) 는 taken이면 카운터를 1 올리고, not taken이면 1 내립니다. 단, 최대인 11과 최소인 00에서는 더 이상 변하지 않고 포화됩니다. strongly taken(11) 상태에서 한 번 틀리면 weakly taken(10)으로 가는데, 여전히 상위 비트가 1이라 taken으로 예측됩니다. 이러면 루프 끝에서 한 번 틀리는 것에 흔들리지 않으니까 기존 1비트 예측기의 문제가 해결됩니다.

2비트 이력 카운터(Hysteresis) 는 상태 전이 방식이 약간 다릅니다. 두 비트를 방향 비트와 이력 비트로 나눠서 해석합니다. 예측은 상위 방향 비트가 결정하고, 이력 비트는 "방향 비트를 바꿀지 말지" 판단할 때 쓰입니다.

상태 전이 규칙은 세 가지입니다. 예측이 맞으면 이력 비트를 1로 설정하고 strong 상태가 됩니다. 예측이 틀렸는데 strong(이력=1)이면 이력 비트만 0으로 내리고 weak 상태가 됩니다. 예측이 틀렸는데 weak(이력=0)이면 방향 비트를 뒤집고 이력 비트를 1로 설정합니다.

포화 카운터와의 차이는 뒤집히는 순간에 있습니다. 포화 카운터에서 10(weakly taken)이 틀리면 01(weakly not taken)으로 갑니다. 하지만 이력 카운터에서는 10(weakly taken)이 틀리면 01(strong not taken)으로 가서 바로 strong 상태로 시작합니다. 방향을 바꾸는 데에는 두 번 연속 틀려야 한다는 점은 같지만, 바꾼 후에 확신도가 다른 겁니다.

실질적으로 두 방식의 예측 정확도 차이는 크지 않은 것으로 알려져 있고, 대부분의 현대 CPU는 포화 카운터를 사용합니다. 중요한 것은 한 번 틀렸다고 바로 예측을 뒤집지 않고, 두 번 연속 틀려야 바꾸는 것입니다.

앞서 1비트 예측기를 분석할 때 썼던 중첩 루프 예시를 2비트 포화 카운터로 다시 돌려 봅시다. 안쪽 루프의 종료 분기가 바깥 루프 한 번당 10번 실행되고, 9번은 taken, 1번은 not taken이라는 상황입니다.

이전 바깥 루프 끝에서 카운터 상태가 어떻게 저장되었는지부터 추적해 보죠. strongly taken(11) 상태로 루프에 들어와 9번 연속 맞히고, 10번째에 한 번 틀리면 카운터는 weakly taken(10)으로 내려가 거기서 바깥 루프를 탈출합니다. 즉 PHT에 남는 상태는 10입니다.

이제 바깥 루프가 다시 돌아와 안쪽 루프에 재진입합니다.

10번 중 단 1번만 틀립니다. 1비트 예측기에서는 루프 탈출(10번째 반복)과 루프 재진입(1번째 반복) 양쪽에서 틀렸지만, 2비트 예측기는 탈출 한 번의 오답으로 11 → 10으로만 내려갈 뿐 상위 비트가 여전히 1이라 재진입 시 여전히 taken으로 예측합니다.

Global Path History

2비트 State Machine 기반 분기 예측은 PHT 크기가 충분하다는 가정하에 90% 내외의 정확도를 가지는 것으로 알려져 있습니다. 나머지 10% 미만은 복잡한 패턴의 분기입니다. 이전에 설명했던 암달의 법칙에 따르면, 이 부분을 개선하더라도 전체 CPU 속도는 크게 변하지 않을 것 같습니다. 10% 미만을 개선하더라도 전체 속도에 미치는 영향은 미미할테니까요.

하지만 현대 CPU 들은 위 분기 예측기보다 복잡하고 더 정확한 분기 예측 기법을 사용합니다. 더 복잡한 회로가 들어가면 비용이 많이 늘어날텐데, 왜 약간의 정확도를 높이기 위해 이렇게 하는걸까요?

그 이유는 CPU의 파이프라인이 깊어지면서 예측 실패 패널티가 훨씬 커졌기 때문입니다. 5단 파이프라인에서 분기 예측 정확도를 1% 정도 늘렸을 때 그 영향은 미미합니다. 분기 예측에 실패하더라도 날리는 사이클은 고작 몇 사이클 정도니까요. 하지만 10단, 20단 이상의 현대 CPU에서는 한 번의 분기 예측 실패가 몇십 사이클을 날려버리기 때문에, 분기 예측 정확도를 1% 늘리는 것의 가치가 더 커집니다.

현대 CPU에서 사용하는 분기 예측 방식 중 대표적인 것은 Global Path History입니다. 분기 예측기에서 PHT를 인덱싱할 때, 최근 분기들의 결과 뿐만 아니라 분기의 주소 정보까지 함께 사용하는 방식입니다.

왜 주변 분기의 결과가 도움이 되는지, 간단한 예시를 하나 보죠. 다음과 같이 서로 상관관계가 있는 세 분기가 한 프로그램에 있다고 해 봅시다.

if (x == 0) { ... }            // B1
if (y == 0) { ... }            // B2
if (x == 0 && y == 0) { ... }  // B3

B3의 결과는 완전히 결정적입니다. B1과 B2가 모두 taken이었다면 B3도 반드시 taken, 그렇지 않다면 반드시 not taken입니다. 이론상 100% 맞힐 수 있는 분기죠.

그런데 앞서 본 2비트 PHT가 B3 하나만 따로 본다면 어떻게 될까요? 프로그램 실행 중 (x, y) 값이 매번 달라지므로, B3의 결과는 이 예측기 입장에서는 taken과 not taken이 무작위로 섞여 들어오는 것처럼 보입니다. 카운터는 계속 흔들리고, 정확도는 잘해야 (x, y) = (0, 0)인 비율에 수렴할 뿐입니다. B3 자체의 PC만 보는 한, 이 상관관계를 포착할 방법이 없습니다.

Global Path History 예측기는 최근 실행된 분기 몇 개의 taken/not taken 결과를 GHR(Global History Register) 에 담아 둡니다. 이름 그대로 프로그램 전체에서 공유되는(global) 단 하나의 레지스터로, 분기 결과가 나올 때마다 한 비트씩 시프트하여 가장 최근 N개의 결과를 유지합니다. 예를 들어 2비트 GHR이 있다면, B3에 도달한 시점의 GHR은 직전 두 분기(B1, B2)의 결과를 가지고 있습니다.

이 GHR 값을 B3의 PC와 섞어 PHT를 인덱싱하면, 네 경우가 서로 다른 PHT 항목에 매핑됩니다. 각 항목은 자기 GHR 상황에서의 B3 결과만 학습하므로, (T, T) 항목은 항상 taken으로 수렴하고 나머지 세 항목은 항상 not taken으로 수렴합니다. B3 하나를 두고 보면 결과가 무작위로 보였던 것이, GHR로 구분해 주면 각 "맥락" 안에서 완벽한 결정적 패턴이 되는 것이죠. 이렇게 하면 B3의 정확도는 100%에 가까워집니다.

일반화하면, Global Path History는 분기 하나의 결과가 주변 분기들과 상관관계를 가질 때 그 상관관계를 PHT 인덱스에 녹여 넣어, 단일 2비트 예측기로는 잡을 수 없던 패턴까지 학습하게 해 줍니다.

GShare Branch Predictor

앞선 설명에서 "GHR 값을 B3의 PC와 섞어 PHT를 인덱싱한다"고 뭉뚱그렸는데, 이 "섞는다"를 구체적으로 어떻게 할지가 사실 남은 과제입니다. 이 부분에 대한 가장 간단하면서 널리 쓰이는 해답이 1993년 Scott McFarling이 제안한 GShare 예측기입니다.

먼저 왜 그냥 GHR이나 PC 하나만 쓰면 안 되는지부터 짚고 가야 합니다. PHT를 GHR만으로 인덱싱한다면, PC가 전혀 다른 두 분기라도 우연히 GHR이 같은 순간에 도달하면 동일한 PHT 항목을 공유하게 됩니다. 서로 상관없는 분기들이 같은 카운터를 놓고 치고받으며 예측을 망치는 aliasing(별칭 충돌) 이 심하게 일어납니다. 반대로 PC만 쓰면 앞서 본 평범한 PHT와 똑같아져, 주변 분기와의 상관관계를 전혀 잡지 못합니다.

그럼 PC와 GHR을 이어붙이면 어떨까요? 예를 들어 PC 하위 6비트와 6비트 GHR을 붙여 12비트 인덱스를 만들면 PHT 항목 수는 $2^{12} = 4096$개가 됩니다. 모든 (PC, GHR) 조합이 각자 독립된 항목을 갖게 되어 aliasing은 해결되지만, 이번에는 PHT 크기가 두 비트 폭의 곱만큼 커져야 합니다. 게다가 실제 프로그램에서 쓰이는 (PC, GHR) 조합은 그중 극히 일부뿐이라, 대부분의 항목은 전체 프로그램에서 한 번도 건드려지지 않고 낭비됩니다.

GShare의 아이디어는 단순합니다. PC와 GHR을 XOR해서 인덱싱하는 것입니다.

$$ \text{index} = \text{PC}[n-1:0] \oplus \text{GHR}[n-1:0] $$

PHT가 $2^{12}$ 항목이라면 PC의 하위 12비트와 12비트 GHR을 XOR해 12비트 인덱스를 얻습니다. 테이블 크기는 그대로 $2^{12}$인데, 인덱스 안에 PC와 GHR 정보가 둘 다 녹아 들어가게 됩니다. 이어붙이기처럼 테이블을 키우지 않고도 두 정보를 모두 활용할 수 있는 것이죠.

물론 GShare도 완벽하지는 않습니다. 서로 다른 두 (PC, GHR) 쌍이 XOR 결과는 같을 수 있기 때문입니다. 예를 들어 PC = 0x100, GHR = 0x010과 PC = 0x010, GHR = 0x100은 XOR이 똑같이 0x110이 되어 버립니다. 이런 파괴적 충돌(destructive aliasing)을 더 줄이기 위해 이후에 Bi-Mode, Agree Predictor, TAGE 같은 더 정교한 예측기가 등장하게 됩니다. 하지만 GShare는 "PC ⊕ GHR"이라는 한 줄짜리 아이디어만으로 Global Path History의 장점을 대부분 얻어내는 방식이라, 1993년 이후 오랫동안 사실상의 표준으로 쓰였고 지금도 새 예측기를 평가할 때의 기준선으로 자주 등장합니다.

Two-Level Branch Predictors

보다 일반적으로, 분기 예측기를 하나의 프레임워크로 정의하기도 합니다. 이 프레임워크는 1991-92년 Yeh와 Patt가 Two-Level Adaptive Branch Prediction이라는 이름으로 정리했으며, 이후 상용 CPU의 분기 예측기는 거의 전부 이 틀 안에서 조금씩 변형되는 형태로 발전해 왔습니다.

이름의 "Two-Level"은 예측이 두 단계의 저장 구조를 거쳐 내려진다는 뜻입니다. 1단계는 BHR(Branch History Register) 로, 최근 분기 결과를 비트열로 기록하는 레지스터입니다. 앞서 본 GHR은 이 BHR을 전역으로 하나만 두는 특수한 경우였는데, Two-Level 프레임워크에서는 뒤에서 볼 것처럼 분기별 또는 집합별로 BHR을 둘 수도 있기 때문에 더 일반적인 이름인 BHR로 부릅니다. 2단계는 PHT로, 1단계의 히스토리 값을 인덱스로 삼아 조회하는 2비트 포화 카운터 테이블입니다.

여기서 재밌는 점은, 1단계와 2단계 각각을 어떻게 구성할지에 여러가지 선택지가 있다는 것입니다. 각 단계에 대해 Yeh와 Patt는 세 가지 선택지를 제시했습니다.

• Global (G/g): 프로그램 전체가 공유하는 단 하나의 구조를 둡니다. 1단계라면 전역 BHR 한 개, 2단계라면 전역 PHT 한 개입니다. 하드웨어 자원이 가장 적게 들고, 분기들 사이의 상관관계를 자연스럽게 포착할 수 있습니다. 대신 서로 무관한 분기들이 같은 구조를 공유하면서 생기는 aliasing 문제가 큽니다.
• Per-address (P/p): 분기 PC마다 자기만의 구조를 둡니다. 1단계라면 분기 PC별로 별도의 BHR을, 2단계라면 분기 PC별로 별도의 PHT를 두는 방식입니다. 각 분기가 자기 이력과 패턴을 독립적으로 학습하므로 aliasing이 거의 없지만, 필요한 엔트리 수가 분기 수만큼 늘어나 하드웨어 비용이 큽니다.
• Per-set (S/s): 분기들을 몇 개의 그룹(집합)으로 나누고, 그룹 단위로 구조를 둡니다. 일반적으로 PC의 일부 비트로 집합 번호를 정하고, 같은 집합에 속한 분기들이 하나의 BHR 또는 PHT를 공유합니다. Global과 Per-address의 중간 지점으로, 하드웨어 비용을 적당히 낮추면서 aliasing도 어느 정도 줄이는 절충안입니다.

Yeh와 Patt는 이 조합을 세 글자 표기 XAY로 정리했습니다. 첫 글자 대문자는 1단계 조직 방식(G/P/S), 가운데 A는 "Adaptive"의 고정 글자, 마지막 소문자는 2단계 조직 방식(g/p/s)을 의미합니다. 1단계 3가지 × 2단계 3가지이므로 총 9가지 조합이 가능합니다.

Tournament Predictor

여기까지 본 예측기들은 모두 "하나의 예측 방식"을 택해 프로그램 전체의 분기를 그 방식으로 예측합니다. 하지만 실제 프로그램의 분기들은 성격이 제각각이라, 어떤 분기는 지역 히스토리(자기 과거 결과)가 가장 큰 단서가 되고, 또 어떤 분기는 주변 분기와의 상관관계(전역 히스토리)가 핵심입니다. 예를 들어 앞서 본 중첩 루프의 종료 분기는 자기 과거 패턴이 그대로 반복되므로 지역 예측기가 유리하고, B3 같은 상관관계 분기는 직전 분기들의 결과가 결정적이므로 전역 예측기가 유리합니다.

그렇다면 이 둘을 둘 다 돌려놓고, 분기마다 더 잘 맞는 쪽을 골라서 쓰면 어떨까요? 이 아이디어의 구현 중 가장 유명한 것이 DEC Alpha 21264(1998) 의 Tournament Predictor입니다. Scott McFarling이 1993년 기술보고서에서 제안한 combined predictor 구조를 실제 상용 CPU에 처음 채택한 사례로, 오랫동안 분기 예측 교과서의 대표 예시로 인용되어 왔습니다.

21264의 예측기는 세 개의 서브 테이블로 구성됩니다.

1. Local Predictor (PAp 구조): 분기 PC별로 10비트 지역 히스토리를 유지하는 1024 엔트리짜리 BHR 테이블과, 그 히스토리로 인덱싱되는 1024 엔트리 3비트 카운터 PHT를 둡니다. 자기 과거 패턴이 뚜렷한 분기에 강합니다.
2. Global Predictor: 12비트 전역 히스토리 레지스터를 두고, 이 값으로 4096 엔트리 2비트 카운터 PHT를 인덱싱합니다. 상관관계 기반 분기에 강합니다.
3. Choice Predictor: 이름 그대로 어느 예측기를 믿을지를 예측하는 예측기입니다. 전역 히스토리로 인덱싱되는 4096 엔트리 2비트 카운터 테이블로, 각 카운터 값은 "지금 상황에서는 local이 맞을 가능성이 큰가, global이 맞을 가능성이 큰가"에 대한 학습된 답입니다.

매 분기마다 세 테이블이 동시에 조회됩니다. Local과 Global이 각자 taken/not taken 예측을 내놓고, Choice가 그중 하나를 "더 믿을 만한 쪽"으로 지목하면 그 결과를 최종 예측으로 사용합니다. 분기 결과가 확정되면 local과 global 예측기 각각의 카운터는 평소처럼 갱신됩니다. Choice 예측기 쪽은 조금 특별하게 동작합니다. 두 예측기 중 한 쪽만 맞혔을 때만 choice 카운터를 움직여, 맞힌 쪽으로 기울게 만듭니다. 둘 다 맞았거나 둘 다 틀린 경우에는 choice를 건드리지 않는데, 이 경우 어느 쪽이 더 나은지에 대한 정보가 사실상 없기 때문입니다.

이렇게 해서 21264는 분기의 성격에 따라 동적으로 가장 적합한 예측기를 골라 씁니다. 순수 PAp나 순수 gshare 어느 한쪽만 쓰는 것보다 정확도가 눈에 띄게 높았고, 당시 벤치마크에서 약 90-100% 수준의 예측 정확도를 보였습니다. 이후 등장한 많은 고성능 CPU가 형태는 달라도 이 여러 예측기 + chooser 아이디어를 그대로 계승하게 됩니다.

다른 분기 예측 기법들

지금까지 설명한 BTB와 PHT 기반 예측기들은 조건 분기의 방향(taken/not taken)과 목표 주소를 예측하는 일반적인 방법들입니다. 하지만 실제 CPU는 그 외에도 특정 상황에 특화된 기법들을 여러 가지 함께 사용합니다. 이 절에서는 그중 자주 언급되는 몇 가지를 간략하게만 살펴봅니다.

Return Address Stack

함수 반환(return) 명령은 지금까지 설명한 BTB만으로는 잘 예측되지 않습니다. 같은 return 명령(=같은 PC)이 실행될 때마다 돌아갈 곳이 달라지기 때문입니다. foo라는 함수가 서로 다른 수십 군데에서 호출된다면, 그 함수의 return 명령은 호출 지점에 따라 수십 개의 서로 다른 목표 주소를 가져야 합니다. BTB는 "이 PC는 지난번 어디로 뛰었는가"만 기억하므로, 호출 지점이 바뀔 때마다 예측이 틀리게 됩니다.

Return Address Stack(RAS) 는 이 문제를 해결하기 위해 CPU 안에 두는 작은 하드웨어 LIFO 스택입니다. 동작은 단순합니다. call(함수 호출) 명령을 만나면 다음 명령 주소(PC + 4)를 RAS에 push하고, return 명령을 만나면 RAS에서 pop한 값을 예측 목표 주소로 사용합니다.

여기서 한 가지 궁금한 점이 생깁니다. IF 단계에서는 아직 명령어를 디코드하지 않았는데, 지금 가져오는 PC가 return인지 일반 분기인지 어떻게 알고 RAS와 BTB 중 어느 쪽을 써야 할지 결정할까요? 답은 BTB 엔트리에 분기 타입 정보까지 같이 저장해둔다는 것입니다. 분기가 처음 실행되어 디코드될 때 conditional / call / return 등의 타입이 BTB에 함께 기록되고, 다음번 같은 PC를 페치할 때 BTB 히트가 "이건 return이다"라고 알려주면 그 순간 목표 주소를 BTB 대신 RAS에서 pop해 쓰는 방식입니다. 즉 RAS와 BTB는 "둘 중 하나를 고르는" 관계가 아니라, BTB가 타입 디스패처 역할을 하고 그에 따라 RAS가 동원되는 구조입니다.

RAS는 보통 8~32 엔트리 정도의 작은 원형 버퍼로 구현되기 때문에, 재귀가 그 깊이를 넘어가면 가장 오래된 엔트리가 덮어써지면서 오버플로우가 납니다. 이때 오버플로우 구간의 return들은 RAS에서 잘못된 주소를 얻어 예측이 틀리지만, 재귀가 어느 정도 풀려 다시 RAS 깊이 안쪽으로 돌아오면 그 이후의 return은 정상적으로 복구됩니다. 중요한 건 이것이 어디까지나 성능 손실일 뿐 정확성 문제가 아니다라는 점입니다. 실제 return 주소는 메모리 스택 프레임에 그대로 저장되어 있고, EX 단계에서 실제 목표 주소가 확인되는 순간 파이프라인을 비우고 올바른 곳으로 점프할 뿐, 프로그램이 엉뚱한 곳으로 돌아가는 일은 없습니다. 현대 CPU는 거의 예외 없이 이 RAS 구조를 기본 탑재하고 있습니다.

Trace Cache

Trace Cache는 엄밀히 말하면 분기 예측 기법이 아니라 명령어 페치 경로의 최적화입니다. 하지만 분기 처리 성능에 직접적인 영향을 주기 때문에 자주 함께 언급됩니다.

일반적인 I-cache는 명령어를 주소 순서대로 저장합니다. 그래서 taken 분기를 만나면 목표 주소로 점프한 뒤 다음 cache line을 새로 읽어야 해서, 한 사이클에 여러 기본 블록을 가로질러 명령어를 가져오기가 어렵습니다. 파이프라인이 깊고 한 사이클에 많은 명령어를 페치해야 하는 고성능 CPU에서는 이것이 병목이 됩니다.

Trace Cache는 대신 실행 순서대로 명령어를 저장합니다. 프로그램이 실제로 실행한 경로(taken 분기를 따라 이어지는 기본 블록들의 연속)를 하나의 "trace"로 묶어 캐시에 저장해두고, 다음번 같은 경로를 만나면 여러 기본 블록에 걸친 명령어들을 한 번에 페치할 수 있게 합니다. 게다가 명령어가 미리 디코드된 형태로 저장되기 때문에 디코드 단계의 부담도 덜어집니다.

Intel Pentium 4(NetBurst 마이크로아키텍처, 2000) 가 이 방식을 대표적으로 채택했지만, 명령어 중복 저장으로 인한 낮은 밀도와 높은 전력 소비 때문에 Core 2에서는 폐지됩니다. 이후 Intel은 Sandy Bridge(2011)부터 비슷한 아이디어를 훨씬 작은 규모의 µop Cache 형태로 되살려 오늘날까지 쓰고 있습니다.

TAGE

TAGE(TAgged GEometric history length predictor)는 André Seznec이 2006년에 발표한 예측기로, 현재까지 알려진 가장 정확한 분기 예측 방식 중 하나이며 Intel Haswell(2013) 이후 프로세서, AMD Zen 계열, Apple Silicon 등 대부분의 현대 고성능 CPU가 변형 형태로 채택하고 있습니다.

핵심 아이디어는 짧은 히스토리로 예측되는 분기와 매우 긴 히스토리가 필요한 분기가 한 프로그램에 섞여 있다는 것입니다. 대다수 분기는 몇 비트의 히스토리만으로도 정확히 예측되지만, 소수의 까다로운 분기는 수십~수백 비트에 이르는 긴 히스토리가 있어야 패턴이 드러납니다. 그렇다고 모든 분기에 수백 비트 히스토리를 붙이면 테이블이 거대해지고 aliasing이 심해집니다.

TAGE는 이 문제를 기하급수적으로 증가하는 히스토리 길이를 가진 여러 개의 테이블로 해결합니다. 예를 들어 히스토리 길이가 0, 4, 10, 25, 64, 160 비트인 6개의 테이블을 두고, 각 테이블은 자신만의 히스토리 길이로 인덱싱됩니다. 캐시의 tag처럼 각 엔트리에 태그를 붙여 "이 엔트리가 진짜 이 분기와 이 히스토리에 대한 것인지"를 검증합니다.

예측 시에는 모든 테이블을 동시에 조회한 뒤, 태그가 일치하는 테이블 중 가장 긴 히스토리를 쓰는 것의 예측을 최종 결과로 사용합니다. 태그가 하나도 안 맞으면 가장 짧은 히스토리(기본 bimodal)로 대체하고요. 이렇게 하면 짧은 히스토리로 충분한 분기는 짧은 테이블에서 처리되고, 긴 히스토리가 필요한 까다로운 분기는 긴 테이블에서 태그가 일치할 때 그쪽 예측을 따릅니다. 테이블 개수는 로그적으로 커질 뿐인데 다룰 수 있는 히스토리 범위는 기하적으로 넓어지는 것이 이 구조의 힘입니다.

TAGE는 여러 분기 예측 대회(Championship Branch Prediction Workshop)에서 오랫동안 1위를 차지했으며, 후속 변형인 TAGE-SC-L, TAGE-GSC 등이 계속 제안되고 있습니다.

Perceptron Predictor

Perceptron Predictor는 Jiménez와 Lin이 2001년에 제안한, 분기 예측을 머신러닝 문제로 바라보는 접근입니다. 퍼셉트론(1950년대 신경망의 조상)은 입력 벡터와 가중치 벡터의 내적을 계산해 부호에 따라 이진 분류를 내리는 가장 단순한 선형 분류기인데, 이 구조를 분기 예측에 그대로 가져온 것입니다.

각 분기는 자신만의 가중치 벡터를 가집니다. 입력은 전역 히스토리 레지스터의 각 비트(+1 또는 -1로 해석)이고, 가중치는 작은 정수(예를 들어 -127~127 범위)로 저장됩니다. 예측은 가중치와 히스토리 비트를 내적해서 합이 양수면 taken, 음수면 not taken으로 결정합니다. 분기 결과가 확인되면 틀렸거나 확신이 부족했던 경우에만 각 가중치를 해당 히스토리 비트 방향으로 조금씩 움직여 학습시킵니다.

이 방식의 가장 큰 강점은 매우 긴 히스토리를 선형 비용으로 쓸 수 있다는 점입니다. 기존 PHT 방식은 히스토리가 $n$비트면 테이블이 $2^n$만큼 필요한 반면, 퍼셉트론은 가중치가 $n$개만 필요하므로 수백 비트 히스토리도 현실적으로 지원됩니다. 덕분에 긴 범위의 상관관계가 필요한 분기에서 두드러지게 잘 동작합니다.

약점도 분명합니다. 퍼셉트론은 선형 분류기라서 XOR 같은 선형 분리 불가능한(linearly inseparable) 패턴은 학습할 수 없습니다. 예를 들어 "직전 두 분기가 서로 다른 결과였을 때 taken, 같은 결과였을 때 not taken" 같은 패턴은 단일 퍼셉트론으로는 정확히 예측되지 않습니다.

AMD Bulldozer(2011) 가 이 방식을 상용 CPU에 처음 채택한 것으로 알려져 있으며, 이후 AMD Piledriver, Jaguar 계열 등이 변형된 형태로 사용했습니다. AMD Zen 부터는 TAGE 계열로 넘어가는 추세지만, perceptron은 여전히 하이브리드 예측기의 한 구성요소로 활용되는 경우가 많습니다.

컴파일러의 분기 최적화

지금까지 본 것은 하드웨어가 런타임에 동적으로 분기를 예측하는 방법들이었습니다. 하지만 분기 예측 성능을 끌어올리는 또 다른 축은 컴파일러입니다. 컴파일러는 소스 코드의 구조와 정적 분석 결과, 혹은 프로파일 정보를 활용해 분기 자체를 줄이거나, 예측기에 유리한 코드 배치를 만들거나, 심지어는 분기를 완전히 없애버리기도 합니다.

If-conversion

예측이 아무리 정확해도 틀릴 가능성 자체를 0으로 만들지는 못합니다. 그렇다면 "예측하지 않아도 되게" 분기 자체를 없애버리면 어떨까요? 이것이 If-conversion(혹은 predication)의 아이디어입니다. 컴파일러가 조건 분기를 조건부 명령어(predicated instruction) 로 변환해서, 결과적으로 양쪽 경로의 코드를 둘 다 실행하되 조건에 맞는 쪽의 결과만 레지스터에 반영하도록 만드는 방식입니다.

예를 들어 다음 코드를 봅시다.

if (a > 0) x = y + 1;
else       x = y - 1;

일반적인 컴파일에서는 a > 0 비교 결과로 조건 분기를 내고, 두 경로 중 하나만 실행합니다. If-conversion을 적용하면 대략 이렇게 바뀝니다.

cmp  a, 0
(p1) x = y + 1   ; p1이 참일 때만 커밋
(p2) x = y - 1   ; p2가 참일 때만 커밋

분기 없이 두 명령어 모두 실행되지만, 결과는 predicate 비트에 따라 한쪽만 레지스터에 반영됩니다. 분기가 아예 사라졌으므로 예측 실패라는 개념이 없는 것이죠. 대신 양쪽 경로를 항상 실행하므로 작업량이 늘고, 경로가 길거나 불균형하면 오히려 손해입니다. 그래서 if-conversion은 주로 짧고 균형 잡힌 분기에 선택적으로 적용됩니다.

ARM(ARM32 이전 명령어 세트는 거의 모든 명령어가 조건부였습니다), Intel Itanium(IA-64 전면 predication), 그리고 GPU(모든 warp 내 분기를 predication으로 처리)가 이 기법을 적극 사용한 대표적인 예입니다. x86/x86-64는 전면 predication은 없지만 cmov 같은 제한적인 조건부 이동 명령을 통해 비슷한 최적화를 부분적으로 지원합니다. 예를 들어 다음 코드는 x86-64에서 분기 없이 cmov로 컴파일되는 경우가 많습니다.

int max(int a, int b) {
    return (a > b) ? a : b;
}

cmp  edi, esi
cmovg eax, edi    ; a > b이면 eax에 a를 넣음
cmovle eax, esi   ; 그렇지 않으면 eax에 b를 넣음

정적 분기 힌트 (Static Branch Hints)

개발자가 특정 분기의 편향 방향을 이미 알고 있을 때, 그 정보를 컴파일러에게 직접 알려 줄 수 있습니다. GCC/Clang의 __builtin_expect가 대표적입니다. Linux 커널에서 널리 쓰는 likely() / unlikely() 매크로가 이 빌트인을 감싼 것입니다.

#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

void process(int *p) {
    if (unlikely(p == NULL)) {
        handle_error();
        return;
    }
    // ... 일반 처리 ...
}

이 힌트가 있으면 컴파일러는 일반 처리 경로를 fall-through(분기 없이 곧장 이어지는 경로)에 배치하고, 드문 에러 처리 경로를 함수 뒤쪽이나 별도 섹션으로 빼서 점프하도록 코드를 재배치합니다. CPU 입장에서는 드물게 쓰이는 에러 코드가 I-cache와 BTB를 오염시키지 않게 되고, 자주 쓰이는 정상 경로는 straight-line code로 유지되어 페치 효율이 올라갑니다.

C++20부터는 표준으로 [[likely]] / [[unlikely]] 속성이 추가되어, 빌트인 없이도 같은 최적화를 요청할 수 있습니다.

if (value < 0) [[unlikely]] {
    throw std::invalid_argument("negative");
}

Rust는 오랫동안 #[cold] 속성을 관용구로 써 왔습니다. 드문 경로를 별도 함수로 빼고 #[cold]를 붙이면, 컴파일러가 해당 호출 지점을 unlikely로 간주하고 코드를 재배치합니다.

#[cold]
#[inline(never)]
fn handle_error() -> ! {
    panic!("invalid input");
}

fn process(p: Option<&i32>) {
    let Some(v) = p else { handle_error() };
    // ... 일반 처리 ...
}

Rust 1.83부터는 std::hint::likely / std::hint::unlikely가 stable로 승격되어, C++20과 비슷한 감각으로 쓸 수도 있습니다. 다만 커뮤니티에서는 여전히 #[cold] 함수 패턴이 더 널리 쓰입니다.

Profile-Guided Optimization (PGO)

개발자가 수동으로 힌트를 붙이는 데에는 한계가 있습니다. 수십만 개의 분기 하나하나에 likely/unlikely를 달 수도 없고, 사실 사람이 추측한 편향이 실제 실행 통계와 어긋나는 경우도 많습니다.

PGO(Profile-Guided Optimization) 는 이 문제를 실제 프로파일 측정으로 해결합니다. 보통 두 단계로 동작합니다.

1. Instrumented build: 컴파일러가 각 분기마다 카운터를 삽입한 바이너리를 만듭니다. 이것을 대표적인 워크로드로 실행해서 "어느 분기가 얼마나 자주 taken되는지"에 대한 통계를 수집합니다.
2. Optimized build: 수집된 프로파일을 다시 컴파일러에 입력으로 넣어, 측정된 편향 방향에 맞춰 코드를 재배치합니다. 뜨거운 경로를 straight-line으로 펼치고, 드문 경로는 뒤로 보내고, 인라인 결정도 프로파일 기준으로 조정합니다.

GCC에서는 -fprofile-generate → 실행 → -fprofile-use 순서로, Clang에서는 -fprofile-instr-generate → -fprofile-instr-use로 PGO를 적용합니다. 대규모 서버 코드에서는 수 %에서 10% 이상의 성능 향상이 관찰되기도 합니다. Google, Facebook 같은 회사들은 내부 인프라 대부분을 PGO로 빌드하며, 최근에는 LLVM의 AutoFDO처럼 샘플링 프로파일러(perf)로 얻은 데이터를 그대로 PGO에 사용하는 방식도 널리 쓰입니다.

블록 재배치 (Basic Block Placement)

PGO나 정적 힌트가 주는 편향 정보를 실제로 활용하는 가장 중요한 최적화 중 하나가 블록 재배치입니다. 컴파일러는 함수 안의 기본 블록들을 실행 빈도에 따라 배치 순서를 바꿉니다.

int f(int x) {
    if (x < 0) {
        return -1;          // 드문 경로
    }
    return compute(x);      // 자주 쓰이는 경로
}

기본 블록이 소스 순서대로 배치되면, x >= 0인 흔한 경우에 "조건 분기 → taken → 목표 주소로 점프"가 필요합니다. 컴파일러가 흔한 경로를 fall-through로 배치하면, 이를 "조건 분기 → not taken → 그대로 다음 명령 실행"으로 바꿀 수 있습니다. taken 분기가 not taken 분기보다 페치 측면에서 약간 더 비싸기 때문에 이 작은 차이가 누적되면 무시할 수 없습니다.

더 나아가 컴파일러는 아주 드문 경로(예외 처리, 에러 로그, cold 초기화) 를 함수 밖의 .text.cold 같은 별도 섹션으로 이동시키기도 합니다. 이렇게 하면 I-cache에는 hot 경로만 올라오고, 드물게 쓰이는 코드는 아예 별도 페이지로 분리되어 cache와 TLB 부담을 크게 줄일 수 있습니다.

Itanium의 brp와 TAR

한 걸음 더 나아가, Intel Itanium(IA-64) 은 "코드 배치"를 ISA 수준의 명령어로 확장해 컴파일러가 분기 예측기에 직접 힌트를 쏘는 전용 명령어를 제공했습니다. Itanium이 표방한 EPIC(Explicitly Parallel Instruction Computing) 철학, 즉 "하드웨어가 동적으로 판단하는 것을 컴파일러가 최대한 정적으로 떠맡는다"는 방향과 맞닿아 있는 기능입니다.

brp (Branch Predict) 는 분기 예측기를 미리 준비시키는 명령어입니다. "앞으로 이 PC에 분기가 올 것이고, 그 목표 주소는 여기이며, 방향은 이쪽이다" 를 하드웨어에 미리 알려, CPU가 실제 분기 명령을 만나기 전에 BTB와 예측 카운터 상태를 갖춰두도록 합니다. 일종의 소프트웨어 주도 분기 예측 프리페치인 셈이죠.

brp.sptk  target_addr, clr       # 곧 target_addr로 가는 분기가 옴
                                 # strongly taken으로 예측 요청
...
// (여러 명령어 뒤)
br.cond   target_addr            # 실제 분기 — 이미 예측기가 준비되어 있음

일반 하드웨어 예측기는 같은 분기를 두 번째 만났을 때부터 제대로 예측할 수 있지만, brp를 쓰면 첫 실행조차도 이미 예측이 준비된 상태에서 맞힐 수 있다는 점이 핵심 차이입니다.

TAR (Target Address Register) 는 간접 분기를 위한 장치입니다. Itanium의 간접 분기는 점프 목표를 일반 레지스터가 아니라 전용 Branch Register(b0~b7)에서 읽어 오는데, 이 구조 위에 별도의 목표 주소 레지스터와 그 내용을 미리 예측기에 연결해 두는 메커니즘이 얹혀 있습니다. 컴파일러가 간접 분기의 목표 주소를 아주 이른 시점에 TAR에 실어 두면, 나중에 실제 br.call 같은 명령이 실행될 때 예측기가 이미 목표를 알고 있어 미스프리딕션 없이 뛸 수 있습니다. 가상 함수 호출이나 함수 포인터 호출처럼 일반적인 BTB로는 예측이 어려운 분기에서 유용합니다.

Itanium의 brp와 TAR은 "하드웨어 예측기가 학습할 때까지 기다리지 말고, 컴파일러가 미리 답을 넣어 주자" 는 접근입니다. 이론적으로는 매우 강력하지만, 실제로는 컴파일러가 분기 동작을 충분히 정확히 예측해서 힌트를 붙이는 것 자체가 어려웠고, Itanium 자체의 상업적 실패와 함께 주류에서 사라졌습니다. 그래도 ISA에 분기 예측 힌트를 직접 넣는다는 아이디어 자체는 이후 여러 연구 프로세서와 일부 임베디드 ISA에 영향을 남겼습니다.

루프 언롤링 (Loop Unrolling)

루프의 종료 분기는 반복 횟수만큼 자주 실행됩니다. 루프 언롤링은 루프 본체를 여러 번 펼쳐서 반복 횟수 자체를 줄이는 최적화입니다.

// 원래
for (int i = 0; i < n; i++) {
    sum += a[i];
}

// 4배 언롤
for (int i = 0; i < n; i += 4) {
    sum += a[i];
    sum += a[i+1];
    sum += a[i+2];
    sum += a[i+3];
}

분기 예측 관점에서 이득은 두 가지입니다. 첫째, 종료 분기의 실행 횟수가 n에서 n/4로 줄어 분기 명령 자체의 비용이 줄어듭니다. 둘째, 루프 본체가 커지면서 명령어 수준 병렬성(ILP) 을 더 확보할 수 있어 OoO 엔진이 일을 더 잘 풀어낼 수 있습니다. 단점은 코드 크기가 커져 I-cache 압박이 늘어나는 것이라, 컴파일러는 언롤 횟수를 신중하게 결정합니다.

함수 인라이닝 (Function Inlining)

call과 return 명령 자체도 분기입니다. RAS 덕분에 예측 정확도는 높지만, 명령어 수가 늘어나고 레지스터 저장/복원 오버헤드도 발생합니다. 함수 인라이닝은 작은 함수의 본체를 호출 지점에 직접 삽입해 call/return 쌍을 아예 제거합니다.

static inline int square(int x) { return x * x; }

int sum_of_squares(int a, int b) {
    return square(a) + square(b);
    // 인라이닝 후: return (a * a) + (b * b);
}

호출 오버헤드가 사라질 뿐 아니라, 인라이닝된 코드가 호출 컨텍스트 안의 상수나 타입 정보와 결합되어 추가 최적화의 기회를 열어주는 효과가 더 큽니다. 컴파일러는 함수 크기, 호출 빈도, 재귀 여부 등을 고려해 인라이닝 여부를 결정하고, PGO 정보가 있으면 훨씬 공격적으로 인라이닝을 수행합니다.