15.1 Pipelining and Data Hazards

By breaking an instruction into multiple stages and allowing different instructions to occupy different stages simultaneously, throughput is improved. Pipelining doesn't make any single instruction execute faster; instead, it reduces the interval between the completion of consecutive instructions.

The classic five-stage RISC pipeline serves as a solid foundation for understanding the concept. Modern CPUs, however, may feature deeper, wider pipelines with dynamic scheduling in front-end and back-end stages. First, master the simpler model thoroughly before moving on to Branch Prediction and Out-of-Order Execution.

1. Latency and Throughput Are Not the Same

Suppose laundry requires three steps: wash, dry, and fold, each taking 30 minutes, with three stations able to work on different loads simultaneously:

• A single load from start to finish still takes 90 minutes of delay;
• Once the line is full, one load completes every 30 minutes, increasing throughput.

The instruction pipeline works similarly. The classic five-stage breakdown is:

Stage	Name	Primary Activity
IF	Instruction Fetch	Fetch instruction from PC
ID	Instruction Decode	Decode instruction and read registers
EX	Execute	ALU operation or address calculation
MEM	Memory Access	Access data storage hierarchy
WB	Write Back	Write result back to register

Ideal timeline:

cycle        1    2    3    4    5    6    7
instruction A IF   ID   EX   MEM  WB
instruction B      IF   ID   EX   MEM  WB
instruction C           IF   ID   EX   MEM  WB

Instruction A still passes through all five stages, but instruction B can begin before A finishes. In steady state, an ideal single-issue pipeline completes one instruction per cycle, achieving an instruction per cycle (IPC) close to 1.

The claim "dividing into five stages speeds up performance by five times" does not hold. Real-world performance gains are constrained by several factors:

• The slowest stage determines the clock cycle length;
• Pipeline registers themselves introduce latency and power consumption;
• The pipeline must be filled and emptied;
• Dependencies, branches, and resource conflicts introduce stalls;
• Cache misses can take significantly longer than a single pipeline stage.

2. Three Kinds of Hazards

Structural Hazards

Two instructions in flight require the same hardware resource during the same cycle. For example, a unified single-port memory must serve both fetching the next instruction and reading data for the current load operation.

Solutions include adding more ports, separating instruction and data caches, duplicating resources, or stalling the pipeline. The more hardware resources you add, the greater the area, power consumption, and routing complexity. Thus, handling structural hazards represents a design trade-off.

Data Hazards

Instructions have dependencies on registers or memory:

RAW (Read After Write) is a true dependency:

add x5, x1, x2
sub x6, x5, x3   # Read the new x5 produced by add

WAR (Write After Read) is an anti-dependency:

read x5
write x5

WAW (Write After Write) is an output dependency:

write x5
write x5

The read/write lines are dependency notation, not RISC-V instructions. In this simple five-stage model, all register reads occur in ID and writes occur in order in WB, so RAW is the main register hazard. WAR and WAW dependencies only obstruct scheduling when out-of-order execution or completion is allowed; modern CPUs eliminate them using register renaming. Memory dependencies are harder because two memory addresses may not be known to be equal until execution time.

Control Hazards

When encountering conditional branches or indirect jumps, the fetch unit doesn't yet know the next program counter (PC). If we wait until the condition is fully evaluated before fetching, we waste cycles; if we guess, a wrong prediction requires discarding all work on the incorrect path and restarting from the correct address.

The earlier the prediction, the deeper the front-end pipeline, and the wider the issue width, the more resources the incorrect path may consume. This topic will be explored in detail in the next section.

3. Forwarding Delivers Results Before Register Write-Back

In the classic five-stage pipeline, ALU results are generated at the end of the EX stage but may not be written into the register file until the WB stage. If the next instruction has to wait until the WB stage to read the value, it wastes cycles.

Forwarding (or bypassing) directly sends intermediate results from pipeline registers to the input of the subsequent ALU:

add: IF ─ ID ─ EX ─ MEM ─ WB
                 ╲
