project2.c

computer Achitecture tomasulo simulator

/* Diming Lu   CDA 5155 Computer Architecture
 *
 * Pentium Pro
 * Compiled on a gcc
 *
 *CYCLES:   cycle time to complete program (cycle when halt is in commit)
 *FETCHED:  # of instruction fetched (including instructions squashed because of branch misprediction)
 *RETIRED:  # of instruction committed
 *BRANCHES: # of branches executed (i.e., resolved)
 *MISPRED:  # of branches incorrectly predicted
 *
 */

#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>
#include <stdlib.h>


#define MAXLINELENGTH 1000  /* maximum size of machine language instr */
#define MEMSIZE 10000       /* maximum number of data words in memory */
#define NUMREGS 8	    
#define RBSIZE 5

#define OP_SHIFT 22         //shift right 22 bits for opcode
#define A_SHIFT  19         //shift right 19 bits for regA
#define B_SHIFT  16         //shift right 16 bits for regB

/*
 * Opcodes and function values
 * 
 */

#define ADD 0
#define NAND 1
#define LW 2
#define SW 3
#define BEQ 4
#define MULT 5 
#define HALT 6
#define NOOP 7

#define NOOPINSTRUCTION 0x1c00000


/*
 * Execution unit in reservation station and reorder
 */	
#define LOAD1	0
#define LOAD2	1
#define LOAD3   2

#define STORE1	3
#define STORE2	4
#define STORE3	5

#define MULT1   6
#define MULT2   7
#define MULT3   8

#define NUMUNITS 12             /* number of units in reservation station is 12: 3 LOAD, 3 STORE, 3 ADD, 3 MULT  */

/*
 * Execution times in cycles
 */

#define MULTEXEC        4
#define BRANCHEXEC	1
#define LDEXEC		1
#define STEXEC		1


/*
 * Instruction status values
 */
#define ISSUING		1
#define EXECUTING	2
#define WRITINGRESULT	3
#define COMMITING       4


/* LOAD1, LOAD2, LOAD3, STORE1, STORE2, STORE3, ADD1, ADD2, ADD 3, MULT1, MULT2, MULT3 */

typedef struct _resStation {
  int busy;             /* not busy = 0, busy = 1 */
  int instr;            

  int Vj;		/* Vj, Vk will hold operand values */
  int Vk;
  int Qj;		/* Qj, Qk hold execution unit numbers that */
  int Qk;		/* will produce the result */

  int exTimeLeft;	/* Remaining execution time for instruction */
  int reorderNum;       /* Number of reorder buffer for this instruction. */
}resStation;


typedef struct _reorderEntry {
  int busy;             /* reorder buffer is in use */
  int instr;	        /* instruction being executed */

  int execUnit;	        /* execution unit in Rservation Station that producing result */

  int instrStatus;      /* ISSUING, EXECUTING, WRITINGRESULT */

  int valid;	        /* flat thag indicates that result value is valid */

  int result;	        /* holds speculative result until commit */
  int storeAddress;     /* holds the memory address for a store word */
}reorderEntry;


/* regResult[NUMREGS] in resStation  */
typedef struct _regResultEntry {
  int valid;	        /* 1 if regFile holds correct value, else 0 */
  int unit;            /* reservation station that has the correct value */
  int result;
}regResultEntry;        /* reservation station entry ( add1, mult2, sw1 ) that has the correct value */


typedef struct _machineState{
  int		   pc;
  int              cycles;  /* how many cycles have executed */
  resStation	   reservation[NUMUNITS+1];  //last one unit for halt 
  reorderEntry	   reorderBuf[RBSIZE];
  regResultEntry   regResult[NUMREGS];
  
  int              memory[MEMSIZE];
  int              regFile[NUMREGS];
  int              issue[MEMSIZE];
  int              rs[MEMSIZE];
  int              rega[MEMSIZE];
  int              regb[MEMSIZE];
  int              exe[MEMSIZE];
  int              write[MEMSIZE];
}machineState;


void printInstruction(int instr)
{
    char opcodeString[10];

    if (opcode(instr) == ADD) {
      strcpy(opcodeString, "add");
    }
    else if (opcode(instr) == NAND) {
      strcpy(opcodeString, "nand");
    } 
    else if (opcode(instr) == LW) {
      strcpy(opcodeString, "lw");
    } 
    else if (opcode(instr) == SW) {
      strcpy(opcodeString, "sw");
    } 
    else if (opcode(instr) == BEQ) {
      strcpy(opcodeString, "beq");
    } 
    else if (opcode(instr) == HALT) {
      strcpy(opcodeString,"halt");;
    } 
    else if (opcode(instr) == NOOP) {
      strcpy(opcodeString, "noop");
    } 
    else if (opcode(instr) == MULT) {
      strcpy(opcodeString, "mult");           
    } 

    else {
      strcpy(opcodeString, "data");
    }
	printf("%s %d %d %d\n", opcodeString, field_ra(instr), field_rb(instr), field_imm(instr) );    
}

int opcode(int instruction)
{
  return ( instruction >> OP_SHIFT );
}


