Branch Prediction Algorithm

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/******************************************************************************
Branch Prediction Simulator
(c) M. Lutfi, 2009
 ******************************************************************************/
#define ROW_MAJOR_ADDR(A, r, c, n)  ((A) + (r)*(n) + (c))
typedef enum {
    not_taken = 0,
    taken
} branch_t;

typedef enum {
    strongly_not_taken  = 0,
    weakly_not_taken,
    weakly_taken,
    strongly_taken
} branch_state_t;

typedef struct {
    unsigned int    correctPredictionCount;
    branch_state_t  state;
    unsigned int    n_iter;
} lbp_t;

enum {
    BRANCH_A = 0,
    BRANCH_B,
    BRANCH_C,
    BRANCH_D,
    N_OF_BRANCHES
};

#define NBITS_OF_GBH    3    // number of bits in Global History register

lbp_t lbp_table[NBITS_OF_GBH][N_OF_BRANCHES];


unsigned char    gbh=0;  // global branch history register (3-bit only)
branch_t    last_outcome = not_taken;


char* get_branch_state_str(branch_t b)
{
    if (b == not_taken)
    return "not_taken";
    else
    return "taken";
}

void update_gbh(void)
{
#if 0
    gbh = (gbh<<1) | last_outcome;
    gbh &= ((1<    printf("last_outcome = %s\n", get_branch_state_str(last_outcome));
    printf("gbh = %0X\n", gbh);
#endif
}

/* Local Branch Prediction FSM */
void lbp_update(lbp_t *lbp, branch_t outcome)
{
   switch (lbp->state) {
    case strongly_not_taken:
        if (outcome == taken) {
        lbp->state = weakly_not_taken;
        } else {
        lbp->correctPredictionCount++;
        }
        break;
    case weakly_not_taken:
        if (outcome == taken) {
        lbp->state = weakly_taken;
        } else {
        lbp->state = strongly_not_taken;
        }
        break;
    case weakly_taken:
        if (outcome == taken) {
        lbp->state = strongly_taken;
        } else
        lbp->state = weakly_not_taken;
        break;
    case strongly_taken:
        if (outcome == taken) {
        lbp->correctPredictionCount++;
        } else {
        // the outcome is NT
        lbp->state = weakly_taken;
        }
        break;
    }
    lbp->n_iter++;
}


int fun(double *p, int n)
{
    int r = 0;
    int c = 0;
    double *pA;

    while (r <= n-1) {
    last_outcome = not_taken;
    update_gbh();
    lbp_update(&lbp_table[gbh][BRANCH_A], not_taken);
    while (c <= n-1) {
        last_outcome = not_taken;
        update_gbh();
        pA = ROW_MAJOR_ADDR(p, r, c, n);
        if (r < c) {
        lbp_update(&lbp_table[gbh][BRANCH_C], not_taken);
            *pA = 2* (*pA) + 1;
        last_outcome = not_taken;
        } else {
        lbp_update(&lbp_table[gbh][BRANCH_C], taken); 
        last_outcome = taken;
        }

        if (r > c) {
        lbp_update(&lbp_table[gbh][BRANCH_D], not_taken);
        *pA = 2* (*pA) - 1;
        last_outcome = not_taken;
        } else {
        lbp_update(&lbp_table[gbh][BRANCH_D], taken);
        last_outcome = taken;
        }
        ++c;
    }
    lbp_update(&lbp_table[gbh][BRANCH_B], taken);
    last_outcome = taken;
    update_gbh();
    ++r;
    }
    lbp_update(&lbp_table[gbh][BRANCH_A], taken);
    last_outcome = taken;
    update_gbh();
    return 0;
}

void print_A(double *p, int n)
{
    int i,j;
    double *pA;
   
    for (i=0; i<n; i++) {
    for(j=0; j<n; j++) {
        pA = ROW_MAJOR_ADDR(p, i, j, n);
        if (!pA) return;
        printf("%d: &A[%d][%d] = %0X,\t", __LINE__, i, j, pA);
        printf("%d: A[%d][%d] = %lf\n", __LINE__, i, j, *pA);
    }
    }
}

void init_gbh(void)
{
    int i,j;
    lbp_t *lbpP;
   
    gbh = 0;
    for(i=0; i<(NBITS_OF_GBH<<3); i++) {
    lbpP = (lbp_t*)&lbp_table[i];
    for(j=0; j<N_OF_BRANCHES; j++) {
        lbpP[j].correctPredictionCount = 0;
        lbpP[j].state = weakly_not_taken;
        lbpP[j].n_iter = 0;
    }
    }
}

int main(void)
{
    #define N 50
    double A[N][N];
    int i,j;

    init_gbh();  
    printf("sizeof(double) = %d\n", sizeof(double));
    printf("%d: &A = %0X\n", __LINE__, &A[0][0]);
    for(i=0; i<N; i++) {
    for(j=0; j<N; j++) {
        A[i][j] = ROW_MAJOR_ADDR(1, i, j, N);
    }
    }
    fun(&A[0][0], N);
    printf("gbh = %0X\n", gbh);
    for(i=0; i<N_OF_BRANCHES; i++) {
    printf("lbp[%d] iteration = %d\n", i, lbp_table[gbh][i].n_iter);
    printf("lbp[%d] correct prediction count = %d\n",
        i, lbp_table[gbh][i].correctPredictionCount);
    printf("Correct Prediction Rate = %4.2lf%\n\n",
      ((double)(lbp_table[gbh][i].correctPredictionCount)/(double)lbp_table[gbh][i].n_iter) *100.0);
    }
}