Structural Hazards

A pipeline overlaps the execution of multiple instructions, each occupying a different stage at each clock cycle. This overlap is only valid if every stage's hardware is available to every instruction that needs it. A structural hazard occurs when the pipeline schedule would require two (or more) instructions, in different stages, to use the same physical resource — a memory port, a functional unit, a register-file port, a bus — during the same clock cycle. The hardware cannot serve both requests simultaneously, so naively continuing would produce incorrect behavior (one access silently overwriting or ignoring the other) or is simply electrically impossible (one wire cannot carry two values at once). The canonical resource is memory. In a five-stage MIPS/RISC-V-style pipeline (IF, ID, EX, MEM, WB), the IF stage of instruction i+3 wants to read an instruction word from memory in the same cycle that the MEM stage of instruction i wants to read or write a data word. If instruction and data memory are the same physical memory with one port, both accesses cannot happen in that cycle. Other classic structural hazards include: a single non-pipelined multiplier that ties up the EX stage for several cycles while later instructions pile up behind it; a single write port on the register file when two instructions in WB in the same cycle both need to write back (rare in a scalar in-order pipeline, but common in superscalar designs); and a single shared bus between the pipeline and a peripheral or memory controller. It is essential to distinguish structural hazards from data and control hazards. A data hazard exists because an instruction needs a value produced by another instruction that has not been computed or written back yet — the hardware could serve both requests, but the data is not ready (this leads to Data Hazards and Forwarding). A control hazard exists because the pipeline does not yet know which instruction to fetch next (this leads to control-flow resolution, branch prediction, and delayed branches). A structural hazard exists because the hardware itself is double-booked, independent of what values are involved. This makes structural hazards, in one sense, the simplest hazard to reason about: you can detect them by looking only at a table of which stage uses which resource in which cycle, with no attention to instruction semantics at all.

The standard way to reason about structural hazards is to build a reservation table: a grid whose rows are hardware resources and whose columns are pipeline stages (equivalently, relative time steps after an instruction enters the pipeline). Each entry marks whether an instruction occupies that resource that many cycles after it starts. Two instructions separated by k cycles collide on resource R if their reservation-table rows for R overlap when shifted by k. For the concrete unified-memory example, define resource `MEM`. Instruction i uses `MEM` in its IF stage (cycle t) and again in its MEM stage (cycle t+3, since IF, ID, EX, MEM are stages 1–4). Instruction i+3, entering the pipeline three cycles after instruction i, wants to use `MEM` for its IF stage at cycle t+3 — exactly the cycle that instruction i needs `MEM` for its MEM stage. Collision. The pipeline control logic must detect this collision every cycle and, if found, freeze the earlier stage (or the later stage, depending on priority policy) by inserting a bubble — a cycle in which no useful work advances, functionally equivalent to a `nop` injected into the pipeline.

Detection and stall algorithm

``` // Runs once per clock cycle, in hardware, for every resource R // that can be shared across stages. function detect_and_resolve_structural_hazard(cycle_t, pipeline_state): for each shared_resource R in ResourceList: requesters = [] for each stage S in PipelineStages: instr = pipeline_state[S] // instruction currently in stage S if instr != BUBBLE and stage_needs_resource(S, instr, R): requesters.append((S, instr)) if len(requesters) > 1: // Conflict: resource R is wanted by more than one stage this cycle. winner = pick_priority(requesters) // policy: e.g., "later pipeline stage wins" for (S, instr) in requesters: if (S, instr) != winner: stall_stage(S) // freeze this stage's instruction in place insert_bubble(downstream_of(S)) // send a NOP forward instead // Stages not stalled proceed normally this cycle. ``` ``` // Concrete instantiation for the IF/MEM shared-memory hazard, // as implemented by the pipeline's hazard-detection unit. function memory_hazard_check(IF_instr, MEM_instr): if IF_instr requires memory read and MEM_instr requires memory read or write: // give MEM (older instruction) priority — it must complete, it's further along stall(IF_stage) // freeze PC, freeze IF/ID latch contents insert_bubble(ID_stage) // ID stage receives a NOP this cycle // else: no conflict, both proceed ``` The priority rule "older instruction wins" is not arbitrary: an in-order pipeline must retire instructions in program order, and letting a younger instruction "jump ahead" of an older one on a shared resource would either violate program order or require complex out-of-order bookkeeping. Stalling the younger instruction (freezing IF, keeping the same PC, holding the IF/ID latch) and inserting a bubble one stage downstream is the standard, easily verified fix.

