This homework is based on Problem 4.57 in the third edition of "Computer Systems, a programmers perspective" by Randal E. Bryant and David R. OHallaron , which is Problem 4.56 in the second edition.

A portion of the problem from the textbook is shown below to make sure you are completing the correct problem...

In our design of PIPE, we generate a stall whenever one instruction performs a load, reading a value from memory into a register, and the next instruction has this register as a source operand. When the source gets used in the execute stage, this stalling is the only way to avoid a hazard. For cases where the second instruction stores the source operand to memory, such as with an rmmovq or pushq instruction, this stalling is not necessary. Consider the following code examples:

1 mrmovq 0(% r c x ) , %rdx #l o a d 1

2 pushq %rdx #s t o r e 1

3 nop

4 popq %rdx #l o a d 2

5 rmmovq %rax , 0(% rdx ) #s t o r e 2

In lines 1 and 2, the mrmovq instruction reads a value from memory into %rdx and the pushq instruction then pushes this value onto the stack. Our design for pipe would stall the pushq instruction to avoid a load/use hazard. Observe however that the value of %rdx is not required by the pushq instruction until it reaches the memory stage...

Questions:

A. Write a logic formula describing the detection condition for a load use hazard similar to the one given below, except that it will not cause a stall in cases where load forwarding can be used.

B. The file pipe-lf.hcl, detailed at the end of this page, contains a modified version of the control logic for PIPE. It contains the definition of a signal e_valA to implement the block labeled Fwd A in Figure 4.70 in 3rd edition (Figure 4.69 in the 2nd edition). It also has the conditions for a load/use hazard in the pipeline control logic set to zero, and so the pipeline control logic will not detect any forms of load/use hazards. Modify the HCL description to implement load forwarding.

Here is a list of all of the places in the hcl file that code needs to be changed:

You need to change the code for F_stall where it states: Set this to the new load/use condition

D_stall where it states: Set this to the new load/use condition

E_bubble where it states: Set this to the new load/use condition

e_valA where it states: LB:

Looking at pipe-full.hcl you can see what the values need to be for the to broad definition of a load/use hazard as a starting point and modify those portions of pipe-full.hcl and put into pipe-lf.hcl to get the load/use hazard to go away for combinations shown at the top of the homework.

#/* $begin pipe-all-hcl */ #################################################################### # HCL Description of Control for Pipelined Y86 Processor # # Copyright (C) Randal E. Bryant, David R. O'Hallaron, 2010 # ####################################################################

## Your task is to implement load-forwarding, where a value ## read from memory can be stored to memory by the immediately ## following instruction without stalling ## This requires modifying the definition of e_valA ## and relaxing the stall conditions. Relevant sections to change ## are shown in comments containing the keyword "LB"

#################################################################### # C Include's. Don't alter these # ####################################################################

quote '#include ' quote '#include "isa.h"' quote '#include "pipeline.h"' quote '#include "stages.h"' quote '#include "sim.h"' quote 'int sim_main(int argc, char *argv[]);' quote 'int main(int argc, char *argv[]){return sim_main(argc,argv);}'

#################################################################### # Declarations. Do not change/remove/delete any of these # ####################################################################

##### Symbolic representation of Y86 Instruction Codes ############# intsig INOP 'I_NOP' intsig IHALT 'I_HALT' intsig IRRMOVL 'I_RRMOVL' intsig IIRMOVL 'I_IRMOVL' intsig IRMMOVL 'I_RMMOVL' intsig IMRMOVL 'I_MRMOVL' intsig IOPL 'I_ALU' intsig IJXX 'I_JMP' intsig ICALL 'I_CALL' intsig IRET 'I_RET' intsig IPUSHL 'I_PUSHL' intsig IPOPL 'I_POPL'

##### Symbolic represenations of Y86 function codes ##### intsig FNONE 'F_NONE' # Default function code

##### Symbolic representation of Y86 Registers referenced ##### intsig RESP 'REG_ESP' # Stack Pointer intsig RNONE 'REG_NONE' # Special value indicating "no register"

##### ALU Functions referenced explicitly ########################## intsig ALUADD 'A_ADD' # ALU should add its arguments

##### Possible instruction status values ##### intsig SBUB 'STAT_BUB' # Bubble in stage intsig SAOK 'STAT_AOK' # Normal execution intsig SADR 'STAT_ADR' # Invalid memory address intsig SINS 'STAT_INS' # Invalid instruction intsig SHLT 'STAT_HLT' # Halt instruction encountered

