Pipelining Fundamentals

TL;DR

Pipelining is a CPU design technique that breaks down instruction execution into smaller, sequential stages to allow multiple instructions to be processed concurrently. This overlap dramatically increases the CPU's throughput, meaning it completes more instructions per unit of time, even though individual instruction latency might not decrease. However, dependencies and resource conflicts can cause "hazards" that disrupt this smooth flow, requiring careful handling to maintain performance gains.

1. The Mental Model

Imagine a car wash with multiple stations: vacuuming, washing, rinsing, drying. Instead of waiting for one car to finish all four steps before starting the next, you can have four different cars at each station simultaneously. Pipelining applies this "assembly line" idea to CPU instructions, processing different parts of multiple instructions at the same time.

2. The Core Material

Traditionally, a CPU executes one instruction completely before starting the next. Pipelining breaks down the instruction execution into several stages, similar to our car wash example. A common five-stage pipeline looks like this:

• IF (Instruction Fetch): Get the next instruction from memory.
• ID (Instruction Decode): Decode the instruction and fetch any required operands (data) from registers.
• EX (Execute): Perform the arithmetic or logical operation specified by the instruction.
• MEM (Memory Access): Access data memory if the instruction requires a read or write.
• WB (Write Back): Write the result of the operation back to a register.

By having these stages, different instructions can be in different stages concurrently. For example, while instruction 1 is in the EX stage, instruction 2 can be in ID, instruction 3 in IF, and so on.

Here's how a typical pipeline works over time, showing the stages for three instructions (I1, I2, I3):

graph TD
    subgraph Cycle 1
        IF1["I1: Fetch"]
    end
    subgraph Cycle 2
        ID1["I1: Decode"]
        IF2["I2: Fetch"]
    end
    subgraph Cycle 3
        EX1["I1: Execute"]
        ID2["I2: Decode"]
        IF3["I3: Fetch"]
    end
    subgraph Cycle 4
        MEM1["I1: Memory"]
        EX2["I2: Execute"]
        ID3["I3: Decode"]
    end
    subgraph Cycle 5
        WB1["I1: Write Back"]
        MEM2["I2: Memory"]
        EX3["I3: Execute"]
    end
    subgraph Cycle 6
        WB2["I2: Write Back"]
        MEM3["I3: Memory"]
    end
    subgraph Cycle 7
        WB3["I3: Write Back"]
    end

Notice how after the initial "fill-up" of the pipeline, an instruction completes nearly every clock cycle. This is the ideal scenario, leading to a theoretical Cycles Per Instruction (CPI) of 1, meaning one instruction is completed per clock cycle.

Hazards in Pipelining

Photo by Sonny Vermeer on Pexels

The smooth flow can be disrupted by hazards. These are situations that prevent the next instruction in the instruction stream from executing in its designated clock cycle. There are three main types:

1. Structural Hazards: Occur when two instructions need the same hardware resource at the same time. For instance, if the CPU only has one memory unit and both an IF stage (fetching instruction) and a MEM stage (fetching data) need to access memory in the same cycle. This can be solved by duplicating resources (e.g., separate instruction and data caches) or by stalling one instruction.

2. Data Hazards: Occur when an instruction depends on the result of a previous instruction that hasn't yet written its result back.

   • RAW (Read After Write): The most common. Instruction 2 tries to read a register that Instruction 1 is about to write to. Example:
     ADD R1, R2, R3 (R1 = R2 + R3)
     SUB R4, R1, R5 (R4 = R1 - R5)
     Here, SUB needs the value of R1 that ADD computes. If SUB reads R1 too early, it gets the old value. Solutions include stalling (pausing SUB until ADD writes R1) or forwarding/bypassing (sending the result from ADD's EX or MEM stage directly to SUB's EX stage, without waiting for WB).

