arch · 12

분기 예측

CPU파이프라인분기예측

파이프라인 CPU는 명령어를 겹쳐 실행하기 위해 다음 명령어를 미리 가져옵니다. 그런데 분기(branch) 명령은 어디로 갈지가 실행 단계 무렵에야(구현에 따라 단계는 다릅니다) 확정되므로, 그 전에 다음 명령어를 가져오려면 결과를 예측해야 합니다. 맞으면 파이프라인이 멈추지 않고, 틀리면 잘못 가져온 명령어를 버리고 다시 시작해야 합니다.

핵심 개념

분기 해저드

분기 결과(taken 또는 not-taken)가 확정되기 전에는 다음에 가져올 명령어 주소를 알 수 없어 파이프라인이 멈출 수 있습니다.

핵심 개념

정적 예측

실행 기록과 무관하게 규칙 하나로 예측합니다. "항상 taken"이나 "뒤로 가는 분기는 taken" 같은 방식입니다.

핵심 개념

동적 예측

분기 주소의 일부 비트로 찾는 하드웨어 테이블(BHT)에 과거 결과를 기록하고, 그 기록을 보고 예측합니다. 반복되는 패턴에 강합니다.

핵심 개념

1비트 예측기

직전 결과 하나만 기억해 그대로 다음을 예측합니다. 반복문이 끝날 때와 다시 시작할 때 연속으로 두 번 틀립니다.

핵심 개념

2비트 포화 카운터

0~3 사이 카운터를 씁니다. 강한 상태(0 또는 3)에서는 한 번 어긋나도 예측을 바로 뒤집지 않고, 같은 방향으로 두 번 어긋나야 예측이 바뀝니다.

핵심 개념

예측 실패 비용

틀리면 잘못 가져온 명령어를 버리는 flush가 일어납니다. 낭비되는 사이클 수는 분기가 확정되는 단계의 깊이에 비례합니다.

파이프라인이 깊을수록 실패가 비쌉니다 — 이 시각화는 5단계에서 2사이클을 잃지만, 실제 고성능 CPU는 파이프라인이 훨씬 깊어 예측 실패 한 번에 십수 사이클을 잃습니다.

1비트가 항상 정적 예측보다 낫지는 않습니다 — 반복문의 루프 분기에서는 종료할 때와 재진입할 때 두 번 틀려서, "항상 taken"으로 고정한 정적 예측보다 적중률이 낮아질 수 있습니다.

예측은 보안과도 연결됩니다 — 예측이 틀렸을 때 버려지는 명령어의 흔적이 캐시에 남는 점을 이용한 공격이 Spectre입니다. 성능을 위한 추측 실행이 부작용을 남길 수 있습니다.

이 시각화에서 확인할 것 — "파이프라인 페널티" 탭에서 예측 성공과 실패의 흐름 차이를, "1비트 vs 2비트" 탭에서 상태 변화를, "적중률 비교" 탭에서 패턴별 정확도를 STEP으로 확인하세요.

예측기가 맞혀야 하는 두 가지

예측기가 맞혀야 할 것은 두 가지입니다. 하나는 분기가 일어날지(taken) 아닐지(not-taken)이고, 다른 하나는 일어난다면 어느 주소로 갈지입니다. 방향은 이 토픽에서 본 1비트 · 2비트 예측기가 맡고, 목표 주소는 분기 명령어 주소별 목적지를 기억하는 분기 목표 버퍼(BTB, Branch Target Buffer)가 맡습니다. 함수에서 돌아오는 return은 호출한 곳이 매번 달라 BTB로는 잘 맞지 않아서, 호출 때 반환 주소를 쌓아 두는 반환 주소 스택(RAS)을 따로 두는 CPU가 많습니다.

예측 실패의 비용을 숫자로 보면

설명용 값으로 계산해 보겠습니다. 분기가 전체 명령어의 20%이고 예측이 틀리면 15사이클을 잃는다고 가정하면, 명령어당 평균 손실은 0.2 × (1 − 적중률) × 15사이클입니다.

적중률 95% — 0.2 × 0.05 × 15 = 명령어당 0.15사이클

적중률 99% — 0.2 × 0.01 × 15 = 명령어당 0.03사이클

읽는 법 — 예측 실패율이 5%에서 1%로 줄면 손실이 5분의 1로 줄어듭니다. 실패 비용이 크고 분기가 자주 나오기 때문에, 적중률의 작은 차이도 성능에 영향을 줍니다.

