Recently I had implemented a pipeline MIPS with forwarding and hazard detection unit!

Unlike my previous MIPS project, this one is way more robust, however, without the GUI side, but who cares!

For the sake of simulation, this MIPS will only support the following commands:

  • Add    (ADD $1 , $2, $3    ; $1 <= $2+$3 )
  • Sub    (SUB  $1 , $2, $3    ; $1 <= $2-$3 )
  • Load  (LOAD $1 , $2(offset)    ; $1 <= memory[$2+offset] )
  • Store (STORE $1 , $2(offset)    ; memory[$2+offset] <= $1)
  • Nop   (ADD $0 , $0, $0    ; $0 <= $0+$0 )

As you are already familiar with pipeline MIPS, it has 5 stages:

  1. IF – Instruction Fetch
  2. ID – Instruction Decode
  3. EXE – Execute
  4. MEM – Memory
  5. WB – Write Back

In this post I assume you are familiar with them all, so we can start straight with the ribs!

Throughout the running of the simulation i had to keep a watchful eye on these things:

  • PC (Program Counter:
    • holds the address of the current command to be executed).
    • If the current command is a branch, we had an issue, as we might flush the pipe (IF, ID and EXE) stages if the branch is taken, thus we need to know that branch destination.
  • Register File.
    • Always updated in WB stage, but in case of Forwarding, we might use the data even before it actually gets written to the register file.
  • Each stage’s status:
    • What command is executed in each stage of the pipe, and what its PC (to be used to determine branch destinations and for Forwarding data) .
    • The source and destination registers of each command in each pipe.
    • Since each stage does execute a different command, one need a watching eye to avoid hazards!
    • Sometimes, the data cannot be forwarded, thus we need to stall the pipe for one cycle by inserting a NOP between the command in EXE and ID. (See Hazard headline later in the post that explain exactly the deal here.)

According to the rough explanation above, we can build ourselves the following struct:

/*
* - cmd : The processed command in each pipe stage.
* - src1Val : Actual value of src1 (considering forwarding mux, etc.)
* - src2Val : Actual value of src2 (considering forwarding mux, etc.)
* - dstVal : Actual Value of dst register after EXE stage.
* this value either gets written to the regFile (in WB stage)
* or to Data Memory (in MEM stage).
* */
typedef struct pipeStageState{
SIM_cmd cmd;
pc_t PCofCmd; //pc_t is typedef for uint32_t
int32_t src1Val;
int32_t src2Val;
int32_t dstVal;
} PipeState;
/*
* - Data structure of the pipeline stages' state (snapshot of the core).
* - pc : Value of the current program counter (at IF stage).
* - regFile : Array of values of each register in the register file.
* - memoryReadWait: 'true' IFF reading from the memory didn't end
* in one cycle, and should try to read in the next cycle.
* - branchTaken: 'true' iff last branch cmd is taken. 'false' otherwise.
* - stall: 'true' if need to put NOP in between cmd in ID and EXE,
* so in the next cycle, the cmd in ID stays and the NOP proceeds to EXE.
* - branch_dst: the address to assign to PC IFF branchTaken = true.
* */
typedef struct state_t {
int32_t pc;
int32_t regFile[SIM_REGFILE_SIZE];
bool afterReset;
bool memoryReadWait;
bool branchTaken;
bool stall;
int32_t branch_dst;
PipeState pipeStageState[SIM_PIPELINE_DEPTH];
} State;

One last fine detail…

A ‘snapshot’ of the CPU is kept before each new fetch, by declaring a global static array of 5 (depth of the pipeline) which holds information regarding the commands in each stage in the pipe:

static State currentState; /* Global state of the Core. */
static PipeState lastIterationInstructions[SIM_PIPELINE_DEPTH];

That basically granted me a rather flexible way to know the correct command to Forward data from. However, pay close attention when Stalling, you need to update that array accordingly!

Memory

The memory implementation in this program is a class of its own!

Since the usual MIPS simulators implement their memory as a normal file with the data in it, this simulator does it in style too!

It has a fixed size cache that saves the recent accessed data, and when a new data needs to be inserted where no place is empty in the cache, a LRU algorithm evicts a certain line.

This is not important for the user, since there is an API that fetched the data, and the user can’t care less about what is going inside!

The  code in C

The C code witch simulates the MIPS, takes as input 2 arguments:

  1. File with the MIPS assembly instructions.
  2. Integer value indicating the number of cycles we intend to run the program.

Unlike how you might have imagined it to flow, the implementation assumes that data reading from memory might NOT end in one cycle (as explained in the ‘Memory’ section)

The reason for this is due to the cache property of the RAM. Think of the cache as a memory, which stores data that could be accessed relatively fast.

To better understand the above paragraph, if a certain data is not used for a specific period of time, then it gets omitted from the cache/memory (and a frequently used data is loaded instead), hence, the CPU will not be able to fetch that data in one cycle, but rather needs to wait until it gets loaded into the cache again, which might take few cycles.

Also i made use of quite many #defines:

#define RESET_SUCCESS 0
#define RESET_FAIL -1
#define REGISTER_RESET_VALUE 0
#define PC_RESET_VALUE 0
#define IF 0
#define ID 1
#define EXE 2
#define MEM 3
#define WB 4
#define DATA_HAZARD_CORRECTED 0
#define DATA_HAZARD_INIVETABLE -1
#define MEMORY_READ_SUCCESS 0
#define MEMORY_READ_WAIT_STATE -1
#define PC_INCREMENT 4
typedef uint32_t pc_t;

Hazards

There are 2 types of hazards which I will refer to in this simulator, but first, we need to understand how hazards get to exist in the first place.

Say you have the following 2 instruction:

ADD $1 $3 $3 ($1 = 2 * $3)
ADD $3 $1 $1 ($3 = 2 * $1)

The problem stems from the 2nd command: ADD $3 $1 $1, since it depend on the value of $1 which is calculated in the 1st command.
However, this problem is fairly easy to solve using the Forwarding (or Bypassing) mechanism, which basically peeks into the previous cycle’s calculated data, even before it reaches the Write Back stage, and forwards it to the current cycle.

This is how it’s implemented:

/*
 * Detect data hazards which cannot be solved by the forwarding units.
 * such hazards stems from 2 consecutive instructions with true dependency between them.
 * */
static bool detectHazard() {
 SIM_cmd_opcode _opcode = currentState.pipeStageState[EXE].cmd.opcode;
 int _dst_index = currentState.pipeStageState[EXE].cmd.dst;
 int _src1 = currentState.pipeStageState[ID].cmd.src1;
 int _src2 = currentState.pipeStageState[ID].cmd.isSrc2Imm ?
 -1 : currentState.pipeStageState[ID].cmd.src2;
 if(_opcode == CMD_LOAD \&amp;amp;\&amp;amp; (_dst_index == _src1 || _dst_index == _src2)) {
 currentState.stall = true;
 return true;
 }
 return false;
}

The project is made up from 3 source files:

  1. MIPS Core functionality – obviously!
  2. Memory API – Read/Write data and instructions.
  3. Main – loads the instructions and fires up the Core!

Code to be found on GitHub!

Advertisements