Free Cheeg Solution

Problems in this exercise refer to the following instruction sequences: I1: ADD R1, R2, R1 I2: LW R2, 0(R1) I3: LW R1, 4(R1) I4: OR R3, R1, R2 1) Find all data dependences in this instruction sequence. 2) Find all hazards in this instruction sequence for a 5-stage pipeline with and then without forwarding. 3)To reduce clock cycle time, we are considering a split of the MEM stage into two stages. Find all hazards in this instruction sequence for this 6-stage pipeline with and then without forwarding.

Solution:
Given instruction sequences:
I1: ADD R1, R2, R1
I2: LW R2, 0(R1)
I3: LW R1, 4(R1)
I4: OR R3, R1, R2
(1) In given instruction sequences, the following data dependencies occur:
RAW: Read-After-Write
WAR: Write-After-Read
WAW: Write-After-Write
These data dependencies are given in Table 1 with instruction sequences:

Table 1: Data dependencies

Instruction Sequences	RAW	WAR	WAW
I1: ADD R1, R2, R1 I2: LW R2, 0(R1) I3: LW R1, 4(R1) I4: OR R3, R1, R2	(R1) I1 to I2, I3 (R2) I2 to I4 (R1) I3 to I4	(R2) I1 to I2 (R1) I1, I2 to I3	(R1) I1 to I3

(2) In the given instruction sequences for a 5-stage pipeline, only RAW data dependence can occur data hazards.
With forwarding and without forwarding, only RAW dependence from a load to the very next instruction become data hazards and any RAW dependence from an instruction to one of the
following 3 instructions becomes a hazard respectively.
RAW dependencies with or without data hazards are given in Table 2:

Table 2

Instruction Sequence	With Forwarding	Without Forwarding
I1: ADD R1, R2, R1 I2: LW R2, 0(R1) I3: LW R1, 4(R1) I4: OR R3, R1, R2	(R1) I3 to I4	(R1) I1 to I2, I3 (R2) I2 to I4 (R1) I3 to I4

(3) To reduce clock cycle time, by considering a split of the MEM stage into two stages only RAW dependence from a load to the next two instructions become hazards with forwarding and without forwarding, any RAW dependence from an instruction to one of the following 4 instructions becomes a hazard:

Instruction Sequence	With Forwarding	Without Forwarding
I1: ADD R1, R2, R1 I2: LW R2, 0(R1) I3: LW R1, 4(R1) I4: OR R3, R1, R2	(R2) I2 to I4 (R1) I3 to I4	(R1) I1 to I2, I3 (R2) I2 to I4 (R1) I3 to I4