Homework Assignment
from
Hennessy & Patterson (5th ed)
Appendix C and Chapter 3

  1. Using the following code fragment:

    Assume that the initial value of R3 is R2 + 396

    Throughout this exercise use the classic MIPS five-stage integer pipeline (see figure C.1) and assume all memory accesses take 1 clock cycle.

    1. Show the timing of this instruction sequence for the MIPS pipeline without any forwarding or bypassing hardware but assume a register read and a register write in the same clock cycle can happen through protocol in the register file, as in figure C.6. Use the pipelining timing chart like in Figure A.5. Assume that the branch is handled by flushing the pipeline.

      If all memory references take 1 cycle, how many cycles does the loop take to execute.

      See attached sheet for the answer to this question as a sample of what I'm looking for.

    2. Show the timing of this instruction sequence for the MIPS pipeline with normal forwarding and bypass hardware. Use the pipelining timing chart like in Figure A.5. Assume that the branch is handled by predicting it as not taken.

      If all memory references take 1 cycle, how many cycles does the loop take to execute.

    3. Assume the MIPS pipeline with a single-cycle branch delay slot and normal forwarding and bypass hardware. Schedule the instructions in the loop including the branch delay slot. You may reorder instructions and modify the the individual instruction operands, but do not undertake other loop transformations that change the number or opcode of the instructions in the loop. Show the pipelining timing chart and compute the number of cycles needed to execute the entire loop.

  2. Imagine we add support for the register-memory ALU operations to the classic five-stage MIPS pipeline. To offset this increase in complexity, all memory addressing will be restricted to register indirect (i.e. all addresses are simply a value held in a register: no offset or displacement may be added to the register value). For example, the register-memory instruction: means to perform the action R4 <- R5 + mem[R1] Register-register operations will remain unchanged. Answer the following for the integer MIPS pipeline.
    1. List a rearranged order of the five traditional stages of the MIPS pipeline that will support register-memory operations implemented exclusively by register indirect address mode.
    2. Describe what new forwarding paths are needed for the rearranged pipeline by stating the source, destination and information transferred on each new forwarding path.
    3. For the reordered stages of the MIPS pipeline, what new data hazards are created by this address mode? Give an instruction sequence to illustrate each new hazard.

  3. Consider the following MIPS assembly code:
    1. Identify each dependence by type; list the two instructions involved; identify which instruction is dependent; and, if there is one, name the storage location involved.
    2. Use the information about the MIPS five-stage pipeline from Appendix A and assume a register read and a register write in the same clock cycle can happen through protocol in the register file, as in figure C.6. Which of the dependencies that you found in part (a) become hazards and which do not? Why?

  4. Suppose we have a deeply pipelined processor, for which we implement a branch-target buffer for the conditional branches only. Assume that the miss-prediction penalty is always 4 cycles and the buffer miss penalty is always 3 cycles. Assume 90% hit rate and 90% accuracy, and branch make up 15% of the instructions executed.
    1. How much faster is the processor with the branch-target buffer verses a processor that has a fixed 2-cycle branch penalty? Assume a base CPI without stalls of 1.
    2. Compare the results of the question (4.a) above with a simple predict-taken branch prediction scheme were the only change is that the miss-rate of the predictor is 38%.
    3. Compare the results of the question (4.a) above with a simple predict-not-taken branch prediction scheme were the only changes are that the miss-rate of the predictor is 62% and the cost of a miss-prediction is only 3 cycles.
April 11, '13