Why splitting memory works

The dominant real-world fix is not to stall at all, but to make the conflict structurally impossible: give instruction fetch and data access separate physical memories (or separate cache ports), so `MEM_instruction` and `MEM_data` are different resources that can never collide. This is why virtually every real pipelined CPU has a split L1 cache — separate instruction cache (I-cache) and data cache (D-cache) — even though a unified L1 would sometimes have better hit rates. The throughput gain from eliminating a hazard that would otherwise fire on nearly every load/store instruction vastly outweighs the modest capacity loss from splitting one cache into two smaller ones.

Cost of a structural hazard (stall model). Suppose a resource conflict fires with probability p per eligible instruction (e.g., every load/store instruction, if memory is unified) and each conflict costs exactly one bubble cycle. For n instructions with a fraction f being loads/stores, the total stall cycles are ``` StallCycles ≈ f · n · p ``` and the effective cycles-per-instruction (CPI) becomes ``` CPI_effective = 1 + f · p ``` instead of the ideal CPI of 1 for a fully pipelined, hazard-free design. This is a linear, per-instruction overhead — not asymptotic complexity in the algorithmic sense, but the relevant "complexity" metric for a hardware structure: cycles per instruction and hardware area/ports. For the unified-memory hazard specifically, every load and store instruction that overlaps with any IF in the same cycle triggers a stall, so in the worst case (steady stream of loads/stores with instruction fetch every cycle) p → 1, giving up to a 33%–50% CPI penalty in a naive 5-stage pipe, depending on instruction mix — a severe cost, which is exactly why real designs eliminate it structurally rather than tolerate it.

Cost of the fix (duplication model). Splitting into I-cache and D-cache costs extra hardware area (two tag arrays, two sets of sense amps, etc.) roughly proportional to the number of caches added, a constant-factor hardware cost, but reduces the stall probability p to 0 for that hazard. The trade is: spend area once, save cycles forever — a classic space/time trade that is almost always favorable once a hazard is common enough (loads and stores are typically 25–40% of dynamic instructions in real workloads).

Correctness argument. The pipeline is correct with respect to a structural hazard if and only if the reservation-table conflict is always detected before the conflicting cycle executes, and the resolution (stall or duplicate) always removes the double-use in that cycle without altering any other instruction's stage assignment. We can state this as an invariant maintained every cycle: > Invariant: At the end of every clock cycle, for every shared resource R, at most one non-bubble instruction is occupying R. The detection algorithm above checks this invariant proactively, before the cycle commits: it inspects, for the upcoming cycle, which instructions in which stages would use R, and if more than one would, it prevents all but one (the priority winner) from advancing into that use this cycle by stalling and substituting a bubble. Because a bubble by construction uses no resource, inserting a bubble can never itself create a new conflict. By induction over cycles — if the invariant holds at the start of cycle t (trivially true at t=0, an empty pipeline) and the detection/stall logic prevents any violation during cycle t, then it holds at the start of cycle t+1 — the invariant holds for all cycles, so the pipeline never actually double-drives a shared resource. This is precisely why structural-hazard logic is simpler to verify than data-hazard forwarding logic: it is a pure occupancy/scheduling argument with no dependence on data values, addresses, or control flow, only on which stage each instruction currently sits in.