##### Signals that can be referenced by control logic ##############

##### Pipeline Register F ##########################################

intsig F_predPC 'pc_curr->pc' # Predicted value of PC

##### Intermediate Values in Fetch Stage ###########################

intsig imem_icode 'imem_icode' # icode field from instruction memory intsig imem_ifun 'imem_ifun' # ifun field from instruction memory intsig f_icode 'if_id_next->icode' # (Possibly modified) instruction code intsig f_ifun 'if_id_next->ifun' # Fetched instruction function intsig f_valC 'if_id_next->valc' # Constant data of fetched instruction intsig f_valP 'if_id_next->valp' # Address of following instruction boolsig imem_error 'imem_error' # Error signal from instruction memory boolsig instr_valid 'instr_valid' # Is fetched instruction valid?

##### Pipeline Register D ########################################## intsig D_icode 'if_id_curr->icode' # Instruction code intsig D_rA 'if_id_curr->ra' # rA field from instruction intsig D_rB 'if_id_curr->rb' # rB field from instruction intsig D_valP 'if_id_curr->valp' # Incremented PC

##### Intermediate Values in Decode Stage #########################

intsig d_srcA 'id_ex_next->srca' # srcA from decoded instruction intsig d_srcB 'id_ex_next->srcb' # srcB from decoded instruction intsig d_rvalA 'd_regvala' # valA read from register file intsig d_rvalB 'd_regvalb' # valB read from register file

##### Pipeline Register E ########################################## intsig E_icode 'id_ex_curr->icode' # Instruction code intsig E_ifun 'id_ex_curr->ifun' # Instruction function intsig E_valC 'id_ex_curr->valc' # Constant data intsig E_srcA 'id_ex_curr->srca' # Source A register ID intsig E_valA 'id_ex_curr->vala' # Source A value intsig E_srcB 'id_ex_curr->srcb' # Source B register ID intsig E_valB 'id_ex_curr->valb' # Source B value intsig E_dstE 'id_ex_curr->deste' # Destination E register ID intsig E_dstM 'id_ex_curr->destm' # Destination M register ID

##### Intermediate Values in Execute Stage ######################### intsig e_valE 'ex_mem_next->vale' # valE generated by ALU boolsig e_Cnd 'ex_mem_next->takebranch' # Does condition hold? intsig e_dstE 'ex_mem_next->deste' # dstE (possibly modified to be RNONE)

##### Pipeline Register M ######################### intsig M_stat 'ex_mem_curr->status' # Instruction status intsig M_icode 'ex_mem_curr->icode' # Instruction code intsig M_ifun 'ex_mem_curr->ifun' # Instruction function intsig M_valA 'ex_mem_curr->vala' # Source A value intsig M_dstE 'ex_mem_curr->deste' # Destination E register ID intsig M_valE 'ex_mem_curr->vale' # ALU E value intsig M_dstM 'ex_mem_curr->destm' # Destination M register ID boolsig M_Cnd 'ex_mem_curr->takebranch' # Condition flag boolsig dmem_error 'dmem_error' # Error signal from instruction memory ## LF: Carry srcA up to pipeline register M intsig M_srcA 'ex_mem_curr->srca' # Source A register ID

##### Intermediate Values in Memory Stage ########################## intsig m_valM 'mem_wb_next->valm' # valM generated by memory intsig m_stat 'mem_wb_next->status' # stat (possibly modified to be SADR)

##### Pipeline Register W ########################################## intsig W_stat 'mem_wb_curr->status' # Instruction status intsig W_icode 'mem_wb_curr->icode' # Instruction code intsig W_dstE 'mem_wb_curr->deste' # Destination E register ID intsig W_valE 'mem_wb_curr->vale' # ALU E value intsig W_dstM 'mem_wb_curr->destm' # Destination M register ID intsig W_valM 'mem_wb_curr->valm' # Memory M value

#################################################################### # Control Signal Definitions. # ####################################################################

################ Fetch Stage ###################################

## What address should instruction be fetched at int f_pc = [ # Mispredicted branch. Fetch at incremented PC M_icode == IJXX && !M_Cnd : M_valA; # Completion of RET instruction. W_icode == IRET : W_valM; # Default: Use predicted value of PC 1 : F_predPC; ];

