Problem #1

Given the following sequence of assembly language instructions:

I1: lw $3, 100($5)

I2: add $6, $3, $2

I3: sub $9, $3, $8

I4: lw $1, 2000($9)

I5: add $5, $4, $3

I6: addi $7, $1, #8

(a) Indicate all data dependencies (RAW, WAR, WAW) that exist between instructions by writing the instruction pairs among which the dependency exist.

(b) Now assume there is a data forwarding circuit in this pipelined processor and data is written in the first half-cycle and read in the second half-cycle, insert nop instructions to eliminate the data hazard in the above program. Show a pipeline execution diagram for the program, where all data forwards are marked with arrows. Moreover, on the data path circuit, identify the data value, inputs and outputs of the data forwarding unit in cycles when data is forwarded.

(c) Now assume there is a data forwarding circuit and hazard detection unit in this pipelined processor and data is written in the first half-cycle and read in the second half-cycle. Show a pipeline execution diagram for the program, where all stalls are marked with "**" and identify the inputs and outputs of the data hazard detection unit in cycles when stalls are inserted.

Problem #2

We assume that the following MIPS code is executed on a pipelined processor with a 5-stage pipeline (IF, ID, EX, MEM, WB), full data forwarding (including from MEM and WB stages to ID stage), hazard detection unit, and branch instruction is executed in ID stage.

Assume that the first half of the clock cycle write-back stage writes to register file and the second half of the clock cycle the decode stage performs a read of source registers. Show a pipeline execution diagram for the program, where all data forwards are marked with arrows and stalls are marked with "**".

I1: lw $4, 8($16)
I2: beq $5, $4, Target I3: add $2, $4, $5

Problem #3

Consider the following code segment executes on a 5-stage MIPS pipeline:

Loop:

lw $3, 0($zero)
lw $1, 0($3)
addi $1, $1, #1
sub $4, $3, $2
sw $1, 0($3)
bne $4, $zero, Loop

Show the pipeline execution diagram of this instruction sequence for the following two cases:

(a) A pipeline without any forwarding or data hazard detection hardware but assume a register read and write in the same cycle, i.e., register write occurs in the first half of the cycle and register read occurs on the second half of the cycle.

Also, assume the outcome of the branch and the branch target address is known and forwarded in the MEM stage. Insert NOPs for the correct execution of the code.

(b) A pipeline with data forwarding and hazard detection hardware. Again, assume the outcome of the branch and the branch target address is known and forwarded in the MEM stage.