자주 하는 오해

예측이 틀리면 프로그램 결과가 틀려진다 — 예측해서 실행한 명령어의 결과는 분기가 확정될 때까지 확정(커밋)되지 않고, 예측이 틀리면 폐기됩니다. 프로그램 결과의 정확성은 유지되고 손해는 낭비된 시간입니다. 다만 캐시 같은 내부 상태에는 흔적이 남을 수 있고, Spectre가 이를 이용합니다.

if 문이 많으면 느리다 — 같은 분기라도 결과가 규칙적이면 적중률이 높습니다. 문제가 되는 것은 예측하기 어려운 분기입니다. 그래서 데이터가 정렬되어 분기 결과에 규칙적인 패턴이 생기면 같은 반복이 빨라지는 경우가 있습니다.

분기 예측은 컴파일러가 하는 일이다 — 실행 중의 결과 기록을 보고 예측하는 것은 하드웨어입니다. 일반 응용 프로그램이 예측 알고리즘 자체를 바꾸지는 못합니다(OS 같은 특권 코드가 일부 예측기를 제어하거나 무효화하는 장치는 있습니다). GCC의 __builtin_expect나 C++20의 [[likely]], [[unlikely]]로 어느 쪽이 더 자주 일어나는지 컴파일러에 알려 최적화에 참고하게 하거나, 데이터와 코드를 예측하기 쉽게 바꾸는 정도입니다.

분기를 없애면 항상 빨라진다 — 조건부 이동 같은 분기 없는 코드는 예측 실패 비용이 없지만, 양쪽 계산을 모두 실행하고 결과 사이에 의존성이 생깁니다. 분기가 잘 예측되는 코드에서는 오히려 느릴 수 있습니다.

면접에서 이렇게 물어요

면접 질문

1비트 예측기와 2비트 예측기는 무엇이 다른가요?

1비트는 직전 결과만 기억해서 반복문이 끝날 때와 다시 시작할 때 두 번 틀립니다. 2비트 포화 카운터는 반복문이 충분히 길면 계속 도는 동안 강한 상태에 있어서, 끝날 때 한 번 어긋나도 예측을 뒤집지 않으므로 보통 반복문이 끝날 때 한 번만 틀립니다.

면접 질문

BTB는 무엇이고 왜 필요한가요?

분기 명령어 주소별로 분기 목표 주소를 저장해 두는 작은 캐시입니다. 명령어를 해석하기 전에 다음에 가져올 주소를 알아야 파이프라인이 멈추지 않으므로, 방향 예측과 별개로 목표 주소를 미리 알려 주는 장치가 필요합니다.

면접 질문

분기 예측 실패의 비용은 무엇에 비례하나요?

분기 결과가 확정되는 단계까지의 깊이, 즉 파이프라인이 깊을수록 한 번 틀릴 때 버려지는 명령어가 많아집니다. 파이프라인이 깊은 CPU일수록 예측기가 중요합니다.

면접 질문

분기가 많은 코드를 빠르게 만드는 방법에는 무엇이 있나요?

분기 자체를 줄이거나(조건부 이동, 비트 연산), 데이터를 정렬하거나 분류해서 분기 결과에 패턴을 만들거나, 실제 실행 기록을 컴파일러가 분기 확률 등 최적화에 반영하게 하는 프로파일 기반 최적화(PGO)를 씁니다. GCC 문서는 __builtin_expect로 직접 알려 주기보다 실제 프로파일 피드백을 쓰라고 권합니다.

실제 시스템에서는

리눅스 커널의 likely / unlikely — __builtin_expect를 감싼 매크로로, 참일 가능성이 높거나 낮은 조건을 컴파일러에 알려 줍니다.

리눅스 perf stat — -e branches,branch-misses 옵션으로 분기 수와 예측 실패 수를 세어 실패율을 계산할 수 있습니다.

Spectre — 2018년에 공개된 취약점으로, 변종 1은 경계 검사 분기를 일부러 잘못 예측하게 만들어 범위 밖 읽기를 추측 실행시키고 캐시에 남은 흔적으로 값을 알아냅니다.

고성능 CPU의 예측기 — 분기 기록을 함께 보는 방식(gshare, TAGE 계열)이나 퍼셉트론 기반 방식 등이 연구되어 왔고, 제품의 구체적인 구조는 대부분 공개되어 있지 않습니다.

