Structural Hazards and the Cost of Duplicated Resources

A data hazard is a relationship between instructions. A structural hazard is a relationship between an instruction and a piece of hardware that only one instruction can use at a time. The distinction matters because the fixes are different: data hazards are resolved by forwarding or stalling, and structural hazards are resolved by buying more hardware, by time-sharing the hardware with a schedule, or by removing the requirement that the hardware be used in a particular cycle. Which of those is chosen determines whether the pipeline loses throughput permanently or only for the instructions that collide.

The single-memory collision

The clearest case is a pipeline with one unified memory. IF reads an instruction from it in every cycle; MEM reads or writes data in the same cycle. Two instructions in different stages both want the memory, and only one can have it.

The naive fix is to stall. IF waits whenever MEM needs the memory, which in a load/store-heavy stream happens often. The cost is not one cycle per load: it is one cycle per load while a fetch is also pending, and since IF issues every cycle, that is nearly every load. A pipeline whose ideal CPI is 1 drifts toward 2 for memory-heavy code.

The fix that is actually used in every commercial design is to split the memory into an instruction memory and a data memory, each with its own port. The two are then independent structures, and the conflict disappears. What is bought is a second port plus a second set of decoders and sense amplifiers; what is paid is area and, in a cache-based design, a second tag array and a second miss-handling path. The trade is explicit: silicon for cycles.

An intermediate design keeps one memory but adds a second port. Dual-ported SRAM cells are substantially larger than single-ported ones, roughly doubling the bit cell area in the common implementations, and the second port also slows access slightly. On-chip caches make the split cheaper than it sounds, because the two structures are small and each can be sized for its own access pattern.

Ports on the register file

The register file is the second resource with a fixed port count. A five-stage RISC pipeline needs two reads in ID and one write in WB every cycle. A three-port register file handles that. What breaks it is a design that wants a fourth access, for example a load/store machine with three-operand instructions that also reads a value for the store address computation in a later stage, or a pipeline that performs write-back in the same half-cycle as two reads without the edge-timing trick described in the five-stage pipeline.

The usual resolution is to replicate the register file rather than add a port to each cell: duplicate the array, write both copies, and read from whichever copy is free. Duplication costs area proportional to the register count, but the register file is small — 32 entries of 64 bits is 2 kilobits — so duplicating it is cheap compared with adding a port to a large memory. The write must reach both copies, which is a fan-out problem rather than a capacity problem, and the copies must stay coherent by construction.

Functional units and the multi-cycle escape

A single unpipelined multiplier occupies EX for several cycles. Any instruction that wants the multiplier behind it must wait, and if the pipeline does not have a mechanism to hold an instruction in EX, the whole pipeline stalls. This is a structural hazard created by a unit that is not itself pipelined.

Two designs resolve it. The first makes the unit pipelined: a multiplier with internal registers accepts a new pair of operands every cycle and produces a result every cycle after a fixed latency. The area cost is the internal pipeline registers and the wider result bus, and the design cost is that the unit’s latency becomes visible to the forwarding network, so every consumer of its result needs a bypass path of the right depth. The second leaves the unit unpipelined but gives it a queue, so instructions issue into the unit and the pipeline continues; the consumer stalls on the result only when it actually needs it. That is dynamic scheduling, and it converts a structural hazard into a scoreboard dependency.

The choice interacts with the instruction set. A machine that exposes multiply latency in the architectural definition, as some DSPs do, pushes the scheduling problem to the compiler and keeps the hardware simple. A machine that hides it needs either a pipelined unit or an interlock, both of which cost more than the arithmetic itself.

Arbitration when replication is impossible

Off-chip resources cannot be duplicated per instruction. A memory controller has one bus, and the bandwidth of that bus is a shared resource. When two pipeline stages both need a bus transfer in the same cycle, one must wait. Arbitration is the general answer: a priority scheme decides who gets the resource, and the loser is delayed.

The scheduling consequence is that the pipeline’s timing becomes data-dependent. A store that loses arbitration occupies MEM for an extra cycle, and everything behind it shifts. The delay is not attributable to any particular instruction in the program; it depends on what else is in flight. This is one reason published cycle counts for memory operations are always ranges or best cases rather than fixed numbers.

There is a further subtlety when the shared resource is a cache. A cache has a fixed number of tag lookups per cycle, and two accesses to the same bank in the same cycle conflict even if the tags differ. Banking the cache by address bits lets independent accesses proceed in parallel and serializes only the ones that hit the same bank. The bank count is chosen from the expected access pattern, and the pathological case is a stride that maps every access to one bank. A 32-bank cache with 4-byte granularity and a 128-byte stride hits bank (128/4) mod 32 = 0 every time, serializing what the banks were meant to parallelize.

/* Which bank a byte address lands in, for a cache with B banks of `gran` bytes.
   The stride that defeats the banking is the one whose address delta is a
   multiple of B * gran. */
static unsigned bank_of(unsigned long addr, unsigned gran, unsigned banks)
{
    return (addr / gran) % banks;
}

/* Count how many of n strided accesses collide in the worst single bank. */
unsigned worst_bank_load(unsigned long base, unsigned long stride,
                         unsigned n, unsigned gran, unsigned banks)
{
    unsigned count[64] = {0};          /* banks <= 64 in this helper */
    for (unsigned i = 0; i < n; i++)
        count[bank_of(base + i * stride, gran, banks)]++;
    unsigned worst = 0;
    for (unsigned b = 0; b < banks; b++)
        if (count[b] > worst) worst = count[b];
    return worst;                       /* == n when stride % (B*gran) == 0 */
}

Why structural hazards are the ones that get designed away

Data and control hazards are properties of the program and can only be mitigated. Structural hazards are properties of the machine and can be removed outright by spending area, which is why they are the first thing a microarchitect retires. The order in which they are retired is a budget statement: split the instruction and data paths first, because fetch-versus-memory is the most frequent conflict; replicate the register file next, because it is small; pipeline the multiplier after that, because a multi-cycle unit is a permanent throughput hole; and leave bus arbitration to the memory system, because off-chip bandwidth cannot be replicated at all.

The residue is the set of conflicts that are too rare to justify hardware. A floating-point unit shared between two issue slots, a single divider used once every few hundred instructions, a translation lookaside buffer with fewer ports than the pipeline would like: these are handled by stalls, and the stalls are acceptable because the frequency is low. The calculation is always the same: multiply the conflict frequency by the cycles lost, compare with the area cost of the fix, and choose. That calculation, rather than any principle, decides which structural hazards a given machine tolerates.

One more class deserves mention because it is easy to overlook: hazards inside a single instruction. A pipeline stage that needs two values from the same structure, such as a store that must read both its address register and its data register in the same cycle, is a structural hazard within one instruction rather than between two. It surfaces as an extra read port requirement, and it is why store data is often carried down the pipeline from ID rather than read late. Holding the value in a pipeline register costs flip-flops; reading it late costs a port. On a 32-entry register file the flip-flops usually win.