부등호가 쏘아 올린 성능 최적화 (2) - 분기 예측

지난 포스팅에서는 명령어를 병렬로 처리하여 처리량을 높이는 명령어 파이프라인(Instruction Pipeline)을 다뤘습니다.

하지만 분기문을 만나면 결과가 확정되기 전엔 다음 명령어를 가져올 수 없어 파이프라인이 멈추는 제어 해저드(Control Hazard)가 발생합니다.”

이 병목을 해결하기 위해, CPU는 결과를 기다리지 않고 미리 실행 경로를 선택하는 분기 예측(Branch Prediction) 기술을 도입했습니다.

Branch Prediction (분기 예측)

인텔 최적화 매뉴얼(Intel Optimization Reference Manual)은 분기 예측을 다음과 같이 정의합니다.

“It enables the processor to begin executing instructions long before the branch outcome is certain.”

분기 결과가 확정되기 훨씬 전부터, 프로세서가 명령어 실행을 시작할 수 있게 해준다.
— Intel 64 and IA-32 Architectures Optimization Reference Manual 中

즉, 분기 예측은 불확실한 미래를 미리 가정하고 실행함으로써 파이프라인의 유휴 상태(Idle)를 방지하는 최적화 기법입니다.

동작 원리 예시

다음과 같은 조건문 코드가 있다고 가정해 봅시다.

if (a > 10) {
   a = a + 1;
}
a = a + 2;

if 문의 연산 결과가 나오기 전까지 CPU는 a = a + 1을 실행해야 할지, 건너뛰어야 할지 알 수 없습니다. 예측 없이 정직하게 기다릴 경우 파이프라인의 흐름은 다음과 같습니다.

구분	T1	T2	T3	T4	T5	T6	T7	T8
a>10	F	D	E	W
a=a+1		☁️	☁️	F	D	E	W
a=a+2					F	D	E	W

• F (Fetch) → D (Decode) → E (Execute) → W (Writeback)
• ☁️ (Stall): 분기 결과 대기로 인한 지연 발생

프로세서는 a > 10의 결과가 나오는 T3 단계까지 다음 명령어를 Fetch 하지 못합니다. 이로 인해 파이프라인에 거품(Bubble, Stall)이 생기며 후속 처리를 담당할 유닛들은 빈 상태(IDLE)로 남게 되어 클럭 사이클을 흘려보내게 됩니다.

🤔 그렇다면, 결과를 기다리지 않고 미리 예측하여 움직인다면 어떻게 될까요?

---

A. 예측 성공

CPU가 if문의 결과를 미리 True로 가정(예측)하고, 지체 없이 다음 명령어를 파이프라인에 밀어 넣은 경우입니다.

구분	T1	T2	T3	T4	T5	T6
분기 (if (a > 10))	F	D	E	W
예측 (a = a + 1)		F	D	E	W
다음 (a = a + 2)			F	D	E	W

분기 연산(T2, T3) 중에도 파이프라인이 멈추지 않고 후속 명령어(a = a + 1)를 처리합니다. 결과적으로 파이프라인이 멈춤 없이 연속적으로 처리되어, 2사이클(Cycle)이 단축되었습니다.

🤔 하지만, 만약 예측이 빗나간다면 어떻게 될까요?

---

B. 예측 실패

예측이 빗나간 경우입니다. CPU는 실행 단계(E)에서 예측 실패를 감지합니다.

구분	T1	T2	T3	T4	T5	T6
분기 (if (a > 10))	F	D	E	W
오답 (a = a + 1)		F	D	Flush	-	-
정답 (a = a + 2)				F	D	E

1. 예측 실패감지:** T3 시점에 조건 불일치를 확인합니다.
2. Flush: 파이프라인에 이미 진입한 잘못된 명령어(a = a + 1)들을 모두 폐기합니다.
3. 재진입: 올바른 경로(a = a + 2)의 명령어를 다시 Fetch 합니다.