void
printState(statePtr, memorySize)
  machineState *statePtr;
  int memorySize;
{
  int i;

  printf("Cycles: %d\n", statePtr->cycles);
  
  int pc = 0;
  while (pc < statePtr->pc){
    printf("\n");
    printInstruction(statePtr->memory[pc]);
    printf("pc =%d", pc);  
    printf("   fetched =%d", pc+1);

    if( pc == 0 )
      printf("   issued=%d",  pc+2);
    else
      printf("   issued =%d", statePtr->issue[pc]);
    
   // unit(0-11):  LOAD1, LOAD2, LOAD3, STORE1, STORE2, STORE3, ADD1, ADD2, ADD3, MULT1, MULT2, MULT3
   
    if( opcode(statePtr->memory[pc]) != NOOP ) {

      if( statePtr->rs[pc] <3 && statePtr->rs[pc] >=0 )
	printf("   rs = LW");
      if( statePtr->rs[pc] <6 && statePtr->rs[pc] >2 )
	printf("   rs = SW");
      if( statePtr->rs[pc] <9 && statePtr->rs[pc] >5 )
	printf("   rs = ALU");
      if( statePtr->rs[pc] <12 && statePtr->rs[pc] >8 )
	printf("   rs = MULT");

    
      if( statePtr->rega[pc] == -1 && statePtr->reservation[statePtr->rs[pc]].Vj != -1) 
	statePtr->rega[pc] = statePtr->cycles;
            
      if( statePtr->regb[pc] == -1 && statePtr->reservation[statePtr->rs[pc]].Vk != -1)
	statePtr->regb[pc] = statePtr->cycles;

      if( pc == 0 ) {
	printf("   regA available= %d", pc+2 );
	printf("   regB available= %d", pc+2 );
      }
      else {
    
      if( statePtr->rega[pc] != -1 )
	printf("   regA available=%d", statePtr->rega[pc]);
      else
	printf("   regA available= No" );
      if( statePtr->regb[pc] != -1)
	printf("   regB available=%d", statePtr->regb[pc]);
      else
	printf("   reB available= No" );
      }


      if( statePtr->reorderBuf[statePtr->reservation[statePtr->rs[pc]].reorderNum].instrStatus == EXECUTING )
	statePtr->exe[pc] = statePtr->cycles;
      
      if( pc == 0)
	printf("   execution=%d", statePtr->exe[pc]-2);

      else if( statePtr->exe[pc] != -1 )
	printf("   execution=%d", statePtr->exe[pc]);
      else
	printf("   execution=No");


      if( statePtr->reorderBuf[statePtr->reservation[statePtr->rs[pc]].reorderNum].instrStatus == WRITINGRESULT)
	statePtr->write[pc] = statePtr->cycles;
      if( pc == 0) {
	printf("   exec finished=%d", statePtr->write[pc]-2);
	printf("   cdb= %d", statePtr->write[pc]-2);
      }
      else if( statePtr->write[pc] != -1 ) {
	printf("   exec finished=%d", statePtr->write[pc]);
	printf("   cdb= %d", statePtr->write[pc]);
      }
      else {
	printf("   execution finish= No");
	printf("   cdb= No");
      }
     


    }
    printf("\n");
    pc = pc + 1;      

  }
  /*  
    
 printf("\t Reorder buffers:\n");
  for (i=0; i<RBSIZE; i++){
    if (statePtr->reorderBuf[i].busy == 1){
      printf("\t \t Reorder buffer %d: ",i);
      printf("instr %d  executionUnit %d  state %d  valid %d  result %d  storeAddr %d\n",
	     statePtr->reorderBuf[i].instr, statePtr->reorderBuf[i].execUnit,
	     statePtr->reorderBuf[i].instrStatus, 
	     statePtr->reorderBuf[i].valid, statePtr->reorderBuf[i].result,
	     statePtr->reorderBuf[i].storeAddress); 
    }
  }

      
  printf("\t Reservation stations:\n");
  for (i=0; i<NUMUNITS; i++){
    if (statePtr->reservation[i].busy == 1){
      printf("\t \t Reservation station %d: ",i);
      printf("Vj = %d ", statePtr->reservation[i].Vj);
      printf("Qj = %d ", statePtr->reservation[i].Qj);    
      printf("Vk = %d ", statePtr->reservation[i].Vk);    
      printf("Qk = %d ", statePtr->reservation[i].Qk);     
      printf(" ExTimeLeft = %d  RBNum = %d\n", 
      statePtr->reservation[i].exTimeLeft,
      statePtr->reservation[i].reorderNum);
      }
    }  
  


  printf("\t Register result status:\n");
  for (i=1; i<NUMREGS; i++){
    if ( statePtr->regResult[i].valid == 1) {
      printf("\t \t Register %d: ",i);
      printf("waiting for reservation number %d\n",
	     statePtr->regResult[i].unit);
    }
  }
  
  */

  printf("\t Memory:\n");
  for (i=0; i<memorySize; i++){
    printf("\t \t memory[%d] = %d\n", i, statePtr->memory[i]);
  }
 
  printf("\t Registers:\n");
  for (i=0; i<NUMREGS; i++){
    printf("\t \t regFile[%d] = %d\n", i, statePtr->regFile[i]);
  }

}
/* end printState(statePtr, memSize) */ 


int field_ra(int instruction)
{
  return ((instruction >> A_SHIFT) & 0X7);
}

int field_rb(int instruction)
{
    return (instruction >> B_SHIFT) & 0X7;
}

int field_imm(int instruction)
{
    return (instruction & 0xFFFF);
}

/* return last 16 bits offsets in lw,sw,beg */
int offset(int instruction)
{
    return field_imm(instruction); /* only used for lw, sw, beq */
}

/* return last 3 bits in AND, NAND */ 
int destReg(int instruction)
{
  return (instruction & 0x07);
}


void
updateRes(reorderNum, statePtr, result)
     int reorderNum;
     machineState *statePtr;
     int result;
{
  /*
   * Add code to update reservation stations:
   * Copy the value "on the common data bus" to
   * any places that might be waiting for it in the 
   * reservation stations.

   *
   * statePtr points to current machine state
   * unit is the reservation station unit number
   * value is the value from regResult entry 
   *
   */