2.1          Introduction

Pipelining is an implementation technique in which multiple instructions are overlapped in execution, much like an assembly line. It is the key to make processors fast. In pipeline architecture a single task is divided in various stages. Pipelining doesn’t help latency of single task, it helps throughput of the entire workload. Here multiple tasks operate simultaneously using different resources. In pipelining the number of stages accounts for the potential speed of the processor.  In this part I have designed a three stage pipeline. This part is further divided into 5 sections. Section 2.2 describes the design of the three stage pipeline. Section 2.3 describes the implementation of the three stage design using HASE simulator. Section 2.4 describes the simulation of the working of the design in the HASE simulator. The subsequent section is used to analyse and conclude on the design.

2.2          Design of the three stage pipeline

This design is a simple three stage pipeline architecture, which implements a basic MIPS32 architecture. Building a three stage pipeline necessitated combining Instruction decode and Instruction Execute stages as well as the Memory Access and Write Back stages. See figure 2.2. The Instruction decode and Execute Unit is used for decoding and also for both data and address arithmetic, so load/store instructions are processed by this Unit before being sent to the Memory Access and Write back Unit and then to Memory.  The Instruction decode and Execute Unit also executes the additions required for integer test and relative branch instructions, so the Memory Access and Write back Unit also executes branches.

The Instruction-decode and Execute Unit receives its operands from the Instruction Decode Unit, which is closely coupled to the Registers. These consist of 32 Integer Registers. The results from both arithmetic/logic and load instructions are returned to the Registers by the Memory Access and Write Back Unit.

Here the MIPS instruction set was used. The instruction sets are in the Appendix A

 2.2.a. 

Data Hazards

Data Hazards occur when an instruction requires the result of a previously issued but as yet uncompleted instruction. Hazards are displayed by a separate Data Hazards entity in the HASE model. See figure 2.2.a

Pipeline Units

 

Instruction Fetch

The Instruction Fetch Unit accesses the Memory for instructions using the address in a Pre-fetch Program Counter (PPC). PPC is initially set equal to 0 (as is the PC register in the Memory Access Unit). Send the content of program count (PC) to memory and fetch the current instruction from memory to update the PC.

Instruction Decode and Execute

The Instruction Decode Unit receives instruction packets from the Instruction Fetch Unit and the result of the arithmetic/logic instruction is computed using native-mode operations of the simulation execution platform. This unit then sends instruction/operand packets to the Memory Access and Write back Unit. Before accessing operands from the Registers, it checks for data hazards. If a hazard is detected, the Unit enters the Held state and the instruction remains in the Instruction Decode Unit until the next clock, when the checks are repeated.

Memory Access and Write back

The Memory Access Unit receives instruction packets from the Instruction decode and execute unit. Each packet contains two data fields in addition to the instruction and status fields. Arithmetic instruction packets contain the data to be sent to the registers in the data1 field. Load instruction packets contain a memory address in the data1 field which is sent to the Memory Unit. The data returned from the Memory is passed to this Unit. Store instruction packets contain a memory address in the data1 field and the data to be sent to Memory in the data2 field. Branch instruction packets contain the new PC address or the offset in the instruction field of the packet. Conditions are evaluated in the relevant Execution Unit and carried through as bits in the Status field of the packet. When the appropriate change has been made to the Program Counter, an untraced packet is sent to the Instruction Fetch Unit to unlock the Held condition in that Unit and to update the Pre-fetch Program Counter. Whenever a valid packet is received, this Unit also constructs a Register Write Request packet and sends it to the Registers. The Registers have three ports, two for reading and one for writing. The Registers unit is not clocked and acts immediately on each packet it receives. To ensure that the simulation works correctly, there is a short delay in the Instruction Decode and Execution unit before it performs the WAW/RAW checks or reads the register values, i.e. a value being written in one clock cycle can also be read in that clock cycle.

Memory and Registers

The Memory

The Memory contains two arrays, one for instructions and one for data. These are held separately because instructions are held in readable (string) form for visualisation purposes whilst data values are held as integers. Each word in both memories contains its own byte address as well as its instruction or data. The Memory receives instruction requests from the Instruction Fetch Unit and Read/Write requests from the Memory Access Unit and, as appropriate, either returns the contents of the requested memory word to the requesting unit or updates it. It checks for invalid addresses, and sets an error flag in the Scoreboard if either occurs.

The Registers

Each word in the Main Registers array contains an index number field, a data field and a ‘Busy Bit’ field. All the data and Busy Bit values are initially set to zero. Main Register 00 is read-only, i.e. writing to it has no effect.

2.3          Implementation in HASE

To implement the above design in HASE simulator, I first created various .gif files using Microsoft Paint tool, to be used in the HASE simulator. Then I have written the EDL file and named it as 3StagePLA.edl.

Entity Definition File

EDL is the entity definition file and it describes the components of the architecture, their ports and parameters, the links between them and the hierarchical structure (in essence the logical structure of the experiment).

The EDL file starts with the PREAMBLE section of the project definition specifies the basic attributes of the project, for example its name, working directory and author.

