Pipeline hazard handling

Question

I0: slli  $s2, $s1, 4
I1: beq   $s1, $zero, top
I2: addi  $s3, $s2, 6
I3: mult  $t2, $s3, $s1
I4: addi  $s4, $s2, 8
I5: sw    $t2, 0($s4)

Consider a pipeline without any hazard handling. The pipeline is the typical 5- stage IF, ID, EX, MEM, WB MIPS design. For the above code, complete the pipeline for the code. Insert the characters IF(instruction fetch), ID(instruction decode), EX(execution), M(memory), WB(write back) for each instruction in the boxes. Do you guys think my chart is correct? Thanks!http://imgur.com/PbJ2egd

Answer 1

This is the correct answer that she gave us from yesterday's review session. Can you point me in the right direction on how to answer this question? How do you know when to delay, put X's, etc? I am sorry I can't give exact details of the answer, but just know this is the correct answer.

Answer 2

First let's plot out which instructions rely on which outputs of preceding instructions:

• I0: Relies on nothing here
• I1: Relies on nothing here, but is a branch
• I2: Relies on I0 ($s2)
• I3: Relies on I2 ($s3)
• I4: Relies on I0 ($s2)
• I5: Relies on I4 ($s4)

So when an instruction relies on another, like I5 on I4, its EX block cannot run until the instruction it is relying on finishes its WB block. In the case of I5, we can see this clearly, since the EX block only starts once I4's WB block is done.

Also note that branches prevent the next instruction from starting at all until its EX block has finishes.

With these two rules we can go instruction by instruction and plot it out:

• I0: Relies on no outputs.
• I1: Relies on no outputs, but note that it is a branch. The next instruction cannot start till EX finishes.
• I2: Relies on I0's output, so wait for I0's WB, but also for I1's EX because I1 was a branch. I1's EX is the worse case, so wait till then. This stalls 2 blocks.
• I3: Relies on I2's output, so wait for I2's WB. This stalls 2 blocks. (We've now stalled 4 total)
• I4: Relies on I0's output, so wait for I0's WB. This stalls 0 blocks, because I0 long since has completed. (We've now stalled 4 total)
• I5: Relies on I4's output, so wait for I4's WB. This stalls 2 blocks. (We've now stalled 6 total)

So in the end we stall 3 times, each for two blocks. This equals the 6 "x"s your teacher drew.