Implement 2-Stage Pipeline and Detect Hazards

Topic Overview

Two Stages: Fetch and Execute

Pipelining overlaps instruction phases. A two-stage design fetches the next instruction while the current one executes. Throughput can approach one instruction per cycle when the pipeline stays full.

cCopy
Loading…

Data Hazards

A hazard occurs when execute reads a register that the previous instruction has not yet written. Example:

cCopy
Loading…

Without forwarding or stalls, the SUB stage reads stale R1.

• Detect: compare source registers of ID stage with destination of EX stage
• Stall: bubble a NOP until write completes
• Forward: pass ALU output directly to next stage (covered later)

For this exercise, you will split your emulator into IF and EX stages and log hazard stalls. This task asks you to count how many bubbles a tight read-after-write chain injects, foreshadowing the five-stage pipeline ahead.

Working Through the Exercise

Keep the relevant datasheet, ISA manual, or architecture textbook chapter open while you implement. When your output disagrees with the reference trace on the same program, the bug is usually a mis-decoded opcode, a stale register read, or a flag bit left unchanged after arithmetic.

• Trace first: walk one failing input by hand before changing random lines
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

For this exercise, you will use those habits while implementing the requirement in the starter code. Microarchitectural product names change across CPU generations, but the control ideas (fetch, bypass, cache lines, vector lanes) stay stable enough to debug from first principles.

Your Task

Pipeline the toy CPU into two stages. FD fetches, decodes and reads registers. EX executes and writes the result back at the end of the cycle. While one instruction executes, the next is being fetched, so a full pipeline completes one instruction per cycle. Two things break that: a data hazard (FD needs a register that the instruction in EX hasn't written yet → stall) and a taken branch (the instruction already fetched is the wrong one → flush). Simulate the pipeline cycle by cycle and compare it with the unpipelined CPU.

ISA

Registers R0: R7 (integers, start at 0). Labels are name: at the start of a line. Programs are well-formed.

Instructions are named I0, I1, … by their position in the program (labels and blank lines don't count).

Pipeline rules, per cycle

1. EX executes its instruction; results are written at the end of the cycle.
2. Hazard: if the instruction in FD reads a register that the instruction in EX writes, it can't read it yet → stall: FD keeps its instruction, EX gets a bubble next cycle.
3. Branch: if EX holds a taken BNEZ, the instruction in FD is flushed (EX gets a bubble), and FD fetches the target next cycle. This takes priority over a stall.
4. Otherwise the FD instruction moves to EX and FD fetches the next instruction.
5. The fetch unit stops after fetching a HALT (and restarts if a taken branch redirects it). Fetching past the last instruction yields nothing.
6. The run ends after the cycle in which HALT is in EX, or when both stages are empty. Give up after 200 cycles.

Output

One line per cycle, with -- for an empty stage or bubble. Add stall Rn (the first conflicting source register, in operand order) or flush when that rule applies:

cCopy
Loading…

Then:

cCopy
Loading…

N counts completed instructions including HALT. Unpipelined, each instruction takes both stages back to back. Print the speedup 2N / C with 2 decimals. If the cycle limit is hit, print cycle limit reached in place of the retired and unpipelined lines.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Model the two pipeline latches explicitly and compute the next-cycle contents from the current ones.
2. Register values are computed in EX, in program order, so the final registers match a non-pipelined run.

Hidden tests cover a countdown loop (BNEZ taken several times, then not taken), and a chain of back-to-back dependent instructions in a program that has no HALT.