PROJECT (

PREAMBLE (

               NAME “3StagePLA”

               AUTHOR “Anshuman Biswal”

               VERSION 1

               DESCRIPTION “3 Stage pipeline based on MIPS32 (simplified instruction set)”

)

Then the PARAMLIB section was defined which contains type definitions of parameters used by the project. It contains the definition of the error description word array, instruction structures, instruction set,

— Definition of instruction set

               INSTR (t_mips_instrn_set, [(VOID),

                                                              (LOAD(LB,LBU,LH,LHU,LW,LWL,LWR), RSTRUCT (t_load,  load_field)),

                                                              (STORE(SB,SH,SW,SWL,SWR), RSTRUCT (t_store, store_field)),

                                                              (ALU(ADD,ADDU,SUB,SUBU,AND,OR,XOR,NOR,SLLV,SRLV,SRAV,SLT,SLTU), RSTRUCT (t_alu, alu_field)),

                                                              (ALUI(ADDI,ADDIU,ANDI,ORI,XORI,SLTI,SLTIU,SLL,SRL,SRA), RSTRUCT (t_alui,  alui_field)),

                                                              (LUI, RSTRUCT(t_loadi, loadi_field)),

                                                              (BRNC(BEQ,BNE), RSTRUCT (t_brnc,  brnc_field)),

                                                              (BRNCI(BLEZ,BGTZ,BLTZ,BGEZ), RSTRUCT (t_brnc_i,  brnc_i_field)),

                                                              (J, RSTRING (label,  “-“)),

                                                              (JR, RSTRING (src_reg,  “-“)),

                                                              (NOP),(BREAK)

                                                             ], function);

 

Instruction register/packet, instruction memory array data memory word, data memory array, data memory access packet, links connecting memory, pipeline stages, registers, etc.

— definition of links connecting to memory

 

               LINK(l_mem,[  (MEM_ACCESS_I,RSTRUCT(t_i_mem_access,DP)),

                                    (MEM_ACCESS_D,RSTRUCT(t_d_mem_access,DP)),

                                    (MEM_INSTR,RSTRUCT(t_instrn_reg,DP)),

                                    (MEM_DATA,RSTRUCT(t_exe_rslt,DP))]);

 

 

— definition of links connecting pipeline stages

 

               LINK(l_pipe,[ (INSTRUCTION,RSTRUCT(t_instrn_reg,DP)),

                                    (UNIT_DATA,RSTRUCT(unit_data_struct,DP)),

                                    (WRITE_BACK,RSTRUCT(t_write_back_struct,DP)),

                                    (BRANCH_RESULT,RSTRUCT(t_branch_rslt,DP))]);

)

 

After the PARAMLIB section GLOBALS section is defined and it contains definitions of parameters that are accessible to all of the entities in the project

GLOBALS(

                              RINT(branches_taken, 0);

                              RINT(branches_not_taken, 0);

                              RINT(memory_reads, 0); 

RINT(memory_writes, 0);

                              RINT(instructions_issued, 0);

                              RRANGE (log_max_cycles, 1, 20, 10)

               )

 