sub:      IF ─ ID ─ EX ─ MEM ─ WB
                   ↑
             forwarded value

The control logic compares the source register of the next instruction with the destination register of the preceding instruction in flight, then selects either the register file value, the EX/MEM result, or the MEM/WB result.

The forwarding network is a microarchitectural detail, visible only in hardware design, not in disassembly. You won't see in a disassembly that "this instruction took the bypass path." Assembly code only reveals data dependencies; whether and where forwarding occurs is determined by the specific CPU design.

4. Why Load-Use Might Still Cause Stalls

Consider:

lw  x5, 0(x10)
add x6, x5, x7

In the classic pipeline model, the data from lw only becomes available at the end of MEM, and the subsequent add requires that data at the start of the EX stage in the same cycle. Standard EX-to-EX forwarding isn't fast enough, so a hazard unit forces the dependent instruction to stall for one cycle:

lw : IF ─ ID ─ EX ─ MEM ─ WB
add:      IF ─ ID ─ stall ─ EX ─ MEM ─ WB

"The stall for exactly one cycle" applies only to this specific pipeline stage configuration and the assumption of cache hits. Different microarchitectures may schedule, replay, or deliver load results with different latencies; a cache miss can extend the wait by many cycles.

A compiler can schedule an independent instruction in the gap to hide the delay; the true dependency remains, and modern out-of-order CPUs can execute other ready work to hide some of the delay. However, when no such independent work exists, the actual dependency chain still sets the ultimate lower bound.

5. Dependency Chain Limits Instruction-Level Parallelism

The two functions use unsigned integers and agree modulo 2^64. The sample stays within range, so both also equal the mathematical sum. Floating-point addition does not generally permit equivalent regrouping. The first version uses a single accumulator, where each addition depends on the previous one. The second version employs four independent accumulators, with the final result obtained by combining them:

#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

static uint64_t sum_one(const uint32_t *values, size_t length) {
    uint64_t sum = 0;
    for (size_t i = 0; i < length; ++i) {
        sum += values[i];
    }
    return sum;
}

static uint64_t sum_four(const uint32_t *values, size_t length) {
    uint64_t a = 0;
    uint64_t b = 0;
    uint64_t c = 0;
    uint64_t d = 0;
    size_t i = 0;

    size_t bulk_end = length - length % 4;
    for (; i < bulk_end; i += 4) {
        a += values[i];
        b += values[i + 1];
        c += values[i + 2];
        d += values[i + 3];
    }
    for (; i < length; ++i) {
        a += values[i];
    }
    return a + b + c + d;
}

int main(void) {
    enum { COUNT = 100000 };
    uint32_t *values = malloc(sizeof(*values) * COUNT);
    if (values == NULL) {
        return EXIT_FAILURE;
    }

    for (size_t i = 0; i < COUNT; ++i) {
        values[i] = (uint32_t)(i % 97);
    }

    uint64_t first = sum_one(values, COUNT);
    uint64_t second = sum_four(values, COUNT);
    printf("%" PRIu64 " %" PRIu64 "\n", first, second);

    free(values);
    return first == second ? EXIT_SUCCESS : EXIT_FAILURE;
}

cc -std=c17 -O2 -Wall -Wextra accumulators.c
./a.out

Multiple accumulators provide independent addition operations, giving superscalar or out-of-order CPUs more parallel work to execute. However, the performance difference cannot be directly attributed to the pipeline alone; compilers may automatically unroll, vectorize, or transform both functions into different instruction sequences. When analyzing performance, it is essential to examine the generated assembly code and measure execution time using appropriate performance counters for the target CPU.

6. The Boundary Between Compilers, ISA, and Microarchitecture

A C loop undergoes multiple layers of transformation:

C source code
  ↓ compiler optimization
ISA instructions
  ↓ decode / rename / schedule
micro-operations and execution units

The compiler knows the target ISA, instruction latency models, and static dependencies, enabling it to:

