5. 분기 예측

5. 분기 예측 - 2025/09

파이프라이닝 프로세서 & 분기 예측

 

컴퓨터 프로그램에서 조건식은 매우 자주 등장합니다.

프로세서의 파이프라인에서 이전 명령어의 처리 단계가 어떤 단계이던

상관 없이 다음 명령어를 인출하는 것이 끊김 없이 진행되어야 하는데,

후에 실행될 명령어의 지점을 알기 위해서는 조건식에 대한 연산을

필연적으로 기다려야 하는 상황이 자주 발생할 수 있게 되는 것입니다. (컨트롤 해저드)

 

이런 상황에 대처하기 위해서 사용되는 방식이 분기 예측 (branch prediction) 입니다.

 

목적지가 바로 보이느냐 ? -> 직접 분기 & 간접 분기

직접 분기 (Direct Branch)

프로그램 명령어가 조건 분기 목적지를 직접 가리키는 경우입니다.

즉, 명령어만 보고도 후의 선택지가 명료한 경우를 이야기 합니다.

if / else 같은 경우를 생각해보면, 선택지가 적기 때문에 명령어 수준에서 예측이 가능합니다.

 

간접 분기 (Indirect Branch)

점프 테이블이 있는 경우나 함수 포인터를 사용하는 경우,

그 분기 목적지에 대한 선택지가 여러개 입니다.

이걸 간접 분기 라고 합니다.

 

어떤것을 예측 할 것인가? -> 방향 & 목적지

분기 방향 예측 (Branch Direction Prediction)

분기를 할까 안할까 예측 하는것이 분기 방향 예측입니다.

 

분기 목적지 예측 (Branch Target Prediction)

점프지점이 어딘지 예측 하는것이 분기 목적지 예측 입니다.

여기서 BTB를 이용한 예측이 등장합니다.

BTB(Branch Target Buffer)

이름에서 알 수 있듯,

'어떠한 분기 명령어가 있을때, 이게 지난번에 여기로 점프하더라' 를 저장해두는 캐시 메모리 입니다.

즉, PC(Program Counter) 를 키로 해서 점프 지점을 저장해두는 방식입니다.

int fnc(int x) 
{
    switch(x) 
    {
        case 0: return f0();
        case 1: return f1();
        case 2: return f2();
        default: return fd();
    }
}

x가 0인 상태에서 초기 실행시, BTB 미스 -> f0의 코드가 목적지로 기록됩니다.

다음 실행시 x가 0이면, BTB 히트 이고, 예측에 성공합니다.

이후로 x가 0이면 미스와 동시에 BTB가 갱신됩니다.

위와 같은 방식으로 아주 간단하게 예측을 하는 방식인데,

성공하면 좋은거고, 점프 지점이 다양하면 별 소용이 없습니다.

다중 엔트리 BTB (Multi-Target BTB) & 간접 분기 예측기

다중 엔트리 BTB는 여러개의 엔트리를 가지는 BTB를 구성하고, 선택지를 여러개 제공하는 방식입니다.

그런데 여러개의 선택지 중 어떤것을 우선적으로 고려하느냐?

이때 분기 히스토리와의 조합이 들어 갑니다.

즉, 어떤 명령어를 실행하는데, 이 명령어가 실행되기 전 컨텍스트는 뭐였을까? 를 통해서 성공율을 높이는 방식입니다.

Base* obj = nullptr;
int r = rand () % 4;

switch(r)
{
	case 0: obj = new derived0; break;
	case 1: obj = new derived1; break;
	case 2: obj = new derived2; break;
	case 3: obj = new derived3; break;
}

obj->run();

위 코드를 보면 r의 값은 완전히 예측이 불가능하지만,

switch(r) 에서 미리 분기가 일어났고, 이 직전 히스로리를 통해

연관된 점프 목적지를 기억해 두면, 어디로 분기해야하는지 예측이 가능해지는 것 입니다.