Pipeline Flush는 단순한 지연 이상의 비용을 초래합니다. 잘못된 명령어를 비우고 프로세서 상태를 되돌리는(Rollback) 과정에서 Cycle 손실이 발생하기 때문입니다.

그렇다면 프로세스는 도대체 어떻게 분기를 예측하는 걸까요?

---

💡 CPU는 무엇을 근거로 예측할까?

예측 전략은 크게 정적(Static) 방식과 동적(Dynamic) 방식으로 나뉩니다.

1. 정적 분기 예측 (Static Prediction)

실행 이력(History)없이, 코드의 구조적 특징만을 분석하여 정해진 규칙대로 예측하는 방식입니다.

BTFNT (Backwards Taken, Forwards Not Taken)

• Backwards (Taken): 분기가 발생하여 실행 흐름이 현재 실행 중인 코드보다 위쪽 라인으로 이동한다면, for나 while 같은 반복문의 재실행으로 간주하여 실행(Taken)으로 예측합니다.
• Forwards (Not Taken): 반대로 분기가 발생하여 실행 흐름이 현재 실행 중인 코드보다 아래쪽 라인으로 이동한다면, if 문의 블록을 건너뛰는 상황으로 간주하여 실행 안 함(Not Taken)으로 예측합니다.

Unconditional branches

• 조건 없이 이동(return, break)하는 경우, 항상 실행될(Taken) 것으로 예측합니다.

Indirect branches

• 분기 결과를 확정하기 위해 메모리 값을 읽어오는 연산이 필요하다면, 실행되지 않을(Not Taken) 것으로 예측합니다.

2. 동적 분기 예측 (Dynamic Prediction)

프로세서는 이전에 수행했던 분기 명령의 기록을 저장해두고, 이를 다시 참조하여 다음 실행 경로를 예측합니다.

BTB / BHT (Branch Target Buffer / History Table)

• 프로세서는 Branch History Table과 Branch Target Buffer를 사용하여 분기의 방향과 목적지를 예측합니다.
  • Branch Target Buffer (BTB): 분기할 목적지 주소를 저장합니다.
  • Branch History Table (BHT): 분기의 실행 결과(Taken/Not Taken)를 저장합니다.

---

🔄 예측의 흐름: 정적에서 동적으로

그렇다면 CPU는 어떤 상황에서 정적 혹은 동적 방식을 선택할까요? 인텔 공식 문서(Optimization Reference Manual)에서는 그 전환 기준을 BTB(Branch Target Buffer) 기록 여부로 설명하고 있습니다.

“Branches that do not have a history in the BTB are predicted using a static prediction algorithm.”

BTB에 이력이 없는 분기는 정적 예측 알고리즘을 사용하여 예측된다.
— Intel 64 and IA-32 Architectures Optimization Reference Manual 中

결국 CPU는 실행 이력 유무에 따라 예측 전략을 결정합니다.

기록이 없는 초기에는 정적 예측을, 데이터가 쌓인 후에는 이를 기반으로 한 동적 예측을 수행하여 성능을 끌어올립니다.

예측 방식은 다양하지만, 결국 분기 예측의 핵심은 데이터와 흐름 속에서 ‘반복되는 패턴’을 찾아내는 것입니다.

---

지금까지 CPU가 성능을 최적화 하기위해 사용하는 분기 예측 기술에 대해 알아보았습니다.

CPU는 정적 규칙과 동적 이력(BTB)을 통해 끊임없이 다음 경로를 미리 파악하려 합니다. 하지만 이러한 예측 메커니즘도 결국 과거의 실행 흐름과 데이터의 일관성에 의존할 수밖에 없습니다. 결국 분기 예측은 불필요한 연산의 리스크를 감수해야 합니다.

그렇다면 애플리케이션의 성능을 최대한 끌어올리기 위해 우리는 어떤 코드를 작성해야 할까요?

다음 포스팅에서는 간단한 예제를 바탕으로 분기 예측 성능 최적화 전략을 살펴보겠습니다.