Honesty about trade-offs. Stalling is simple to implement and verify but throws away cycles permanently; there is no way to "recover" a bubble later (in a strictly in-order pipeline). Duplicating hardware avoids stalls entirely but costs silicon area, power, and sometimes cycle time (a bigger, more complex register file with more ports can have a longer access time, which can lengthen the clock period for every instruction, not just the conflicting ones). Real designs choose per-resource: memory is almost always split (cheap fix, huge win), but a full crossbar giving every functional unit unlimited register-file ports would be prohibitively expensive, so real superscalar machines instead limit issue width or use banked/multi-ported register files as a compromise, accepting occasional structural stalls when contention is rare enough not to matter.

Consider this instruction sequence running on a 5-stage pipeline (IF, ID, EX, MEM, WB) with a single unified memory (one port, shared by IF and MEM): ``` I1: LW R1, 0(R2) ; load I2: ADD R3, R1, R4 I3: SUB R5, R6, R7 I4: OR R8, R9, R10 ``` Without any hazard, instruction k would be in IF at cycle k, ID at cycle k+1, EX at cycle k+2, MEM at cycle k+3, WB at cycle k+4. I1's MEM stage falls in cycle 4. I4's IF stage, absent any stall, would also fall in cycle 4 (since I4 is the 4th instruction, IF at cycle 4). Both want the single memory port in cycle 4 — a structural hazard.

At cycle 4, I1 is in MEM (needs the memory port) and, without intervention, I4 would be trying to enter IF (also needs the memory port). The hazard-detection unit sees this collision one cycle ahead, stalls I4's IF (freezes the PC, keeps fetching nothing useful — a bubble propagates into ID), and lets I1 win the memory port since it is older. I4 then successfully fetches in cycle 5, one cycle later than the ideal schedule, and every later stage of I4 is pushed back by exactly one cycle. I2 and I3, already past their IF stage, are entirely unaffected — the stall is localized to the instructions still contending for the resource.

Tally: 4 instructions, ideal completion at cycle 8 (I4's WB) with no hazard would have been cycle 7 — one extra cycle, exactly matching the prediction `StallCycles = 1 conflict × 1 bubble`. CPI over this window is `8 cycles / 4 instructions = 2.0` locally, though amortized over a longer program with only occasional such collisions, the steady-state CPI approaches `1 + f·p` as derived above.

Second case — the fix in action. Rerun the identical instruction sequence on a machine with a split I-cache/D-cache. Now I1's MEM access goes to the D-cache and I4's IF access goes to the I-cache — different physical ports, no conflict.

All four instructions complete by cycle 7 with zero bubbles — the ideal `n + 4` cycle schedule for an n-instruction, 5-stage pipe. This is the direct, measurable payoff of eliminating the structural hazard by hardware duplication rather than tolerating it with stalls.

The formalization of pipeline hazards — structural, data, and control — as a taxonomy for reasoning about pipelined machine design was crystallized in the classic RISC pipeline literature of the early 1980s, building on decades of mainframe and supercomputer pipelining practice.

Every modern pipelined CPU core — from embedded microcontrollers to high-end server chips — is designed around eliminating the most common structural hazards by construction. The near-universal split L1 instruction/data cache exists directly because of the IF/MEM conflict described here; a unified L1 would need a second read/write port or would stall on essentially every load and store. Multi-ported register files in superscalar and out-of-order processors (Intel's Core and Xeon lines, AMD's Zen, Arm's Cortex-A and Neoverse families) are engineered with enough read/write ports to let several instructions in flight access operands simultaneously, precisely to avoid structural stalls in the decode/writeback stages when issue width is greater than one. GPUs, which issue many threads' worth of instructions in parallel, replicate ALUs and memory banks partly to avoid the same class of contention at massive scale, and memory-bank conflicts in GPU shared memory are a direct descendant of the structural-hazard idea. Understanding structural hazards is also the natural stepping stone to Data Hazards and Forwarding (where the conflict is over values, not hardware) and to Control Hazards (where the conflict is over which instruction to fetch), the other two legs of the classic pipeline hazard taxonomy taught alongside The Pipelined Datapath.

Ask the tutor: How would the reservation-table method change if a functional unit (like a multiplier) takes 4 cycles instead of 1, and how many structural stalls would a back-to-back sequence of multiply instructions incur?