## Determine icode of fetched instruction int f_icode = [ imem_error : INOP; 1: imem_icode; ];

# Determine ifun int f_ifun = [ imem_error : FNONE; 1: imem_ifun; ];

# Is instruction valid? bool instr_valid = f_icode in { INOP, IHALT, IRRMOVL, IIRMOVL, IRMMOVL, IMRMOVL, IOPL, IJXX, ICALL, IRET, IPUSHL, IPOPL };

# Determine status code for fetched instruction int f_stat = [ imem_error: SADR; !instr_valid : SINS; f_icode == IHALT : SHLT; 1 : SAOK; ];

# Does fetched instruction require a regid byte? bool need_regids = f_icode in { IRRMOVL, IOPL, IPUSHL, IPOPL, IIRMOVL, IRMMOVL, IMRMOVL };

# Does fetched instruction require a constant word? bool need_valC = f_icode in { IIRMOVL, IRMMOVL, IMRMOVL, IJXX, ICALL };

# Predict next value of PC int f_predPC = [ f_icode in { IJXX, ICALL } : f_valC; 1 : f_valP; ];

################ Decode Stage ######################################

## What register should be used as the A source? int d_srcA = [ D_icode in { IRRMOVL, IRMMOVL, IOPL, IPUSHL } : D_rA; D_icode in { IPOPL, IRET } : RESP; 1 : RNONE; # Don't need register ];

## What register should be used as the B source? int d_srcB = [ D_icode in { IOPL, IRMMOVL, IMRMOVL } : D_rB; D_icode in { IPUSHL, IPOPL, ICALL, IRET } : RESP; 1 : RNONE; # Don't need register ];

## What register should be used as the E destination? int d_dstE = [ D_icode in { IRRMOVL, IIRMOVL, IOPL} : D_rB; D_icode in { IPUSHL, IPOPL, ICALL, IRET } : RESP; 1 : RNONE; # Don't write any register ];

## What register should be used as the M destination? int d_dstM = [ D_icode in { IMRMOVL, IPOPL } : D_rA; 1 : RNONE; # Don't write any register ];

## What should be the A value? ## Forward into decode stage for valA int d_valA = [ D_icode in { ICALL, IJXX } : D_valP; # Use incremented PC d_srcA == e_dstE : e_valE; # Forward valE from execute d_srcA == M_dstM : m_valM; # Forward valM from memory d_srcA == M_dstE : M_valE; # Forward valE from memory d_srcA == W_dstM : W_valM; # Forward valM from write back d_srcA == W_dstE : W_valE; # Forward valE from write back 1 : d_rvalA; # Use value read from register file ];

