ECE 445 Computer Organization

Homework #8 Solutions

 PROBLEM SET : 

1. Pipeline Operation (5-stage MIPS pipeline).

Consider the MIPS assembly language code segment given below.

I1:  add $s0, $s1, $s2

I2:  add $s3, $s4, $s5

I3:  add $s6, $s7, $zero

I4:  add $t0, $t1, $t2

I5:  add $t3, $t4, $t5

I6:  add $t6, $t7, $t8

I7:  add $fp, $sp, $zero

(a)  Determine the number of clock cycles needed to execute this code segment on the        pipelined implementation of the MIPS processor (5-stage pipeline).

11 clock cycles.

• Identify the registers that are read during clock cycle #4.

                                Registers Read:          $s7, $zero       I3

• Identify the register that is written during clock cycle #6.

                               Register Written:        $s3                  I2

• Determine the number of clock cycles needed to execute a MIPS assembly language program consisting of 100 instructions on the 5-stage MIPS pipeline.

       Clock cycles  =  5 clock cycles for 1^st Instruction + 1 clock cycle for all other instructions.

Clock cycles   =  5 clock cycles for instruction I1

+  1 clock cycle for all other instructions.

Clock cycles   =  5 * (1) + 1 * (99)  =  5 + 99  =  104 clock cycles.

        (assuming no pipeline stalls).

2. Resource Hazards

Consider the MIPS assembly language code segment given below.

I1:  lw $s0, 0($t0)

I2:  lw $s1, 4($t0)

I3:  add $s2, $zero, $zero

I4:  add $s3, $zero, $zero

I5:  add $s4, $zero, $zero

Assume that the MIPS processor uses a single memory to store both instructions and data, rather than use separate instruction and data memories (as has been discussed).

Assume, also, that data read and write takes precedence over instruction fetch.

• Is there a resource hazard in this implementation of the MIPS processor. Briefly explain.

Yes, there is a resource hazard in this implementation of the MIPS processor.  With a single memory used to store both instructions and data, an instruction cannot be fetched from memory during the same clock cycle that data is either read from (lw) or written to memory (sw).  Consequently, if a load word or store word instruction is in the MEM stage of the pipeline, then the pipeline must be stalled to allow the data to be read from or written to memory and then the next instruction fetched from memory.  With two memories, as in the MIPS processor that we have discussed in class, instructions can be fetched from the instruction memory in the IF stage of the pipeline during the same clock cycle that data is either read from or written to the data memory in the MEM stage of the pipeline.

(continued on next page)

• Determine the number of clock cycles needed to execute this code segment on the modified pipelined implementation of the MIPS processor (5-stage pipeline).

11 clock cycles.

3. Data Hazards

Identify all of the data dependencies in the following code. The book now uses a short form for addressing registers. Instead of writing $s3 and $t1 it just writes $3 and $1 as it is not of importance for this chapter to distinguish registers by their function, e.g. temporary, saved, argument, etc.

I1:  addi $3, $2, 5

I2:  sub  $1, $3, $4

I3:  add  $3, $3, $1

I4:  lw   $2, 0($3)

I5:  sub  $2, $2, $4

I6:  sw   $2, 200($3)

I7:  add  $2, $2, $4

(a)  Show all dependencies in a diagram similar to Figure 4.30 in the textbook on page 280.

4. Forwarding

Consider the pipelined datapath with forwarding in Figure 4.60 on page 316 of the textbook, and the code segment below. The first instruction is fetched (IF) during the first clock cycle. 

I1:  add $3, $4, $1

I2:  add $4, $5, $2

I3:  sub $2, $4, $3

I4:  or $7, $4, $2

I5:  and $8, $2, $3

• At the end of the fifth clock cycle, which registers are being read and which being written?

                                Registers Read:          $4, $2              I4

                               Register Written:        $3                    I1

• What is the forwarding unit doing during the fifth cycle of execution? Mention any comparisons that it makes.

From H/P text (pp. 308 – 310) and Lecture 14 (slide 40):

if (EX/MEM.RegWrite and (EX/MEM.RegisterRd != 0) and (EX/MEM.RegisterRd = ID/EX.RegisterRs)   ForwardA = 10

if (EX/MEM.RegWrite and (EX/MEM.RegisterRd != 0) and (EX/MEM.RegisterRd = ID/EX.RegisterRt)   ForwardB = 10

if (MEM/WB.RegWrite and (MEM/WB.RegisterRd != 0) and (MEM/WB.RegisterRd = ID/EX.RegisterRs)   ForwardA = 01

if (MEM/WB.RegWrite and (MEM/WB.RegisterRd != 0) and (MEM/WB.RegisterRd = ID/EX.RegisterRt)   ForwardB = 01

From pipeline diagram above (on previous page), during clock cycle #5:

EX/MEM.RegisterRd  =  $4  (instruction I2)

ID/EX.RegisterRs  =  $4  (instruction I3) ID/EX.RegisterRt  =  $3  (instruction I3)

MEM/WB.RegisterRd  =  $3  (instruction I1)

ID/EX.RegisterRs  =  $4  (instruction I3)

ID/EX.RegisterRt  =  $3  (instruction I3)

Since, EX/MEM.RegisterRd  =  ID/EX.RegisterRs  =  $4 ForwardA  =  10 (forward $4).

Since, MEM/WB.RegisterRd  =  ID/EX.RegisterRt  =  $3 ForwardB  =  01 (forward $3).

(c)  Explain what the hazard detection unit is doing during the fifth cycle of execution.       Mention any comparisons that it makes.

From H/P text (p. 314) and Lecture 14 (slide 42):

if (ID/EX.MemRead)

and ( (ID/EX.RegisterRt = IF/ID.RegisterRs)       or (ID/EX.RegisterRt = IF/ID.RegisterRt) ) Stall the pipeline.

From pipeline diagram above (on previous page), during clock cycle #5:

                               I4: or $7, $4, $2                   is in the ID stage.

                                I3: sub $2, $4, $3               is in the EX stage.

ID/EX.MemRead = 1 indicates that the instruction in the EX stage is load word.

ID/EX.RegisterRt  =  $3  (instruction I3)

IF/ID.RegisterRs  =  $4  (instruction I4)

IF/ID.RegisterRt  =  $2  (instruction I4) 

Since the instruction in the EX stage is not load word, ID/EX.MemRead = 0.

Consequently, the pipeline is not stalled.