The next definition in the EDL file is the ENTITYLIB which enables the user to create a library of entities, the basic components from which architecture can be created. This section is similar to the parameter library in that it creates definitions of entities which are used later in the STRUCTURE section to create the architecture.

          ENTITYLIB (

 

                              ABSTRACT Biclocked sync ( )

                              ENTITY Clock sync ( )

                              ENTITY Clockphase sync ( )

 

               ENTITY registers (

                              DESCRIPTION (“MIPS Registers”)

                              STATES (RF_IDLE, RF_WRITE, RF_READ)

                              PARAMS (

                                             RARRAY ( prog_reg_set, main_reg, 32);

                              )

                              PORTS (

                              PORT(from_instr_decode1,l_reg,DESTINATION);

                              PORT(to_instr_decode1,l_reg,SOURCE);

                              PORT(from_instr_decode2,l_reg,DESTINATION);

                              PORT(to_instr_decode2,l_reg,SOURCE);

                              PORT(from_write_back,l_reg,DESTINATION);

                 )

               );

The next section is the STRUCTURE section of the project definition and it describes which entities from the entity library are to be included in the architecture description and how many of them there are. It also deals with how the entities and connected together.

• architecture_entity – This defines a component (AENTITY) to be included in the architecture.

STRUCTURE(

— List of entity instances in top-level model

              

                              AENTITY memory MEMORY (

                                             DESCRIPTION(“memory”)

                              );

                              AENTITY registers REGISTERS (

                                             DESCRIPTION(

);

                             

                              AENTITY instr_fetch INSTR_FETCH (

                                             DESCRIPTION(“Instruction Fetch”)

                              );

.

.

.

AENTITY Clock CLOCK ( DESCRIPTION (“Clock”));

                              AENTITY Clockphase CPHASE (DESCRIPTION (“Clock display”));

• communication_channel – This defines a link (CLINK) that interconnects AENTITIES in the architecture.

CLINK(instr_fetch.INSTR_FETCH[to_memory]->memory.MEMORY[instr_request],1);

                              CLINK(memory.MEMORY[instr_out]->instr_fetch.INSTR_FETCH[from_memory],1);

                              CLINK(mem_access.MEM_ACCESS[to_memory]->memory.MEMORY[data_request],1);

                              CLINK(memory.MEMORY[data_out]->mem_access.MEM_ACCESS[from_memory],1);

                              CLINK(instr_fetch.INSTR_FETCH[instr_out]->instr_decode.INSTR_DECODE[instr_in],1);

                              CLINK(instr_decode.INSTR_DECODE[to_registers1]->registers.REGISTERS[from_instr_decode1],1);

                              CLINK(registers.REGISTERS[to_instr_decode1]->instr_decode.INSTR_DECODE[from_registers1],1);

                              CLINK(instr_decode.INSTR_DECODE[to_registers2]->registers.REGISTERS[from_instr_decode2],1);

                              CLINK(registers.REGISTERS[to_instr_decode2]->instr_decode.INSTR_DECODE[from_registers2],1);

Entity Layout File

First I have written the .edl file and then I wrote the .elf file to put the various gif files that I have created in respective position of the design and named it as 3StagePLA.elf. This file contains information related to an entity (position, states, ports and parameters) and to a link (link corner positions) when displayed on screen. An Entity Layout File contains a list of lines each of which should have one of the following formats:

• object_id : POSITION (x,y) info1 info2 info3
• object_id : STATES state1_name gif_image1 state2_name gif_image2 …
• object_id : PORT port_name SIDE entity_side POSITION port_position position_string ICON icon_file

“registers”);

• object_id : PARAM param_name MODE mode_name POSITION (param_x,param_y)
• object_id :
• object_id : LINKCORNER src_entity src_port dest_entity dest_port no_of_corners (cx1,cy1) …
• bottomcorner : position (x,y)

Where object_id can be either an entity name (which has been declared in the entity library) or a component name defined as a CHILD of a COMPENTITY or as an AENTITY STRUCTURE.

msrsas : position (10,30)

title_v2 : position (70,620)

 

SCOREBOARD : position (310,455)

SCOREBOARD : PARAM WAW MODE VALUE POSITION (69,42)

SCOREBOARD : PARAM RAW1 MODE VALUE POSITION (69,61)

SCOREBOARD : PARAM RAW2 MODE VALUE POSITION (69,80)

 

PIPE_DISP : position (70,404)

PIPE_DISP : PARAM M_A MODE VALUE POSITION (80,40)

PIPE_DISP : PARAM I_D MODE VALUE POSITION (80,73)

PIPE_DISP : PARAM I_F MODE VALUE POSITION (80,109)

Coding Entity Behaviour

For each entity, an entity.hase file is created containing Hase++ program code that defines its behaviour. It includes a set of library routines to provide for process oriented discrete event simulation and a run time system for multi-threading many entities in parallel and keeping track of simulation time.

Instruction-Fetch Entity Behaviour

I wrote the instruction fetch entity behaviour in instr_fetch.hase file. The hase file starts with a declaration section ($class_decls) containing declarations of entity references, structures, variables and classes.

$class_decls

  sim_entity_id pipe;

  scoreboard * mySB;

  instr_decode * myID;

  mem_access * myMA;

//structures and variables

  t_i_mem_access InstrMemRequest;

  t_instrn_reg IF_Input_Reg, InputPacket, IF_Output;

  t_mips_instrn_set Instruction;

  t_branch_rslt BranchResult;

  bool Hold;

  bool Branch, DelaySlot, Jump;

  bool ClearValid, SetClearValid;

  int ClockPhase;

  pc_struct next_PPC, old_PPC;

  bool PPC_init, SetPPC_init;       // used to ensure that no instruction accesses

                                                            // occur until PPC has been set from PC

  int branch_address;

  int branch_status;

  int MemReqOutstanding;

  int NewSequence; // = 8 if instruction fetch is the start of new sequence

  int old_state;

//classes

  void InitialisePC(pc_struct PC);

  void ClearPipe();                         

and a section for definitions of declared classes is present under $class_defs.

$class_defs

void instr_fetch::InitialisePC(pc_struct PC)

 

               // Invoked by Memory Access during initialisation

               // Updates PPC with new value of PC

{

  strcpy(next_PPC.label, PC.label);

  next_PPC.offset = PC.offset;

  SetPPC_init = true;

}

 

void instr_fetch::ClearPipe()      // invoked by MA at a branch

{

  SetClearValid = true;   // sets ClearValid in ClockPhase 1; ClearValid is

                                             // reset by first instruction of a new sequence

}

The $pre section contains code to be executed before the simulation proper starts, e.g. initialisation of variables (all variables, classes, ) and the setting of pointers to other entities.

$pre 

  pipe = sim.get_entity_id(“PIPE_DISP”);

  m_access = sim.get_entity_id(“MEM_ACCESS”); 

 myID = (instr_decode*)sim.get_entity(sim.get_entity_id(“INSTR_DECODE”));

 myMA = (mem_access*)sim.get_entity(m_access); 

 SetPPC_init = false;

 PPC_init = false;

  sim_entity_id m_access;

 old_PPC.offset = 0;

 MemReqOutstanding = 0;

 Branch = false;

 DelaySlot = false;

 ClearValid = true; // initially set, awaiting initialisation of PPC by MA Unit

 SetClearValid = true;

 NewSequence = 0; // = 8 if instruction fetch is to start of new sequence

 Hold = false;

 IF_Input_Reg.status = 0;

 IF_Output.status = 0;

 IF_Output.instrn.reset();

 my_state = IF_VOID;

 old_state = IF_VOID;

 dump_state();

Since this is a two-phase clocked system, the definition of each clocked entity will include the following: EXTENDS (Bi-clocked), where “Bi-clocked” is an abstract entity which registers the entity to be clocked with the appropriate pre-defined clock entity. This clock sends phase 0 and phase 1 clock signals to the clocked entities and receives “done” signals back from them once they have completed their actions in each phase. The statements $phase0 and $phase1 in the entity’s .hase file act as include statements for the code in the “clocked” entity which interacts with the clock entity. In phase 0 an entity typically tests for the presence of an input packet from another entity, reads an input packet (SIM_CAST (packet_type, InputPacket, ev);) and carries out its internal actions in response. In the case of a processor pipeline unit, for example, this will involve decoding the instruction in some way, using classes in the global functions files. The global function files global_fns.h and global_fns.c are accessible from all entities. In phase 1, entities normally send packets to their successor units ready to be read at the next phase 0 clock signal.

In phase 0 of the hase file the pre program counter (PPC) normal update is done.

strcpy(PPC.label, next_PPC.label);

 PPC.offset = next_PPC.offset;

If there’s an update from the MA (Memory Access) unit then again the PPC update is done. To read the packets from the MA unit sim_waiting() is used. This method computes the number of events (from within the queue of events that are waiting to be processed) that are for the entity containing the sim_waiting statement and that match the predicate requirements. It is normally used in clocked entities to look for packets sent by some other entity in the previous clock period. So here we look for the packets sent by the MA unit

if (sim_waiting(pc_packet) > 0)

               {

                sim_select (pc_packet, ev);

                SIM_CAST( t_branch_rslt, BranchResult, ev);

                branch_address = BranchResult.branch;              // not used yet

                branch_status  = BranchResult.status;

                strcpy(PPC.label, BranchResult.addr.label);

                PPC.offset = BranchResult.addr.offset;

                strcpy(next_PPC.label, PPC.label);

                next_PPC.offset = PPC.offset; // to ensure that PPC remains

                                                                           // = target address if there’s a Hold

                MemReqOutstanding = 0;                          // all further replies will be ignored

                NewSequence = 8;

                Branch = false;

                

               }

 Then check if the Instruction fetch is not held by the branch or external condition.

 if  (!Hold)

Check for reply from memory and copy packet received into input register. Memory access time may be >1 clock. At a pipeline clear, ClearValid flag is set which says all instructions are invalid until one is returned with bit 28 set indicating first of new sequence. This bit is set with first request to memory after a clear and resets ClearValid flag when it returns.

IF_Input_Reg.status = 0;              // initialise to non-valid

               if (sim_waiting(mem_packet) > 0)

                {

                 sim_select(mem_packet, ev);

                 SIM_CAST(t_instrn_reg, InputPacket, ev);

                 IF_Input_Reg.instrn = InputPacket.instrn;

                 IF_Input_Reg.status = InputPacket.status & -3;

                                                            // remove access type bit

                 if ((IF_Input_Reg.status & 9) == 9)        // bits 31 and 28 = 1

                  {ClearValid = false;} 

                 if (!ClearValid)

  {MemReqOutstanding –;} // decrement memory requests outstanding

                } // end of packet from memory 

               if (ClearValid)

                {IF_Input_Reg.status = 0;} 

                 if ( (IF_Input_Reg.status & 1) == 1 )                     // valid instruction

sim_select  method is used when an entity can have received packets on a number of ports since it processed the last one, sim_select is used in conjunction with sim_waiting to select the appropriate packet for a particular action.Here it is used to receive the packets from the memory. To extract the packet SIM_CAST is used. If it is a valid instruction then Decode input registers content to look for branches.

if ( (IF_Input_Reg.status & 1) == 1 )                       // valid instruction

// Decode input register content to look for branches

                  {

                   if (   IF_Input_Reg.instrn.function == t_mips_instrn_set::J

                              || (IF_Input_Reg.instrn.function == t_mips_instrn_set::JR)

                              || IF_Input_Reg.instrn.decode_BRNC()

                              || IF_Input_Reg.instrn.decode_BRNCI()

                              //|| IF_Input_Reg.instrn.decode_BFP()

                              )

Set Branch, this sets Delay Slot in ClockPhase 1 so that the next instruction, in the delay slot, won’t increment PC and then Decode absolute jumps to stop pre-fetching.

{Branch = true;}

if (  IF_Input_Reg.instrn.function == t_mips_instrn_set::J

                               || (IF_Input_Reg.instrn.function == t_mips_instrn_set::JR)

                               || (IF_Input_Reg.instrn.function == t_mips_instrn_set::BREAK) )

                     {Jump = true;}

                   }                                       // end of if valid instruction

if the instruction issued is a valid instruction, and it is not a ‘filler’ instruction (i.e. NOP / VOID), increment the global fn. 

          if( IF_Input_Reg.instrn.function == t_mips_instrn_set::J

                              || IF_Input_Reg.instrn.decode_LOAD()

                              || IF_Input_Reg.instrn.decode_STORE()

                              || IF_Input_Reg.instrn.decode_ALU()

                              || IF_Input_Reg.instrn.decode_ALUI()

                              || IF_Input_Reg.instrn.decode_BRNC()

                              || IF_Input_Reg.instrn.decode_BRNCI()

                              || (IF_Input_Reg.instrn.function == t_mips_instrn_set::JR)

)

                              {instructions_issued++;}

If PPC has been initialised from PC and if there are none or one memory requests outstanding, access memory for next instruction and increment Pre-fetch Program Counter

if ((MemReqOutstanding <= 1)  && PPC_init && (!Jump))

               {

                 InstrMemRequest.status = 2 | NewSequence;

                 strcpy(InstrMemRequest.addr.label, PPC.label);

                 InstrMemRequest.addr.offset = PPC.offset ;

                 send_MEM_ACCESS_I(to_memory, InstrMemRequest);

                 NewSequence = 0;

                 MemReqOutstanding ++;           // increment memory requests outstanding

                 next_PPC.offset = PPC.offset + 1; // was + 4

                 strcpy(next_PPC.label, PPC.label);}}                    // end of if IF not held up

and then set the state.

if ((IF_Input_Reg.status & 1) == 0)

                {my_state = IF_VOID;} 

               if (((IF_Input_Reg.status & 1) == 1) && !Hold)

                {my_state = IF_BUSY;} 

               if (((IF_Input_Reg.status & 1) == 1) && Hold)

                {my_state = IF_HELD;} 

               if (old_state != my_state || old_PPC.offset != PPC.offset) {

                   dump_state(); old_state = my_state; old_PPC.offset = PPC.offset;

               }

After setting the state send the packet to the pipe_disp using sim_schedule method.  This method schedules an event to an entity; it does not cause an entry to be made in the trace file. sim_schedule is normally used in conjunction with SIM_PUT. To assemble the output copy the input register into output packet.

IF_Output.instrn = IF_Input_Reg.instrn;

               IF_Output.status = IF_Input_Reg.status;

In phase 1 of the clock cycle send the outputs to the Instruction-decode and execute stage.

if (!Hold || (ClearValid && !myID->DelaySlot))

                {

                 if (DelaySlot)

                              {IF_Output.status = IF_Output.status | 4;

                               Branch = false;} 

                 if ((IF_Output.status & 1) == 1)

                  {send_INSTRUCTION(instr_out, IF_Output);}

                 else

                  {sim_schedule(instr_out, 0.0, INSTRUCTION,

 SIM_PUT(t_instrn_reg, IF_Output));}

Instruction decode and execute entity behaviour

I wrote the instruction decode and execute entity behaviour in instr_decode.hase file. This file also contains the $class_decls , $class_defs and $pre section.In phase 0 of the clock cycle in the decode and execute phase I deal with the input packets that was sent from the Instruction Fetch stage. Check If IDHold or Hazard is set, then no packet will have been sent to this unit and no packets must be sent to MA units. If ID Hold is set, current instruction must not be processed.

if  ((!Hazard && !Hold && !SecondCycle) || ClearValid)

                {

                 ID_Input_Reg.status = 0;                          // initialise to nonvalid

                if  (sim_waiting(ev, instr_packet) > 0)

                {

                SIM_CAST( t_instrn_reg, InputPacket, ev );

                ID_Input_Reg.status = InputPacket.status;

                ID_Input_Reg.instrn = InputPacket.instrn;

                }

                if ((ID_Input_Reg.status & 5) == 5)

                  {DelaySlot = true;}

At a pipeline clear, ClearValid flag is set which says all instructions must be set invalid until one arrives with bit 28 set indicating first of new sequence. This bit resets ClearValid.

if ((ID_Input_Reg.status & 9) == 9)          // bits 31 and 28 = 1

                  {ClearValid = false;}

 

               }             // end of Hold, etc

               if (ClearValid)

                {ID_Input_Reg.status = 0;}

Send the packet to the pipeline display ,set the state.

sim_hold(1);                                     // to allow write by Write Back unit         

 

                              sim_schedule(pipe, 0.0, INSTRUCTION,

                                             SIM_PUT(t_instrn_reg, ID_Input_Reg));

 

     if ((ID_Input_Reg.status & 1) == 0)

               {my_state = ID_VOID;}

     if (((ID_Input_Reg.status & 1) == 1) && !Hold)

               {my_state = ID_BUSY;}

 

     if (((ID_Input_Reg.status & 1) == 1) && Hold)

               {my_state = ID_HELD;} 

Check for the data hazards and then check for the structural and control hazards to check whether the instructions can be executed or not.

temp_buff1.instrn = ID_Input_Reg.instrn;

               if (Hazard)

                {temp_buff1.status = 0;}

               else

                {temp_buff1.status = ID_Input_Reg.status;}

               Checkhaz = mySB->CheckHazards(temp_buff1); 

Then update the scoreboard display and if valid instruction and hazard, set my_state = Held. And If valid instruction and no hazards, assemble output and assemble the operands

if (((ID_Input_Reg.status & 1) == 1) && (!Hazard) && (!Hold))

                {

// assemble operands

    if (source_regs == 0)

               {

                 ID_Output.data1 = 0;   // set data1 = 0

                 ID_Output.data2 = 0;   // set data2 = 0

                                                            // for instructions which have no reg sources

               }

    if (source_regs >= 1)

               {

               if (src1T == ‘R’)                 {strcpy (read_src1.reg_type, “R”);}

               read_src1.reg_no = src1;

               send_REG_READ(to_registers1, read_src1);

                sim_get_next(ev);                          //wait for reply

 

               if (ev.from_port(from_registers1))

                 {SIM_CAST(t_reg_value, src1_value, ev);

   ID_Output.data1 = src1_value.value;

                  ID_Output.data2 = 0;} // set data2 = 0 for instructions

                                                                           // which only have 1 data value

               }

  if (source_regs == 2)

               {

               if (src2T == ‘R’)                 {strcpy (read_src2.reg_type, “R”);}

               read_src2.reg_no = src2;

               send_REG_READ(to_registers2, read_src2);

               sim_get_next(ev);                           //wait for reply

 // copy src2_value into output packet

               if (ev.from_port(from_registers2))

                 {SIM_CAST(t_reg_value, src2_value, ev);

                  ID_Output.data2 = src2_value.value;}

               }

Copy instruction and status into output register. And if the pipeline is the progress pipeline then move instruction/operand packets through pipeline registers.

Any = 0;

               for ( i= (latency-1); i>=1; i–)

                {

                Pipeline[i].status = Pipeline[i-1].status;

                              if ((Pipeline[i].status & 1) == 1)

                              {Any = 1;}

                Pipeline[i].instrn = Pipeline[i-1].instrn;

                Pipeline[i].data1 = Pipeline[i-1].data1;

                Pipeline[i].data2 = Pipeline[i-1].data2;

                }

If it contains a valid instruction then compute Result and copy into first Pipeline stage output register (Pipeline [0]) and then send the packet to pipeline display

Instruction.status = ID_Output.status;

                              Instruction.instrn = ID_Output.instrn;

                              sim_schedule(pipe, 0.0, INSTRUCTION,

                                             SIM_PUT(t_instrn_reg, Instruction));

                if (my_state != old_state)

                 {dump_state();

                  old_state = my_state;}

In phase 1 of the clock cycle send the packet to the memory access and write back unit using send_UNIT_DATA

if ((Pipeline[latency-1].status & 1) == 1)

                 {send_UNIT_DATA(int_instr_out, Pipeline[latency-1], 0.0, 17, 2 );}

                else

                 {sim_schedule(int_instr_out, 0.0, UNIT_DATA,

                                             SIM_PUT(unit_data_struct, Pipeline[latency-1]));}

Memory Access and Write-back entity behaviour

I wrote the instruction decode and execute entity behaviour in mem_access.hase file. This file also contains the $class_decls , $class_defs and $pre section. Unless Memory Access and write back unit is held up waiting for a reply from Memory,check for valid packet from decode/execution units and then copy valid packet to MA_Input_Reg.

if (!MAHeld)

  {

               MA_Input_Reg.status = 0;           // Initialise MA_Input_Reg valid to 0

               if (sim_waiting(ev, from_int) > 0)

                {

                 SIM_CAST( unit_data_struct, IntOutput, ev );

                  if ((IntOutput.status & 1) == 1)

                              {

                              MA_Input_Reg.status = IntOutput.status;

                              MA_Input_Reg.instrn = IntOutput.instrn;

                              MA_Input_Reg.data1 = IntOutput.data1;

                              MA_Input_Reg.data2 = IntOutput.data2;

                              }

                }

The complete functionality is done as described in section 2.2 under the Pipe line unit subsection (b). If it is Arithmetic instructions then do the write back action. If it is Load instructions then    send Read access to Memory and set waiting flag. If it is Store instructions then send Write access to Memory and set waiting flag and if it is Branch operations then execute. If a control transfer occurs (unconditional jump, or

conditional branch for which the condition is satisfied, with no branch predicted), then the instructions in Instruction Fetch (IF) and Instruction Decode (ID) must be invalidated.  IF and ID set the status of their outgoing instructions to 0 in Clock Phase 1. ID invokes clearHazard() in the Scoreboard to clear any hazards.

if (Update_PPC)

                {

                 myIF->ClearPipe();

                 myID->ClearPipe();

                 //printf(“MEMORY ACCESS: Clearing pipeline\n”);

                }

Now I need to process the reply that i got from the memory unit. If MAHold = 1, look for packet from memory for STORE orders, this is an acknowledgement and for LOAD orders, the packet contains data which must be processed. In clock phase 1 send the output to memory if Forward is set. If the input is valid then construct a packet to send to registers using send_REG_WRITE().

//If Forward = 1, send Output to Write Back Unit

                 if (((MemoryReadAccess == 1) || (MemoryWriteAccess == 1))

           && (MemReqOutstanding == 0))

                  {

                   send_MEM_ACCESS_D(to_memory, MemRequest);

                   MemReqOutstanding = 1;

                  }

                 else

                  {

                   if ((WB_Input_Reg.status & 1) == 1)

                              // if input is valid, construct a packet to send to Registers

                   {

                              WB_Output.data = WB_Input_Reg.data;  

                              if (WB_Input_Reg.instrn.decode_LOAD())

                              {Dest_reg = WB_Input_Reg.instrn.load_field.dest_reg;}

                              else if (WB_Input_Reg.instrn.decode_ALU())

                              {Dest_reg = WB_Input_Reg.instrn.alu_field.dest_reg; }  

                              else if (WB_Input_Reg.instrn.function == t_mips_instrn_set::LUI)

                              {Dest_reg = WB_Input_Reg.instrn.loadi_field.dest_reg;}

 else if (WB_Input_Reg.instrn.decode_ALUI())

                              {Dest_reg = WB_Input_Reg.instrn.alui_field.dest_reg; }

                              destT = Decode_Register(Dest_reg).type;

                              dest  = Decode_Register(Dest_reg).number + IncRegNo;

                              if (destT == ‘R’) {strcpy(WB_Output.reg_type, “R”);}

                              WB_Output.reg_no =  dest;

                              send_REG_WRITE(to_registers, WB_Output);  

                              }            

                 }

 

If Update_PPC is set then send PC value(s) to Instruction Fetch Unit.

if (Update_PPC && ((MA_Input_Reg.status & 1) == 1))

                  {

                   BranchResult.branch = 0;

                   BranchResult.status = 0;

                   send_BRANCH_RESULT(to_instr_fetch, BranchResult);

                   Update_PPC = false;

                  }

2.4          Simulation using the trace files

To do the simulation using the trace file then the contents files should also be defined. The Memory contains two arrays, one for instructions and one for data. These are held separately because instructions are held in readable (string) form for visualisation purposes whilst data values are held as integers. Each word in both memories contains its own byte address as well as its instruction or data. When a project is loaded, HASE looks for files with the same name as each of the arrays declared in the .edl file, but with a .mem extension and loads the contents into the corresponding array, e.g. the contents of  MEMORY.instr_mem.mem are loaded into the instruction memory. Appendix B has the instruction file contents.

And MEMORY.data_mem.mem contains 0 1 2 ….15 .Each number in a new line. The mips_v1.1.params is in Appendix C.

And REGISTERS.main_reg.mem contains 0 0 from 0 to 32 times in a new line as follows.

0 0

0 0

0 0

.

.

.33 times

0 0

After the content files were written, then I built and compiled the project in the HASE simulator

After this step the trace file was generated and was placed in the results folder inside the projects directory with the name 3StagePLA.sim. And trace file was loaded in the HASE simulator as follows

When played the trace file the following were some screen shots of the simulations for the following instructions provided.

ADDI R2 R0 15 which means R2 = R0 + 15 (=15)

ADDI R1 R0 1 which means R1 = R0 + 1 (=1)

loop1 which means Label (loop1) – does not count as an instruction

ADDI R1 R1 1   which means R1 = R1 + 1 (increment R1 by 1)

ADD R3 R1 R0 which means R3 = R1 + R0 (copy R1 to R3)

loop2   which means Label (loop2) – does not count as an instruction

ADD R3 R3 R1   which means R3 = R3 + R1 (increment R3 by R1)

SLT R4 R2 R3 which means R4 = 1 if R2 < R3 else R4 = 0

BNE R4 R0 done which means Branch to done if R4 != R0 (R4 != 0)

SLL R5 R3 2 which means R5 = R3 Left shifted 2 places

J loop2 which means Branch to loop2

SW R0 0(R5) which means Delay slot: Store R0 at memory location R5

Done which means Label (done) – does not count as an instruction

BNE R1 R2 loop1 which means Branch to loop1 if R1 != R2

NOP which means Delay slot: No operation

BREAK which means End the simulation

NOP which means No operation

The three stage pipeline took 1024 clock cycles to complete all the instructions.

 

2.5          Simulation analysis

Data Hazards occur when, an instruction requires the result of a previously issued but as yet uncompleted instruction. Here the data hazards was handled using the Data Hazard window. Here the Data hazards are handled through Use bits. Each register has a Use bit which is set when an instruction that will write to the register is issued and reset when the result is written to the register. In the HASE MIPS model the registers are implemented as C++ struct with two fields: Use bit and value.

In the Register Display Window if Register 5 has its Use bit set and has a value of 16, while all the others are in the reset state. Before accessing a source or destination register, the Instruction Decode Unit invokes a class in the Registers entity which reads the relevant Use bit.

If the Use bit for a Register required as a source operand is set, then there is a RAW hazard, as shown for Register 5 in the Data Hazards Display window.

2.6          Conclusion

In this part I have designed a three stage pipeline based on MIPS instruction set. To simulate the design I have used HASE simulator. The three stages are the Instruction fetch as first stage, Instruction decode and Execute as second stage and Memory Access and Write-back as third stage. I have combined the Instruction Decode and Instruction Execute into one unit and combined the Memory Access and Write back into one third stage. From the  simulation and by seeing the trace file it is understood that the instructions as mentioned in Appendix B to get completely executed ,took 1024 clock cycles. In PART C we will see how much does the 5 stage pipeline architecture takes to completely execute the same set of MIPS Instructions.

Link to Design and Implementation of 5 Stage Pipeline

References

____________________________________________________________________

[1] Hennessy,J. and Patterson,D. (2005) Computer Organization and Design:T H E  H A R D W A R E / S O F T W A R E I N T E R F A C E,3rd edition,Morgan Kaufmann

[2] Hennessy,J. and Patterson,D. (2007) Computer Architecture: A Quantitative Approach, 4th edition, Morgan Kaufmann.

[3] Hesham,E.R. and Mostafa,A.(2005) ADVANCED COMPUTER ARCHITECTURE AND PARALLEL PROCESSING,John Wiley & Sons

[4] Smith,M., Johnson and Horowitz,M.A.(April 1989) “Limits on Multiple Instruction Issue“, Proceedings of the 3rd International Conference on Architectural Support for Programming Languages and Operating Systems.

[5] Princeton wordnet web [Online] Available from http://wordnetweb.princeton.edu/perl/webwn?s=Computer+Architecture&sub=Search+WordNet&o2=&o0=1&o8=1&o1=1&o7=&o5=&o9=&o6=&o3=&o4=&h=

Accesses:31 December 2012

Appendix A MIPS Instruction Sets

____________________________________________________________________

Load/Store Instructions

Instruction	Description	Example	Result
LB	Load Byte	LB R3 1(R0)	Loads Byte from memory location 1
LBU	Load Byte Unsigned	LBU R4 1(R0)	Loads Byte Unsigned from memory location 1
SB	Store Byte	SB R1 1(R0)	Stores Byte in R1 into memory location 1
LH	Load Halfword	LH R4 2(R0)	Loads Halfword from memory location 2 into R4
LHU	Load Halfword Unsigned	LHU R4 2(R0)	Loads Halfword Unsigned from memory location 2 into R4
LUI	Load Upper Immediate	LUI R1 124	Load 124 in the the upper half of regester R1
SH	Store Halfword	SH R5 6(R0)	Stores Halfword from R5 into memory loction 6
LW	Load Word	LW R4 8(R0)	Loads Word from data memory loaction word 8 into R4
SW	Store Word	SW R3 16(R0)	Stores Word in R3 into location 16 in data memory

Arithmetic instructions

Instruction	Description	Example	Result
ADDI	Add Immediate Word	ADDI R1 R2 -4	Store R2 + -4 in R1
ADDIU	Add Immediate Unsigned Word	ADDIU R1 R2 16	Store R2 + 16 in R1
ADD	Add Word	ADD R1 R2 R3	Store R2 + R3 in R1
ADDU	Add Word Unsigned	ADD R1 R2 R3	Store R2 + R3 in R1
SUB	Subtract Word	SUB R1 R2 R3	Store R2 – R3 in R1
SUBU	Subtract Word Unsigned	SUB R1 R2 R3	Store R2 – R3 in R1
SLT	Set on less than	SLT R1 R2 R3	If R2 is less than R3 set R1 to be 1 else set it to 0
SLTI	Set on less than Immediate	SLTI R1 R2 5	If R2 is less than 5 then set R1 to 1 else set it to 0
SLTU	Set on less than Unsigned	SLTU R1 R2 R3	If the unsigned value of R2 is less than the unsigned value R3 set R1 to 1 else set it to 0
SLTIU	Set on less than Immediate Unsigned	SLTIU R1 R2 6	If the R2 is less than 6 (after sign extension)set R1 to 1else set it to 0

Logical Instructions

Instruction	Description	Example	Result
AND	And	AND R1 R2 R3	Stores result of R2 AND R3 into R1
ANDI	And Immediate	ANDI R1 R1 19	Stores the result of R1 AND 19 back into R1
OR	Or	OR R1 R2 R3	Stores result of R2 OR R3 into R1
ORI	Or Immediate	ORI R1 R1 128	Stores the result of R1 OR 128 back into R1
XOR	Exclusive Or	XOR R1 R2 R3	Stores result of R2 XOR R3 into R1
XORI	Exclusive Or Immediate	XORI R1 R1 64	Stores the result of R1 OR 64 back into R1
NOR	Nor	NOR R1 R2 R3	Stores result of R2 NOR R3 into R1
SSL	Shift Word Left Logical	SSL R1 R2 4	Shift R2 4 bits to the left and store in R1
SRL	Shift Word Right Logical	SRL R1 R2 2	Shift R2 2 bits to the right and store in R1
SRA	Shift Word Right Arithmetic	SRA R3 R4 2	Arithmrticaly shift R4 2 bits right and store in R3
SLLV	Shift Word Left Logical Varable	SLLV R1 R2 R3	Shift R2 left by R3 bits and store in R1
SRLV	Shift Word Right Logical Varable	SRLV R1 R2 R3	Shift R2 right by R3 bits and store in R1
SRAV	Shift Word Right Arithmetic Varable	SRAV R1 R2 R3	Shift R2 right arithemeticaly by R3 bits and store in R1

Jump Instructions

Instruction	Description	Example	Result
J	Jump	J 8	Jump to instruction 8
JR	Jump Register	J R1	Jump to the instruction number held in R1

Branch Instructions

Instruction	Description	Example	Result
BEQ	Branch on equal	BEQ R1 R2 4	Branch forward 4 instructions if R1 and R2 are equal
BNE	Branch on not equal	BNE R1 R2 8	Branch forward 8 instructions if R1 and R2 are not equal
BLEZ	Branch on less than or equal to zero	BLEZ R2 -2	Branch back 2 instructions if R2 is less than or equal to zero
BGTZ	Branch on greater than zero	BGTZ R2 -2	Branch back 2 instructions if R2 is greater than zero
BLTZ	Branch on less than zero	BLTZ R2 3	Branch forward 3 instructions if R2 is less than zero
BGEZ	Branch on greater than or equal to zero	BGTZ R2 5	Branch forward 5 instructions if R2 is greater than or equal to zero
BLTZAL	Branch on less than zero and link	BLTZAL R2 3	Branch forward 3 instructions if R2 is less than zero
BGEZAL	Branch on greater than or equal to zero and link	BGTZAL R2 5	Branch forward 5 instructions if R2 is greater than or equal to zero and link

Other Instructions

Instruction	Description	Example	Result
BREAK	Breakpoint	BREAK	Halt
NOP	No Operation	NOP	No operation

                    Appendix B Instructions File (MEMORY.instr_mem.mem)

____________________________________________________________________

ADDI R2 R0 15

ADDI R1 R0 1

loop1:

ADDI R1 R1 1

ADD R3 R1 R0

loop2:

ADD R3 R3 R1

SLT R4 R2 R3

BNE R4 R0 done

SLL R5 R3 2

J loop2

SW R0 0(R5)

done:

BNE R1 R2 loop1

NOP

BREAK

NOP

                    Appendix C Parameter File (mips_v1.1.params)

____________________________________________________________________

0 (branches_taken)

0 (branches_not_taken)

0 (memory_reads)

0 (memory_writes)

0 (instructions_issued)

10 20 1 (log_max_cycles)

CLOCK (clockName)

IDLE (INSTRUCTION)

IDLE (DATA)

2 8 1 (d_accesstime)

1 (i_accesstime)

65536 (I_Mem_Size)

65536 (D_Mem_Size)

128 (NoOfElements)

64 (NoOfElements)

32 (NoOfElements)

CLOCK (clockName)

main (label)

0 (offset)

CLOCK (clockName)

CLOCK (clockName)

main (label)

0 (offset)

— (WAW)

— (RAW1)

— (RAW2)

0 (cycle)

10.0 (period)

-1.0 (period1)

CLOCK (clockName)  0 (cycle)