branch predictor 구현해보기

Tournament 방식의 branch predictor 구현

-여러 파일 중 cpp파일만 기록

#include "b_predictor.hpp"
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

b_pre::b_pre() {
    int idx_bit = 13;    //global 13b
    int local_bit = 11;   //local 11b
    int pc_bit = 11;         //pc 11b

    pc_entry = pow(2, pc_bit);
    local_entry = pow(2, local_bit);
    num_predictor_entry = pow(2, idx_bit);
    pred_arr_global = new int[num_predictor_entry] {
        1,
    };
    pred_arr_local = new int[local_entry] {
        1,
    };
    history_arr= new int[pc_entry] {
        0,
    };
    select_arr= new int[num_predictor_entry] {
        2,
    };
    ghr = 0;
};

b_pre::~b_pre() {
    if (pred_arr_global != NULL) delete[] pred_arr_global;
    if (pred_arr_local != NULL) delete[] pred_arr_local;
    if (history_arr != NULL) delete[] history_arr;
    if (select_arr != NULL) delete[] select_arr;
}

int b_pre::get_pred(int pc) {
    int gh = ghr % num_predictor_entry;
    int select = select_arr[gh];
    int prediction;
    int pcbit;
    int lh;
    if (select <= 1) {
        pcbit = pc % pc_entry;
        lh = history_arr[pcbit] % local_entry;
        prediction = pred_arr_local[lh];
    }
    else {
        prediction = pred_arr_global[gh];
    }
    if (prediction >= 2) {
        return 1;
    }
    else {
        return 0;
    }   
}

void b_pre::update(int pc, int res) {
    int gh = ghr % num_predictor_entry;
    int select = select_arr[gh];
    int pcbit = pc % pc_entry;
    int lh = history_arr[pcbit] % local_entry;
    int localpred = pred_arr_local[lh];
    int globalpred = pred_arr_global[gh];

    if (globalpred >= 2) {
        globalpred = 1;
    }
    else {
        globalpred = 0;
    }
    if (localpred >= 2) {
        localpred = 1;
    }
    else {
        localpred = 0;
    }

    if (globalpred == res && localpred != res && select_arr[gh] < 3) {
        select_arr[gh]++;
    }
    else if (globalpred != res && localpred == res && select_arr[gh] > 0) {
        select_arr[gh]--;
    }
    if (res == 1) {
        if (pred_arr_global[gh] <  3) {
            pred_arr_global[gh]++;
        }
        if (pred_arr_local[lh] < 3) {
            pred_arr_local[lh]++;
        }
    }
    else {
        if (pred_arr_global[gh] > 0) {
            pred_arr_global[gh]--;
        }
        if (pred_arr_local[lh] > 0) {
            pred_arr_local[lh]--;
        }
    }
    history_arr[pcbit] = ((history_arr[pcbit] << 1) | res) % local_entry;
    ghr = ((ghr << 1) | res) % num_predictor_entry;
    
}

[사용한 array 및 멤버 변수 설명]

• history_arr(Local history table): PC(11b)를 index로 하여 branch의 history를 가지고 있는 array로, history의 길이는 11bit이고 history_arr의 entry 수는 2^11이다. 모든 엔트리는 0으로 초기화했다. (히스토리 크기는 예측을 위해 사용되는 이전 분기 실행 정보를 저장하기 위한 비트 수)
• pred_arr_local(Local prediction): history_arr에 저장된 local history를 index로 하여 2-bit counter를 가지고 있는 array이다. pred_arr_local의 entry 수는 2^11이다. 모든 엔트리는 1로 초기화하여 초기값은 01인 WN이다. 각 history의 패턴에 대한 예측값(counter)을 갖는다.
• pred_arr_global(Global prediction): Global history(13b)인 ghr(13b)을 index로 하여 2-bit counter를 가지고 있는 array이다. pred_arr_global의 entry 수는 2^13이다. 모든 엔트리는 1로 초기화하여 초기값은 01이다.
• select_arr(Choice prediction): ghr을 index로 하여 Local prediction의 counter와 Global prediction의 counter 중 어느 것을 사용하는 것이 좋은지 학습하는 array이다. 모든 엔트리는 2로 초기화하여 10인 2이다.
• ghr 변수는 Global History Register이고, 초기값은 0이다.

[history를 위해 사용한 저장공간]

[구현한 predictor 실행 결과]