CSE 141 Homework # 4

Due June 5.
Please see class homepage concerning late assignments and academic dishonesty policies.

Figure 6.24 on page 391 of the text shows a pipelined MIPS implementation. It has four tall skinny boxes, labelled IF/ID, ID/EX, EX/MEM and MEM/WB, representing the pipeline registers that separate the 5 pipeline stages. For each of the four pipeline registers, tell how many bits the register hold, and what those bits represent.
Example (and the correct answer for the first pipeline register) - the IF/ID pipeline register has:
32 bits for the incremented PC
32 bits for the instruction
64 bits total.
For the remaining three pipeline registers, be sure to include the control signals (shown in red in the figure).
Consider this MIPS code sequence:
```
      sll  $2, $2, 2      # multiply $2 by 4 
      sub  $5, $5, $5     # initialize Sum = 0
loop: lw   $8, 1000($2)   # load A(i)
      add  $5, $5, $8     # add it to Sum
      addi $2, $2, -4     # decrement i	
      bne  $2, $0, loop   # are we done?
      sw   $5, 500($0)    # if so, store Sum
```
- (a) Consider a pipelined MIPS processor that does no forwarding but instead has a data hazzard detection unit that introduces the stalls needed to avoid data hazards. Suppose the processor uses the "Assume Branch Not Taken" method (described on pg 425) of dealing with branches. Suppose that before the program starts, register $2 contained the value 1, so that the final bne falls through to the next instruction. Draw a diagram that shows when and where stall cycles are introduced. The diagram should start with the sll instruction and end with the sw. The diagram should look something like Figures 6.32, 6.33 and 6.51 in the text, but you can use IF, ID, EX, Mem, and WB instead of the little pipeline stage icons, and use "-" instead of the bubble icon.
- (b) Now suppose register $2 contained a large value, so the branch back to loop is taken. Draw the diagram showing the stalls that are introduced each time around the loop, starting with the execution of a bne instruction (at the end of the loop) and ending with the next execution of the bne).
- (c) Show how to change the order of instructions so that the program still computes the same answer, but has fewer stall cycles. How many stall cycles are now needed each time around the loop?
- (d) Now assume that the processor had a forwarding unit as described in Chapter 6. Redraw the new answer to part (a)? (Use the original program, not your modified code of part (c).)