allpredictors.c

This code : implemetation of branch predictors gag gap gshare

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
/* 
	11=ST=3
    10=WT=2
    01=WN=1
    00=SN=0 */

void initialize_pht(int);
int power_two(int);
void Gag();
void Gap();
void Gsel();
void Gshare();
void pred_check();
void update();

int correct_predictions, mispredictions;
int t_or_nt, addr_br_instr, br_target;
int *pht_table;
int predicted_taken, pht_index, masking_value;
int hist_bits;
int bhr,masking_val_addr,pht_table_size;
int addr_instr_extrbits;/* For Gap*/
int s; /*For Gap*/
int gsel_bits,add_brinstr_sbits;/*For Gselect  */
int gshare_addr_bits;/* for Gshare  */
FILE *f1;

int main()
{
  int sel_pred;
 /*Opening file history.txt which contains addresses and whether branch was taken or not */
  f1 = fopen("history.txt", "r");
    if(f1 == NULL)
    {
		printf("FILE NOT OPENED\n");
	}

  printf("\n Enter the predictor ");
  printf("\n 1. Gag \n 2.Gap \n 3. Gsel \n 4. Gshare \n");
  scanf("%d",&sel_pred);
  switch (sel_pred)
  {
  case 1: { Gag(); break ;}
  
  case 2: {Gap(); break;}

  case 3: { Gsel(); break;}

  case 4: { Gshare(); break;}

  default : {printf("Error "); break;} 
  }
    printf("Number of Correct Predictions = %d\n", correct_predictions);
	printf("Number of Mispredictions = %d\n", mispredictions);
	printf("Total Predictions = %d\n", correct_predictions + mispredictions);
	printf("Misprediction Rate = %f\n%", (float) mispredictions * 100.0 / ((float)correct_predictions + (float)mispredictions));
    printf("Total Predictions = %d\n", correct_predictions + mispredictions);
	fclose(f1);
    return 0;
}

void initialize_pht(int num_entries)
{
	int count;
	/* Allocating memory for the PHT entries */
	pht_table = malloc(num_entries * sizeof(int));

	for (count = 0; count < num_entries; count++)
	{
		/* Initializing all counters to 10=WT */
		pht_table[count] = 2;
	}
}

int power_two(int num)
{
	int power_of_two = 1, count;

	for (count = 0; count < num; count++)
	{
		power_of_two *= 2;

	}

	return (power_of_two);
}

void pred_check()
{
	/* Check counter value in the corresponding PHT index */
		if(pht_table[pht_index] >= 2)
		{
			/* Predicted TAKEN if counter value >= 2 */
			predicted_taken = 1;
		}
		else
		{
			/* Predicted NOT TAKEN if counter value < 2 */
			predicted_taken = 0;
		}
}

void update()
{
	/* Check predicted value against actual branch outcome and increment correct_predictions or mispredictions */
		if (predicted_taken == t_or_nt)
		{
			correct_predictions++;
		}
		else
		{
			mispredictions++;
		}
		/* Modify contents of BHR based on actual outcome */
		bhr = (bhr << 1) + t_or_nt;

		/* Mask the new value of BHR so that we retain only hist_bits in BHR */
		bhr= (bhr) & masking_value;

		/* Increment or decrement the corresponding PHT entry depending on branch outcome */
		if (t_or_nt)
		{
			pht_table[pht_index] = pht_table[pht_index] + 1;
		}
		else
		{
			pht_table[pht_index] = pht_table[pht_index] - 1;
		}
		/*saturate counter  the 2 bit counter */
		if (pht_table[pht_index] > 3)
		{
			pht_table[pht_index] = 3;
		}
		else if (pht_table[pht_index] < 0)
		{
			pht_table[pht_index] = 0;
		}
}

void Gag()
{
  printf("\n GAg");
  printf("\n Enter no of History bits ");
  scanf("%d",&hist_bits);
  masking_value = power_two(hist_bits) - 1;
  
  initialize_pht(power_two(hist_bits));
  bhr=0;
    while(fscanf(f1, "%x %x %d", &addr_br_instr, &br_target, &t_or_nt) == 3)
	{
     	pht_index = bhr;
		pred_check();
		update();
	}
}

void Gap()
{
  printf("Gap \n");
  printf("\n Enter no of History bits k ");
  scanf("%d",&hist_bits);
  printf("\n Enter no of tables  s ");
  scanf("%d",&s);
  //printf("\n Enter no of bits from branch addr : ");
  //scanf("%d",&br_addr_bits);


  masking_value = power_two(hist_bits) - 1;
  masking_val_addr=s-1;  
  pht_table_size=s*power_two(hist_bits);
  initialize_pht(pht_table_size);
  bhr=0;
  while(fscanf(f1, "%x %x %d", &addr_br_instr, &br_target, &t_or_nt) == 3)
  {
	  addr_instr_extrbits=(addr_br_instr & masking_val_addr)>>hist_bits;
	  pht_index = addr_instr_extrbits+ bhr;
	  pred_check();
	  update();

  }
}

void Gsel()
{
  printf("\nGsel \n");
  printf("\n enter val of Gselect");
  scanf("%d",&gsel_bits);
  masking_value = power_two(gsel_bits) - 1;
 // masking_val_addr=power_two(s)-1;
  pht_table_size=power_two(gsel_bits*2);
  initialize_pht(pht_table_size);
  bhr=0;
    while(fscanf(f1, "%x %x %d", &addr_br_instr, &br_target, &t_or_nt) == 3)
	{
		add_brinstr_sbits=((addr_br_instr & masking_value)<<gsel_bits);
     	pht_index = add_brinstr_sbits + bhr;
		pred_check();
		update();

	}

}

void Gshare()
{
  printf("Gshare \n");
  printf("\n Enter no of Gsharebits  ");
  scanf("%d",&gshare_addr_bits);
  hist_bits=gshare_addr_bits;
  masking_value = power_two(hist_bits) - 1;
  masking_val_addr=power_two(gshare_addr_bits)-1;
  pht_table_size=power_two(gshare_addr_bits);
  initialize_pht(pht_table_size);
    bhr=0;
    while(fscanf(f1, "%x %x %d", &addr_br_instr, &br_target, &t_or_nt) == 3)
	{
     	pht_index = bhr ^ (addr_br_instr & masking_val_addr);
		/*Gshare is formed by XORing the gshre no of addre bits with gshare bits of BHR */
		pred_check();
		update();
	}
}