Problem Set Number 6
Computer Science 471

Due by 5 PM, Monday Nov. 11, 1996

1. (5 points) (An improved version of Exercise 6.1 from the text.) For each pipeline register in Figure 6.18 on page 434, label each portion of the pipeline register with the name of the value that is loaded into the register. Determine the length of each field in bits. For example, the IF/ID pipeline register contains an instruction field that is 32 bits wide.

2. (5 points) Exercise 6.3 from the text.

3. (5 points) (An improved version of Exercise 6.19 from the text.) Using Figure 4.42 as your foundation, figure out a reasonable pipelined datapath structure for floating-point addition, and integrate the floating-point registers and the data memory into your picture. You will probably want to use 2 or 3 cycles to get through the floating-point adder; don't worry too much about exactly how long different logic functions take.

4. (5 points) A register write followed by a register read (like for example add r1,-,- followed by and -,r1,-) resulted in a pipeline data hazard that could be solved with forwarding. What about a memory write followed by a read of that same memory location? What would be needed to make this code work: 

        sw    r1, 100(r9)
        lw    r2, 100(r9)
Please explain. Why is this different from the case of registers?

5. (10 points) Suppose a load instruction writes a register that a store instruction then wants to copy to memory. That is, suppose this happens: 

        lw    r1, 100(r9)
        sw    r1, 200(r8)
The Elaboration starting on page 465 of the text discusses this. Please show additions to the datapath of Figure 6.50 that would allow code like this to run without stalling. Also, please write a logical equation for the signal that would control the inevitable mux in your design; use the style of the forwarding equations starting on page 455. Finally, rewrite the stall formula on page 464 so that this code sequence won't stall.

6. (5 points) In problem set 4 you looked at a possible new MIPS instruction, addm, that would add a memory location to the contents of a register. Why would this be hard to add to the MIPS pipeline?

7. (20 points) Four cycles for a taken branch is really bad for CPI. Branches are pretty common, and in lots of applications, they are taken a lot of the time--at the ends of loops, for instance. The main design of chapter 6 flushes the pipe on a taken branch. Delayed branches (see pages 417 and 474) are one way to address this issue. In this problem you will redesign the pipe of Figure 6.52 so that branch instructions have a single delay slot, and do no flushing. You'll want to move and/or re-design logic associated with branch instructions from later pipe stages to earlier ones. Here are the pieces of hardware to consider as you do your design:

Your solution to this problem should be a new version of Figure 6.52, in about the same level of detail. Your design should be able to execute the beq instruction with one delay slot; ignore all other branches. Take out the flush stuff, and substitute whatever new control your design needs. Assume that the cycle time of Figure 6.52 is limited by the memories, and that therefore you can put some additional logic in the other stages without affecting the cycle time.

8. (5 points) So here's the thing: the real MIPS architecture has single-cycle delayed branches, but also has more compare-and-branch instructions than just beq. All the conditions are simple ones, like comparing registers for equality and comparing a register with zero. There is no general comparison of two arbitrary registers. (We had a class discussion about this early in the fall, and in problem set 1 you designed hardware to test these various conditions.) In view of what you learned in question 7, please write an explanation for the MIPS branch architecture.

9. (5 points) Did you send in your Chapter 2 questionnaire before break? If you did, write down the time you sent it, and get 5 points. If you didn't, you can still get 2 points on this question by sending it in now (and writing down the time).

10. (1 point) How long did this take you, not counting the reading, and with whom did you work?