함께 보면 좋은 토픽

파이프라이닝 — 분기 예측이 왜 필요한지, 제어 해저드가 무엇인지 봅니다.

비순차 실행 — 예측 실행과 폐기가 비순차 실행과 어떻게 이어지는지 봅니다.

명령어 사이클 — 분기 명령어가 PC를 바꾸는 과정을 봅니다.

캐시 메모리 — Spectre가 이용하는 캐시의 흔적이 어떻게 생기는지 봅니다.

참고 자료

Spectre 논문(2018 공개, IEEE S&P 2019) — Spectre Attacks: Exploiting Speculative Execution

__builtin_expect — Other Built-in Functions Provided by GCC — GCC Manual

[[likely]] — C++ attribute: likely, unlikely (since C++20) — cppreference

perf stat — perf-stat(1) — Linux manual page

교재 — Hennessy, Patterson, "Computer Architecture: A Quantitative Approach" 5판 3장 "Reducing Branch Costs with Advanced Branch Prediction" 절

2비트 포화 카운터 예측기

// 0,1 = not-taken 예측 / 2,3 = taken 예측
class TwoBitPredictor {
    private int counter = 3; // 3 = Strongly Taken

    boolean predict() {
        return counter >= 2;
    }

    void update(boolean taken) {
        if (taken) counter = Math.min(3, counter + 1);
        else       counter = Math.max(0, counter - 1);
    }
}

카운터가 3에서 한 번 not-taken을 만나도 2가 될 뿐이라 예측은 여전히 taken입니다. 반복문이 끝나는 순간 한 번만 틀리고, 다음 반복문 시작에서는 다시 맞춥니다.

분기 예측이 잘 되는 코드와 안 되는 코드

// 정렬된 데이터: 앞쪽은 전부 false, 뒤쪽은 전부 true → 패턴이 단순해 예측이 잘 맞음
long sum = 0;
for (int x : sortedData) {
    if (x >= 128) sum += x;
}

// 무작위 데이터: 조건이 매번 제멋대로라 예측이 자주 틀림 → 같은 코드인데 더 느림
for (int x : randomData) {
    if (x >= 128) sum += x;
}

똑같은 반복문이어도 데이터를 정렬해 두면 분기 결과가 길게 한 방향으로 이어져 예측이 잘 맞습니다. 무작위 데이터에서는 예측 실패가 잦아 flush가 반복되어 느려질 수 있습니다.

분기를 없애는 방법 — 조건부 이동

// 분기가 있는 형태: 조건마다 예측이 필요
if (x >= 128) sum += x;

// 분기 없는 형태: 조건을 0 또는 1 마스크로 바꿔 계산 (예측할 필요가 없음)
int mask = ~((x - 128) >> 31); // x >= 128 이면 전부 1, 아니면 0
sum += x & mask;

분기가 예측하기 어렵다면 조건부 이동이나 비트 연산으로 분기 자체를 없애는 방법이 있습니다. 컴파일러도 간단한 조건은 cmov 같은 명령으로 바꿔 분기를 제거하기도 합니다.

파이프라인 CPU에서 분기 예측이 필요한 이유는?

분기 결과는 실행 단계쯤에야 알 수 있습니다.

분기 명령의 결과(어느 주소로 갈지)는 실행 단계에서야 확정됩니다. 그때까지 기다리면 파이프라인에 버블이 생기므로, 예측으로 다음 명령어를 미리 가져와 흐름이 끊기지 않게 합니다.

분기 예측이 틀렸을 때 CPU에서 일어나는 일은?

잘못된 길로 미리 가져온 명령어는 쓸 수 없습니다.

예측이 틀리면 잘못 가져와 실행 중이던 명령어들을 파이프라인에서 비우고(flush), 올바른 분기 목적지에서 다시 시작합니다. 이때 낭비되는 사이클이 예측 실패 비용입니다.

2비트 포화 카운터 예측기가 1비트 예측기보다 유리한 점은?

반복문을 여러 번 다시 실행하는 경우를 생각해 보세요.

1비트 예측기는 직전 결과만 기억해 반복문이 끝날 때와 다시 진입할 때 두 번 틀립니다. 2비트 예측기는 두 번 연속 어긋나야 예측을 바꾸므로 반복문 종료 때 한 번만 틀립니다.