RISC Pipeline: Hazards and Solutions

The Classic RISC Pipeline

A simple, non-pipelined processor executes one instruction to completion before starting the next. This is inefficient because most of the CPU's hardware sits idle, waiting for the current step to finish. Pipelining is the solution. It's an assembly-line approach where instruction execution is broken down into a series of smaller, independent steps or stages. This allows the processor to overlap the execution of multiple instructions, dramatically increasing instruction throughput (the rate at which instructions are completed).

The classic RISC architecture, which influenced designs like MIPS, SPARC, and early ARM cores, uses a five-stage pipeline.

In an ideal world, this pipeline would complete one instruction every single clock cycle, achieving an Instructions Per Cycle (IPC) of 1. However, the real world is more complicated. The dependencies between instructions create problems called hazards, which prevent the pipeline from always achieving its maximum throughput.

What are Pipeline Hazards?

A pipeline hazard is any condition that forces the pipeline to stall or deviate from its normal one-cycle-per-stage flow, potentially leading to incorrect execution if not handled. These are broadly categorized into three types.

Now, let's dissect each of these hazard types and their solutions.

1. Structural Hazards

A structural hazard occurs when two or more instructions in the pipeline need the same piece of hardware at the same time.

As the video shows, the classic example is a processor with a single, unified memory for both instructions and data. An instruction in the MEM stage (doing a load/store) would conflict with an instruction in the IF stage (fetching the next instruction).

Solution:
Structural hazards are almost always resolved at design time by providing sufficient hardware resources.

• For the memory conflict, the solution is to use separate instruction and data caches (or memories), a concept known as a Harvard architecture.
• If an ALU were needed for both branch target calculation in the ID stage and arithmetic in the EX stage, designers would add a dedicated adder for branch calculations.

Because they are solved by hardware design, you are less likely to be asked about dynamically handling structural hazards in an interview. The focus is almost always on data and control hazards.

2. Data Hazards

Data hazards are the most common type of hazard. They occur when an instruction's execution depends on the result of a previous instruction that is still moving through the pipeline. The most prevalent type is the Read-After-Write (RAW) hazard.

Consider this code sequence:

// r1 = r2 + r3
ADD r1, r2, r3

// r4 = r1 - r5 (depends on the new value of r1)
SUB r4, r1, r5

The SUB instruction needs the new value of r1 at the start of its EX stage. However, in a simple pipeline, the ADD instruction only writes this new value back to the register file in its WB stage, which is two cycles later. The SUB would read the old, stale value of r1 and compute an incorrect result.

Solution 1: Stalling (Pipeline Bubbles)

The simplest way to solve this is to stall the pipeline. The hardware can detect the dependency and insert nop (no-operation) instructions, often called bubbles, into the pipeline. This freezes the dependent instruction (and all those behind it) until the required data has been written to the register file.

Stalling is effective, but it hurts performance by reducing the pipeline's throughput. Every bubble is a lost opportunity to complete an instruction.

Solution 2: Forwarding (Bypassing)

A much more efficient solution is forwarding, also known as bypassing. The key insight is that the result of the ADD instruction is actually available at the output of the ALU at the end of its EX stage. We don't have to wait for it to be written to the register file in the WB stage.

With forwarding, the hardware adds data paths to send a result directly from the output of one pipeline stage (like EX or MEM) back to the input of an earlier stage (like EX).

Forwarding resolves most RAW hazards without any stalls, allowing the pipeline to maintain its full throughput.

The Load-Use Hazard: A Special Case

There is one critical RAW hazard that forwarding alone cannot solve: the load-use hazard. This occurs when an instruction immediately uses a value loaded from memory by the preceding instruction.

// Load value from memory into r1
LD r1, 0(r2)

// Use r1 immediately
ADD r3, r1, r4

Here's the problem:

• The LD instruction gets the data from memory at the end of the MEM stage (cycle 4).
• The ADD instruction needs this data at the beginning of its EX stage (cycle 3).

The data isn't available yet. Forwarding it from the MEM stage output to the EX stage input would require the data to go "backwards in time," which is impossible.

Solution: The solution is a stall-plus-forward combination. The pipeline must stall for exactly one cycle. This pushes the ADD instruction's EX stage to cycle 4, just in time to receive the forwarded data from the LD instruction's MEM stage.

This one-cycle stall after a load is a common and important performance characteristic of RISC pipelines.

3. Control Hazards

Control hazards arise from branch and jump instructions. The processor doesn't know for sure whether a branch will be taken or not until the instruction is evaluated, typically in the EX stage. By that time, the processor has already fetched several subsequent instructions along the default path (PC+4). If the branch is taken, these fetched instructions are incorrect and must be discarded.

Solution 1: Stall

The naive solution is to freeze the pipeline as soon as a branch is decoded, waiting until the branch is resolved. This guarantees correctness but introduces a significant performance penalty on every branch, which is unacceptable for loop-heavy code.

Solution 2: Branch Prediction and Pipeline Flush

A better approach is to predict the outcome of the branch and speculatively execute down the predicted path.

• Predict Not-Taken: A simple strategy is to always assume the branch is not taken and continue fetching instructions sequentially.
• If the prediction is correct (the branch is not taken), no cycles are wasted.
• If the prediction is incorrect (the branch is taken), the processor must flush the pipeline. This means invalidating all the speculatively fetched instructions and restarting the fetch process from the correct branch target address.

While there's a penalty for a misprediction (equal to the number of pipeline stages filled with wrong-path instructions), it's often much better than always stalling, because many branches are predicted correctly.

Mention for Interviews: Branch Delay Slot

Early RISC ISAs (like MIPS and SPARC) used an architectural solution called the branch delay slot. The instruction immediately following the branch is always executed, regardless of the branch outcome. It was the compiler's job to fill this slot with a useful instruction that was independent of the branch. This technique has largely been abandoned in favor of the more flexible and powerful dynamic branch prediction used in modern superscalar processors, but it's an important historical concept to be aware of.

Conclusion

In this lesson, we deconstructed the classic RISC pipeline and the hazards that disrupt its flow. Understanding these concepts is fundamental to appreciating why CPU performance isn't just about clock speed, but also about how efficiently the pipeline is kept full and executing useful work.

Key Takeaways:

• Pipelining improves instruction throughput by overlapping the execution of multiple instructions in stages (IF, ID, EX, MEM, WB).
• Hazards are situations that prevent the ideal flow and can cause incorrect execution if not handled.
• Structural Hazards are resource conflicts solved by hardware design (e.g., separate I/D caches).
• Data Hazards (RAW) are solved primarily by forwarding results directly between pipeline stages. The exception is the load-use hazard, which requires a one-cycle stall.
• Control Hazards from branches are solved by branch prediction and flushing the pipeline on a misprediction, which is more efficient than always stalling.

Preview of the Next Lesson:
We've seen that branch prediction is the key to mitigating control hazards. In our next lesson, we will dive deeper into this topic. We'll compare different static vs. dynamic branch prediction strategies and analyze their effectiveness in keeping the pipeline fed with the correct instructions.