Tutorial 9
CSE 112 Computer Organization
Q1. Consider a 5-stage pipelined processor following the RISC-V ISA with stages Fetch (F),
Decode (D), Execute (E), Memory (M), and Writeback (W).
Answer the following:
1. Explain why data hazards cannot be identified from a single instruction alone.
2. Give examples of instruction sequences that produce data hazards:
a) when the processor has no data forwarding.
b) when the processor has full forwarding.
Ans 1. A data hazard does not come from one instruction by itself. It occurs only when:
● one instruction produces a value, and
● a later instruction uses that same value before it is safely available.
So data hazards depend on the relationship between two or more instructions, not on a single
isolated instruction.
For example:
ADD x2, x1, x0
ADD x3, x2, x1
Here the second instruction uses x2, which is produced by the first instruction. That
dependency can create a data hazard.
2(a). When forwarding is not available, dependent instructions must wait until the result is
written back to the register file.
Examples:
ADD x2, x1, x0
ADD x3, x2, x1
Here:
● ADD x2, x1, x0 writes to x2
● ADD x3, x2, x1 reads x2
So the second instruction depends on the first one. This creates a RAW (Read After Write) data
hazard.
2(b). When full forwarding is available, most ALU-to-ALU dependencies can be handled without
stalls. But a load-use hazard can still occur.
Example:
LW x2, 8(x0)
ADD x3, x2, x1
Here:
● LW x2, 8(x0) loads data into x2
● the next instruction immediately uses x2
Even with full forwarding, the data loaded by LW becomes available only after the memory
stage, so the next instruction may still need a stall. This is called a load-use data hazard.
Q2. Consider the following instruction sequence executed on a 5-stage pipelined RISC-V
processor:
I1: add s8, s4, s5
I2: sub s2, s8, s3
I3: or s9, t6, s8
I4: and s7, s8, t2
Answer the following:
a) Identify the hazard in the above instruction sequence.
b) Specify the type of dependency involved.
c) Draw the pipeline timing diagram without any hazard handling.
d) Insert the required NOPs to remove the hazard.
e) Draw the corrected pipeline timing diagram after inserting NOPs.
f) How many extra cycles are added because of the hazard?
Ans 2:
a) The given instruction sequence has a data hazard. Instruction I1 writes the value of
register s8, and the following instructions I2, I3, and I4 use s8 as a source operand. Since
these instructions try to read s8 before the value is safely written back to the register
file, a hazard occurs.
b) The dependency is RAW (Read After Write).
● I1: add s8, s4, s5 writes to s8
● I2: sub s2, s8, s3 reads s8
● I3: or s9, t6, s8 reads s8
● I4: and s7, s8, t2 reads s8
c) Pipeline timing diagram without hazard handling:
Cycles 1 2 3 4 5 6 7 8
I1: add s8, s4, s5 F D E M W
I2: sub s2, s8, s3 F D E M W
I3: or s9, t6, s8 F D E M W
I4: and s7, s8, t2 F D E M W
● I1 writes s8 in cycle 5 during the Write back stage.
● I2 needs s8 in cycle 3 during the Decode stage.
So the hazard occurs because I2 reads s8 before I1 writes it back.
d) To avoid the hazard without forwarding, we insert enough NOPs so that the dependent
instruction reads the correct value only after the producing instruction has completed
Writeback.
Corrected instruction sequence:
I1: add s8, s4, s5
nop
nop
I2: sub s2, s8, s3
I3: or s9, t6, s8
I4: and s7, s8, t2
e) Corrected pipeline timing diagram after inserting NOPs
Cycles 1 2 3 4 5 6 7 8 9 10
I1: add s8, s4, s5 F D E M W
nop F D E M W
nop F D E M W
I2: sub s2, s8, s3 F D E M W
I3: or s9, t6, s8 F D E M W
I4: and s7, s8, t2 F D E M W
Now I2 reaches its Decode stage only after sufficient delay, so the value of s8 is available.
f) Originally, the 4 instructions would complete in 8 cycles. After inserting 2 NOPs, execution
completes in 10 cycles. So the number of extra cycles added is: 10 - 8 = 2 cycles. Thus, 2 extra
cycles are added because of the hazard.
The instruction sequence has a data hazard on register s8. The dependency type is RAW (Read
After Write) because instruction I1 writes s8, while instructions I2, I3, and I4 read it. Without
hazard handling, the dependent instruction reaches the Decode stage before the result is
written back, causing incorrect execution. To solve this using compiler-based scheduling, two
NOPs are inserted after the add instruction. As a result, the total execution time increases from
8 cycles to 10 cycles, so 2 extra cycles are added.
Q3. Consider the following sequence of instructions executed on a processor:
I1: ADD R1, R2, R3
I2: SUB R4, R1, R5
I3: ADD R6, R4, R7
I4: MUL R1, R6, R8
I5: ADD R9, R1, R2
Answer the following:
1. Identify all data dependencies present in the instruction sequence.
2. For each dependency, specify whether it is
a) RAW (Read After Write)
b) WAR (Write After Read)
c) WAW (Write After Write)
3. Mention the register responsible for each dependency.
Ans 3:
I1: ADD R1, R2, R3 → writes R1
I2: SUB R4, R1, R5 → reads R1, writes R4
I3: ADD R6, R4, R7 → reads R4, writes R6
I4: MUL R1, R6, R8 → reads R6, writes R1
I5: ADD R9, R1, R2 → reads R1, writes R9
RAW (Read After Write)
● I1 → I2 on R1
● I2 → I3 on R4
● I3 → I4 on R6
● I4 → I5 on R1
RAW means the second instruction reads a value written by the previous instruction.
WAR (Write After Read)
● I2 reads R1, I4 writes R1 → WAR on R1
WAR means earlier instruction reads, later writes.
WAW (Write After Write)
● I1 writes R1
● I4 writes R1
So:
● I1 → I4 on R1
WAW means two instructions write the same register.
true data dependencies = RAW.
name dependencies = WAR, WAW.
Q4. Consider a 5-stage pipelined RISC-V processor with stages Fetch (F), Decode (D), Execute
(E), Memory (M), Writeback (W). The processor supports data forwarding, but a stall is
required for load-use dependency. The following instruction sequence is executed:
I1: lw s7, 40(s5)
I2: and s8, s7, t3
I3: or t2, s6, s7
I4: sub s3, s7, s2
Answer the following:
1. Identify the hazard present in the instruction sequence.
2. Explain why forwarding alone cannot solve the hazard.
3. Draw the pipeline timing diagram with forwarding and stall logic.
4. What would happen if the stall logic was not used?
Ans 4: 1) The hazard is a data hazard, specifically a RAW (Read After Write) hazard.
● I1 writes to register s7
● I2 immediately reads s7
● I3 also reads s7
● I4 also reads s7
So the main immediate problem is between:
● I1: lw s7, 40(s5)
● I2: and s8, s7, t3
This is the classic load-use data hazard.
2) In a lw instruction, the data is obtained from memory, so the loaded value becomes available
only after the Memory stage. But I2 needs to register s7 in its Execute stage immediately in the
next cycle.
So the problem is:
● I1 gets the value late, after M
● I2 needs the value early, in E
That means the value is not ready in time for immediate forwarding to I2.
3) Pipeline timing diagram with forwarding and stall logic:
a) Without stall
Cycles 1 2 3 4 5 6 7 8
F D E M W
I1: lw s7, 40(s5)
F D E M W
I2: and s8, s7, t3
F D E M W
I3: or t2, s6, s7
F D E M W
I4: sub s3, s7, s2
b) With stall
Cycles 1 2 3 4 5 6 7 8 9
F D E M W
I1: lw s7, 40(s5)
F D D E M W
I2: and s8, s7, t3
F F D E M W
I3: or t2, s6, s7
F D E M W
I4: sub s3, s7, s2
With stall I2 stays in Decode for one extra cycle and I3 is held in Fetch during that stall. After
that, I2 can proceed and get s7 through forwarding. I3 and I4 do not need extra stalls because
forwarding from the Writeback/Memory stage makes the value available when they reach
Execute.
4) If stall logic were not used, I2 would move to Execute before the loaded value of s7 is ready.
So I2 would use an incorrect/old value of s7, leading to a wrong result.