Optimization - Branch Prediction (더 많은 분기 예측 유도하기)

reference: 시스템 프로그래밍 수업 / 최종무 교수님

분기 예측(branch prediction)

jge .L3 명령어를 패치하고(IF), 디코딩(DE)하면서 동시에 다른 명령어를 가져올 수 있지만 판단(0보다 크거나 같은지)이 끝나지 전까진 어떤 명령어를 수행해야할 지 알 수 없다. 따라서 stall이 발생한다. control hazard

따라서 CPU가 negl %eax로 뛸 지, .L3로 뛸 지 내부적으로 예측을 한다. branch prediction

위 흐름에서 만약 예측이 옳았다면 13사이클이 소모되고, 예측이 틀렸다면 27사이클이 소모된다. 14사이클이 패널티로써 추가된 것이다.

SW개발자들은 이 분기 예측이 잘 되도록 프로그래밍할 수 있다. 과거의 행위를 보고 분기를 예측하는 CPU 내부 동작 특성을 고려하는 것이다.

예를 들어 아래의 코드 경우

for(i=-1000; i<=1000; i++){
   int x = absval(i);
}

-1000, -999, -998, .. , -3, -2, -1 ..
초반부터 중반까지는 음수만을 판단하므로 negl 명령어로 점프하는 예측을 할 것이고, 이 후 양수가 나올때부터 초반은 예측이 틀리겠지만 다시 양수들만 나오기에 L3 점프하는 예측을 할 것이다.

반면 임의적인 패턴(양수와 음수가 뒤섞인 경우)인 경우 위와 같은 예측이 틀릴 횟수가 훨씬 많아질 것이다.

따라서 프로그래머는 이러한 CPU의 내부 동작을 파악해 분기 예측이 잘 되도록 프로그래밍 할 수 있다.

---

test

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

#define LIMIT 1000
#define ARR_SIZE LIMIT*2+1


int absval(int val){
    return (val < 0) ? -val : val;
}

int main(){
    int i;
    struct timeval stime, etime, gap;

    int reg_arr[ARR_SIZE];
    int rand_arr[ARR_SIZE];

    int idx = 0;
    for(i=-LIMIT; i<=LIMIT; i++){
        // regular pattern        
        reg_arr[idx] = i;

        // random pattern 만들기 
        // 랜덤하게 부호 설정 (+, -)
        if(rand()%2 == 0)   // 부호는 random
            rand_arr[idx] = i;
        else
            rand_arr[idx] = -i;

        idx++;
    }

    printf("branch prediction performanc test [regular pattern] \n");
    gettimeofday(&stime, NULL);
    for(i=0; i<ARR_SIZE; i++){
        absval(reg_arr[i]);
    }
    gettimeofday(&etime, NULL);
    gap.tv_sec = etime.tv_sec - stime.tv_sec; 
    gap.tv_usec = etime.tv_usec - stime.tv_usec;
    if (gap.tv_usec < 0) {
        gap.tv_sec = gap.tv_sec - 1; 
        gap.tv_usec = gap.tv_usec + 1000000;
    }   
    printf("[regular pattern]: Elapsed time %ldsec :%ldusec\n", gap.tv_sec, gap.tv_usec);

    printf("\n\n");

    printf("branch prediction performanc test [random pattern] \n");
    for(i=0; i<ARR_SIZE; i++){
        absval(rand_arr[i]);
    }
    gettimeofday(&etime, NULL);
    gap.tv_sec = etime.tv_sec - stime.tv_sec; 
    gap.tv_usec = etime.tv_usec - stime.tv_usec;
    if (gap.tv_usec < 0) {
        gap.tv_sec = gap.tv_sec - 1; 
        gap.tv_usec = gap.tv_usec + 1000000;
    }   
    printf("[random pattern]: Elapsed time %ldsec :%ldusec\n", gap.tv_sec, gap.tv_usec);


    return 0;
}

생각보다 큰 차이가 남을 확인할 수 있다.
regular pattern에서 분기 예측이 훨씬 더 많이 correct됨을 추정할 수 있다.