55:132/22C:160 HPCA

Spring, 2011

Second Homework Assignment

Due: Thursday, Feb 17, in class

1. For the five-stage MIPS-like pipeline that we have been discussing in class, complete the tables below to characterize all RAW data hazards. For each case, indicate the number of stall cycles required if forwarding paths are not implemented, the number of stall cycles required with forwarding, and the forwarding path. One of the cases is done for you. Also, for each case you should show an example of the hazard using pipeline diagrams like the ones that we have been using extensively in lecture.

Five-stage Pipeline: Distance-one RAW Hazards: Read Instr. immediately follows Write instr.

	Write Instruction
Read Instr	ALU (Rd <-Rs1 op Rs2)	LOAD (Rd <- MEM[d(Rs)])
ALU Rd <-Rs1 op Rs2	Stalls without forwarding = 2 Stalls with forwarding=0 Forwarding path: EX/MEM to EX
LOAD Rd <- MEM[d(Rs)]
STORE MEM[d(Rs)] <- Rd*
STORE MEM[d(Rs)] <- Rd*

* Note that, for STORE instruction, Rd is actually a source operand that supplies the data value to be written to memory.

Five-stage Pipeline: Distance-two RAW Hazards: one intervening instruction between Write and Read instrs.

	Write Instruction
Read Instr	ALU (Rd <-Rs1 op Rs2)	LOAD (Rd <- MEM[d(Rs)])
ALU Rd <-Rs1 op Rs2)
LOAD Rd <- MEM[d(Rs)]
STORE MEM[d(Rs)] <- Rd*
STORE MEM[d(Rs)] <- Rd*

* Note that, for STORE instruction, Rd is actually a source operand that supplies the data value to be written to memory.

2. A program that performs a 6 x6 matrix multiply can be found here. This program is written in the Instruction Set posted earlier on the class web site. The program assumes a two-cycle branch delay and hence two NOPs have been inserted after each branch. Identify all of the RAW hazards in this program. Now, assume that the program will be executed on a pipeline that does not implement either stalls or forwarding-i.e. the compiler must insert NOPs to eliminate all hazard situations. Modify the program by inserting the minimal number of NOPs to eliminate all data hazards. Note that you will need to adjust the branch offsets as a result of inserting the additional NOP instructions.