int d_valB = [ d_srcB == e_dstE : e_valE; # Forward valE from execute d_srcB == M_dstM : m_valM; # Forward valM from memory d_srcB == M_dstE : M_valE; # Forward valE from memory d_srcB == W_dstM : W_valM; # Forward valM from write back d_srcB == W_dstE : W_valE; # Forward valE from write back 1 : d_rvalB; # Use value read from register file ];

################ Execute Stage #####################################

## Select input A to ALU int aluA = [ E_icode in { IRRMOVL, IOPL } : E_valA; E_icode in { IIRMOVL, IRMMOVL, IMRMOVL } : E_valC; E_icode in { ICALL, IPUSHL } : -4; E_icode in { IRET, IPOPL } : 4; # Other instructions don't need ALU ];

## Select input B to ALU int aluB = [ E_icode in { IRMMOVL, IMRMOVL, IOPL, ICALL, IPUSHL, IRET, IPOPL } : E_valB; E_icode in { IRRMOVL, IIRMOVL } : 0; # Other instructions don't need ALU ];

## Set the ALU function int alufun = [ E_icode == IOPL : E_ifun; 1 : ALUADD; ];

## Should the condition codes be updated? bool set_cc = E_icode == IOPL && # State changes only during normal operation !m_stat in { SADR, SINS, SHLT } && !W_stat in { SADR, SINS, SHLT };

## Generate valA in execute stage ## LB: With load forwarding, want to insert valM ## from memory stage when appropriate ## when M_icode reads from memory and E_icode writes to memory and ## execute stage uses register rA, then we load forward using m_valM int e_valA = [ M_dstM == E_srcA && M_icode in { IMRMOVL, IPOPL } && E_icode in { IRMMOVL, IPUSHL } : m_valM; 1 : E_valA; # Use valA from stage pipe register ];

## Set dstE to RNONE in event of not-taken conditional move int e_dstE = [ E_icode == IRRMOVL && !e_Cnd : RNONE; 1 : E_dstE; ];

################ Memory Stage ######################################

## Select memory address int mem_addr = [ M_icode in { IRMMOVL, IPUSHL, ICALL, IMRMOVL } : M_valE; M_icode in { IPOPL, IRET } : M_valA; # Other instructions don't need address ];

## Set read control signal bool mem_read = M_icode in { IMRMOVL, IPOPL, IRET };

## Set write control signal bool mem_write = M_icode in { IRMMOVL, IPUSHL, ICALL };

#/* $begin pipe-m_stat-hcl */ ## Update the status int m_stat = [ dmem_error : SADR; 1 : M_stat; ]; #/* $end pipe-m_stat-hcl */

## Set E port register ID int w_dstE = W_dstE;

## Set E port value int w_valE = W_valE;

## Set M port register ID int w_dstM = W_dstM;

## Set M port value int w_valM = W_valM;

## Update processor status int Stat = [ W_stat == SBUB : SAOK; 1 : W_stat; ];

################ Pipeline Register Control #########################

# Should I stall or inject a bubble into Pipeline Register F? # At most one of these can be true. bool F_bubble = 0; bool F_stall = # Conditions for a load/use hazard (taken from Fig. 4.64) ## Set this to the new load/use condition 0 || E_icode in { IMRMOVL, IPOPL } && E_dstM in { d_srcA, d_srcB } && !( D_icode in { IRMMOVL, IPUSHL } ) || # Stalling at fetch while ret passes through pipeline IRET in { D_icode, E_icode, M_icode };

# Should I stall or inject a bubble into Pipeline Register D? # At most one of these can be true. bool D_stall = # Conditions for a load/use hazard ## Set this to the new load/use condition 0 || E_icode in { IMRMOVL, IPOPL } && E_dstM in { d_srcA, d_srcB } && !( D_icode in { IRMMOVL, IPUSHL } );

bool D_bubble = # Mispredicted branch (E_icode == IJXX && !e_Cnd) || # Stalling at fetch while ret passes through pipeline # but not condition for a load/use hazard !(E_icode in { IMRMOVL, IPOPL } && E_dstM in { d_srcA, d_srcB }) && IRET in { D_icode, E_icode, M_icode };

# Should I stall or inject a bubble into Pipeline Register E? # At most one of these can be true. bool E_stall = 0; bool E_bubble = # Mispredicted branch (E_icode == IJXX && !e_Cnd) || # Conditions for a load/use hazard ## Set this to the new load/use condition 0 || E_icode in { IMRMOVL, IPOPL } && E_dstM in { d_srcA, d_srcB } && !( D_icode in { IRMMOVL, IPUSHL } );

# Should I stall or inject a bubble into Pipeline Register M? # At most one of these can be true. bool M_stall = 0; # Start injecting bubbles as soon as exception passes through memory stage bool M_bubble = m_stat in { SADR, SINS, SHLT } || W_stat in { SADR, SINS, SHLT };

# Should I stall or inject a bubble into Pipeline Register W? bool W_stall = W_stat in { SADR, SINS, SHLT }; bool W_bubble = 0; #/* $end pipe-all-hcl */

Trigger Condition Processing ret IRETEID icode. Eicode.Micodel Load use hazard Eicode e llMRMOVQ, IPOPQ) && E dstME (d srCA, d srcB) Mispredicted branch. E.icode IIxx && Cnd m stat E (SADR, SINS. SHLTI II W-stat e ISADR, SINS, SHLT Exception Figure 4.64 Detection conditions for pipeline control logic. Four different conditions require altering the pipeline flow by either stalling the pipeline or canceling partially executed instructions. Trigger Condition Processing ret IRETEID icode. Eicode.Micodel Load use hazard Eicode e llMRMOVQ, IPOPQ) && E dstME (d srCA, d srcB) Mispredicted branch. E.icode IIxx && Cnd m stat E (SADR, SINS. SHLTI II W-stat e ISADR, SINS, SHLT Exception Figure 4.64 Detection conditions for pipeline control logic. Four different conditions require altering the pipeline flow by either stalling the pipeline or canceling partially executed instructions