#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);
}
}