3. Control Hazards (Branch Hazards): Occur with branch instructions (like if statements or loops). When a branch instruction is fetched, the CPU doesn't immediately know which instruction to fetch next (the target of the branch or the instruction immediately following the branch). If the pipeline fetches instructions speculatively down the "wrong" path, those instructions need to be flushed if the branch prediction was incorrect, causing a performance penalty. Solutions involve branch prediction (guessing which way the branch will go) and delayed branches (executing instructions immediately after the branch even if the branch is taken).

3. Worked Example

Let's look at a data hazard and how forwarding helps.

Consider these two instructions:
1. ADD R1, R2, R3 (R1 = R2 + R3)
2. SUB R4, R1, R5 (R4 = R1 - R5)

Without forwarding, the pipeline stages would look like this (assuming a 5-stage pipeline, and we're only interested in the interaction between I1 and I2 for R1):

• Cycle 1: I1 fetches (IF)
• Cycle 2: I1 decodes (ID), I2 fetches (IF)
• Cycle 3: I1 executes (EX) -> R1 is computed. I2 decodes (ID) -> I2 tries to read R1 here. The value R1 needs isn't available until I1's WB stage (Cycle 5).
  • This is where a stall would occur. I2's ID stage would wait.
• Cycle 4: I1 accesses memory (MEM). I2 stalls.
• Cycle 5: I1 writes back (WB) -> R1 is finally updated in the register file. I2 stalls.
• Cycle 6: I2 can now proceed to execute (EX) using the correct R1 value.

This scenario introduces two stall cycles, slowing down the pipeline.

With Forwarding:
Forwarding (also called bypassing) means that the result from I1's EX stage (where R1 is computed) is immediately "forwarded" or "bypassed" to I2's EX stage, without waiting for it to be written back to the register file.

• Cycle 1: I1 fetches (IF)
• Cycle 2: I1 decodes (ID), I2 fetches (IF)
• Cycle 3: I1 executes (EX) -> R1 is computed. I2 decodes (ID).
  • Now, the computed R1 from I1's EX stage is forwarded directly to I2's EX stage for the next cycle.
• Cycle 4: I1 accesses memory (MEM). I2 executes (EX) using the forwarded R1 value from I1's EX stage from the previous cycle.
• Cycle 5: I1 writes back (WB). I2 accesses memory (MEM).
• Cycle 6: I2 writes back (WB).

Forwarding eliminates the stalls, allowing I2 to proceed without delay by getting the data as soon as it's available in the pipeline.

4. Key Takeaways

• Pipelining breaks instruction execution into stages to process multiple instructions concurrently.
• The goal is to increase throughput by completing an instruction every clock cycle after the pipeline fills up.
• A common pipeline has stages: Instruction Fetch (IF), Instruction Decode (ID), Execute (EX), Memory Access (MEM), Write Back (WB).
• Hazards (structural, data, control) disrupt the pipeline's smooth flow, reducing performance.
• Structural hazards arise from resource conflicts, often solved by duplicating hardware.
• Data hazards occur when an instruction needs data from an instruction not yet completed.
• Forwarding (bypassing) is a key technique to mitigate data hazards by delivering results directly between pipeline stages.
• Control hazards are caused by branch instructions and are tackled with branch prediction and delayed branches.

Common mistakes to avoid:
- Confusing increased throughput (more instructions per second) with decreased latency (faster individual instruction execution). Pipelining primarily improves throughput.
- Assuming pipelines magically eliminate all dependencies; hazards still need careful architectural handling.
- Thinking stalling is the only solution for hazards; forwarding and prediction are often more efficient.
- Underestimating the complexity of implementing forwarding or accurate branch prediction.

5. Now Try It

Draw a simple 3-stage pipeline (Fetch, Execute, Write Back) and trace the execution of the following two instructions:
LOAD R1, 100(R2) (Load value from memory address R2+100 into R1)
ADD R3, R1, R4 (R3 = R1 + R4)

Assume no forwarding is available, and an instruction needs its operands available at the start of its Execute stage. Identify any stalls. What would success look like? You should clearly show which instruction is in which stage for each clock cycle and mark where any stalls occur and why.