Pipeline Hazards

3
votes

I am wondering if someone could verify my answer to this question please! I have a midterm next week and the TA has not posted solutions to this question yet:

Consider the following MIPS assembly code and identify all pipeline hazards under the assumption that there are no pipeline optimizations implemented- including forwarding. The first column of numbers are line numbers that you can refer to in your explanation.

1. addi $3, $0, 100
2. addi $4, $0, 0
3. loop: addi $4, $4, 4
4. add $5, $4, $3
5. sw $5, 100($4)
6. addi $1, $1, -1
7. slt $2, $4, $3
8. bne $2, $0, loop
9. jr $31

Reorder the instructions to reduce the number of stalls to a minimum

My answer:

Moving from line 2 to line 3 (from outside loop to inside), there is a hazard because $4 needed on line 3 for addition is dependent on the value set in $4 on line 2.

Line 4 has a hazard because it is dependent on the value set for $4 in line 3.

Line 5 has a hazard because it is dependent on the value set for $4 in line 4.

Line 8 has a hazard because it is dependent on the value set for $2 in line 7.

Reordered instructions:

        addi $4, $0, 0      2
        addi $3, $0, 100    1
loop:   addi $4, $4, 4      3
        addi $1, $1, -1     6
        add  $5, $4, $3     4
        slt  $2, $4, $3     7
        sw   $5, 100($4)    5
        bne  $2, $0, loop   8
        jr   $31        9
2
assemblymipspipeline

2 Answers

0
votes
Data hazards:
(a) Line 3 needs to wait for line 2 to evaluate the value of $4 (in the
first iteration)
(b) Line 4 needs to wait for line 2 to evaluate the value of $4 (every
iteration)
(c) Line 5 needs to wait for line 4 to evaluate the value of $5 (every
iteration)
(d) Line 8 needs to wait for line 7 to evaluate the value of $2

Control hazard
(a) Line 8 will stall while determining if $2 is equal to $0

Moving lines 6 and 7 to between lines 4 and 5 (alternatively moving
line 5 to between line 7 and 8) and swapping the order, i.e. line 7
before line 6, would provide the most savings with stalls, because that
stall occurs on each iteration of the loop. The swap is necessary to
avoid the data hazard with line 8.
0
votes
  1. Line 3 is dependant on Line 2 (for $4)
  2. Line 4 is dependant on Line 3 (for $4)
  3. Line 5 dependant on Line 3 (for $4) and Line 4 (In the WB of add: value will be written to the register file --in the first half of clock cycle. At the same time MEM of sw would be going on, the value would be needed --in the first half of clock cycle. So Hazard condition exists between these two)
  4. Line 8 is dependant on Line 7