Homework 4

CMSC 411 / Olano, Fall 2015

The MIPS R4000 had an eight-stage pipeline as shown here in abbreviated form:

This organization can be pipelined without structural hazards, as shown in this pipeline timing diagram:

                    Cycle ->
Instruction         0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15
0: add  $1, $2, $3  IF IS RF EX DF DS TC WB
1: add  $4, $5, $6     IF IS RF EX DF DS TC WB
2: add  $7, $8, $9        IF IS RF EX DF DS TC WB
3: add $10,$11,$12           IF IS RF EX DF DS TC WB
4: add $13,$14,$15              IF IS RF EX DF DS TC WB
5: add $16,$17,$18                 IF IS RF EX DF DS TC WB
6: add $19,$20,$21                    IF IS RF EX DF DS TC WB
7: add $22,$23,$24                       IF IS RF EX DF DS TC WB
8: add $25,$26,$27                          IF IS RF EX DF DS TC WB

Pipeline Speedup (10 points)

  1. What is the ideal pipeline speedup for this processor?
  2. What are three assumptions of the ideal pipeline speedup?

Data Hazards (30 points)

For each data hazard that can happen between R-type instructions with this MIPS R4000 organization:

  1. Show a sequence of MIPS instructions that has that that hazard and no others.
  2. Explain what forwarding would be necessary to avoid it (e.g. forward the ALU result from EX/DF to ALU input in EX of instruction 1).
  3. Show the necessary forwarding path(s) for just this hazard on the abbreviated datapath.

Draw a version of the abbreviated datapath with all of the R-type instruction forwarding paths.

Control Hazards (30 points)

Consider this sequence of instructions, implementing y = |x|+1:

if (x<=0)
    x = -x;
y = x + 1;

If x is in register $1 and y in register $2, this could correspond to the following assembly code:

        bgtz $1, endif
        sub $1, $0, $1
endif:  addi $2, $1, #1

Assume the branch target can only be resolved at the end of the EX stage, and the processor always predicts not taken (no delayed branch, branch target buffer, or other branch prediction).

  1. Show a pipeline timing diagram for the MIPS R4000 when $1 is 5.
  2. Show a second pipeline timing diagram for when $1 is -5
  3. What is the branch penalty?
  4. If 20% of the instructions in a program are branches, and 40% of the branches are taken, what is the expected average CPI?

Structural Hazards (30 points)

Assume we have a multiply operation that takes five cycles in the execute stage.

  1. Write assembly code for a*x+b, where x is in $1, a is in $2, b is in $3, and the result should end up back in $1.
  2. Show a pipeline timing diagram for your code, assuming forwarding.
  3. Where are the stalls due to structural hazards?
  4. Where is does the forwarding take place (Which cycle? Between which stages?)

Submitting

Submit on paper or electronically (by pushing to your assn4 directory in your git repository) by the beginning of class on the due date. You do not need to submit the readme.txt for this assignment, even if you submit electronically.