Pipeline Hazard in a Single-Cycle-to-Pipelined ALU Datapath
A simple datapath executes ADD, SUB, AND, OR, and a conditional branch. Originally single-cycle. It is converted to a 3-stage pipeline: IF, ID/EX (register read + ALU), WB (register write). There is no forwarding network. The register file writes on the rising edge and reads combinationally within the same cycle. A test program is: I1: ADD R1,R2,R3; I2: SUB R4,R1,R5; I3: AND R6,R4,R7; I4: OR R8,R6,R9; I5: BEQ R8,R0,target. The team observes wrong results starting at I2 and wants to know whether adding forwarding alone fixes everything or whether stalls are still required.
1. Identify each data dependence and determine, without forwarding, how many stall cycles each pair needs given this 3-stage structure.
Read the worked answer
Dependences (RAW):
- I1→I2 on R1
- I2→I3 on R4
- I3→I4 on R6
- I4→I5 on R8 (branch compares R8)
Timing without forwarding: a value written in WB is available to a reader in ID/EX. I1 computes in ID/EX during its cycle 2, writes in WB during its cycle 3. I2 needs R1 in its ID/EX, which is its cycle 2 - but I2's cycle 2 overlaps I1's cycle 2 (ALU result not yet written). I2 must wait until I1's WB completes, i.e. I2's ID/EX must be delayed by 1 cycle minimum (wait for writeback edge). So each RAW pair needs 1 stall cycle without forwarding (the producer's result only lands at end of its WB stage, and the consumer's read must be after that edge).
So 4 dependence pairs → up to 4 stall cycles inserted, one per pair, in this straight-line code.
2. Now add full forwarding (EX-result and WB-result paths). Recompute the stalls and explain which dependence, if any, still cannot be fully forwarded.
Read the worked answer
With forwarding:
- ALU→ALU (I1→I2, I2→I3, I3→I4): the producer's ALU result is available at the end of its ID/EX stage; the consumer's ALU needs it at the start of its ID/EX. Because stages overlap, the consumer's ID/EX is one cycle after the producer's ID/EX, so the value can be forwarded from the EX/MEM-style latch. These need 0 stalls with an EX-to-EX forward path.
- I4→I5: the branch decision is made in ID/EX (since there is no separate branch stage). I4's OR result is produced in ID/EX of I4; I5's branch compare happens in ID/EX of I5, one cycle later. Forwarding can supply it, so 0 stalls - provided the comparator in ID/EX accepts a forwarded operand.
So with full forwarding, this sequence needs 0 stalls. The catch: the load-use style problem does not appear here because there is no load. If a load existed, its data arrives only at end of WB, and a consumer immediately after would still need 1 stall even with forwarding.
3. The team adds forwarding but still sees I2 produce a wrong value in one corner case. Give the most likely cause and how to fix it, referencing the write/read timing given.
Read the worked answer
Most likely cause: the register file writes on the rising edge and reads combinationally in the same cycle, so a WB in the same cycle as an ID read can create a same-cycle read/write hazard. If the read port sees the old value before the write edge, a consumer that reads in the same cycle as the producer's WB gets stale data; if it sees the new value, it is fine. The ambiguity depends on internal timing (write-first vs read-first register file).
Fix: make the register file explicitly write-first (write then read within the cycle) or add a bypass from the WB input to the read ports when the write address matches a read address. Alternatively, ensure the consumer's ID/EX is scheduled strictly after the WB edge. Also verify the forwarding mux priority: WB-result forwarding must take precedence over EX-result forwarding when both match the same source register (the younger producer wins). A wrong priority in the mux is a classic cause of a single wrong value that appears only when two in-flight instructions write the same register.