• Eliminate redundant work;
• Unroll loops;
• Choose between branch instructions or conditional moves;
• Automatically vectorize code;
• Reorder independent instructions;
• Prove memory accesses do not conflict via alias analysis.

The CPU, in contrast, observes real cache misses, branch history, and operand readiness during runtime and performs dynamic scheduling. Together, these components work in tandem, but neither can fully replace the other.

The C volatile qualifier is not a general barrier preventing CPU out-of-order execution. It primarily constrains access to volatile objects within an abstract machine, and is typically used in specific interfaces such as memory-mapped I/O. For thread synchronization, developers should use atomic operations, mutexes, and the language’s memory model. In Java, volatile has well-defined cross-thread visibility and ordering semantics specified by the language specification; these two constructs cannot be directly compared based on their names alone.

7. Cache Miss Amplifies Short Pipeline Issues

ALU operations can be fast, but memory hierarchy delays can be orders of magnitude larger. After a load miss, the CPU may:

• Continue searching within the cache hierarchy;
• Generate and track pending memory requests;
• Execute subsequent instructions unrelated to the load;
• Stall due to resource exhaustion or data dependencies;
• Eventually retrieve the data from a deeper memory level and resume dependent instructions.

Memory-level parallelism enables multiple independent misses to be in flight simultaneously. In a linked list traversal, the next address depends on the current node’s content, making such parallelism difficult to achieve. In contrast, sequential array access is more amenable to prefetching and can trigger multiple concurrent requests.

Thus, "optimizing the pipeline" often comes down to data layout: ensuring contiguous access, minimizing pointer chasing, reducing working sets, and avoiding false sharing.

8. Precise Exceptions Preserve a Defined Program Boundary

Even in a simple pipeline where multiple instructions are in flight simultaneously, the architecture must present clear and understandable boundaries. If a load instruction encounters a page fault:

• All instructions that precede it should appear as having completed;
• For this single load, the faulting and younger instructions leave no irreversible destination-register or ordinary-memory results;
• After exception handling completes, execution should either resume from the correct point or terminate cleanly.

ISA-defined exception records, page-table accessed bits, and restartable compound instructions may have their own partial-progress rules. A fault does not imply that nothing changed. An in-order pipeline preserves the required boundary by controlling writes at each stage. In contrast, out-of-order CPUs require more explicit retirement and commit mechanisms. The next section introduces how a reorder buffer maintains precise exception handling.

9. Analyze a Dependency Problem

Given:

add x5, x1, x2
lw  x6, 0(x5)
xor x7, x6, x3
add x8, x4, x9

The dependencies can be sequentially annotated as follows:

1. lw depends on add's x5, which is a RAW (read-after-write) dependency; ALU forwarding may resolve this.
2. xor depends on lw's x6, which is a load-use RAW dependency that requires a stall in the classic five-stage pipeline.
3. The final instruction add is independent of the first three and can be scheduled ahead of the waiting instructions in more advanced schedulers.
4. Assembly code alone cannot determine how many cycles the real CPU actually stalls; microarchitecture details and cache state must also be considered.

The correct analysis language is "what dependencies allow," not memorizing a fixed cycle count for every processor.

10. Summary

A pipeline improves throughput by overlapping the execution stages of different instructions:

• The five-stage RISC model separates instruction fetch, decode, execute, memory access, and write-back;
• Structural hazards occur when resources are contested, data hazards arise from dependencies, and control hazards result from uncertainty in the next program counter;
• Forwarding shortens the path for result propagation, but cannot eliminate all wait states for load-use dependencies;
• Multiple independent accumulators expose greater instruction-level parallelism;
• Cache misses, memory dependencies, and data layout often matter more than the ideal five-stage timeline;
• volatile is not a universal switch for thread synchronization or hardware ordering.

The next section, Branch Prediction, Superscalar, and Out-of-Order Execution, explores how modern CPUs achieve substantial internal out-of-order execution while preserving the expected sequential behavior of the architecture.

Check the Implementation and Compiler Documentation

• GCC volatile semantics