Hazard Identification and Resolution in Pipelines

The Three Types of Pipeline Hazards

A pipeline hazard is any condition that prevents the next instruction in the instruction stream from executing during its designated clock cycle. There are three main types:

1. Structural Hazards: These occur when two or more instructions need the same hardware resource at the same time. For example, if a processor's memory unit has only one port, it can't handle an instruction fetch (IF stage) and a data access (MEM stage) in the same clock cycle. The solution is usually to add more hardware (e.g., separate instruction and data caches), which is a design decision. For GATE, you mainly need to know the definition, as data and control hazards are far more common in questions.

2. Data Hazards: These arise when an instruction depends on the result of a previous instruction that is still in the pipeline and has not yet completed.

3. Control Hazards: These are caused by branch and jump instructions that change the flow of program execution, making the instructions already fetched into the pipeline potentially incorrect.

We will now focus on data and control hazards, as they are central to your syllabus and require specific techniques to handle.

Data Hazards: The Problem of Dependencies

Data hazards occur because the overlapped execution in a pipeline can reorder the read and write operations of operands compared to the sequential order intended by the program. Let's delve into the specifics.

As the video explains, the core issue is that an instruction might need a value that hasn't been written to the register file yet. This leads to three distinct types of data dependencies, often referred to by their acronyms.

1. Read After Write (RAW) or True Dependency

This is the most common and intuitive type of data hazard. It occurs when an instruction tries to read an operand before a preceding instruction has written to it.

• Example:

  I1: ADD R1, R2, R3  ; R1 <- R2 + R3
  I2: SUB R4, R1, R5  ; R4 <- R1 - R5
  

  Here, I2 needs the value of R1 that I1 produces. In a 5-stage pipeline, I2 will try to read R1 in its ID stage (cycle 3), but I1 only writes the new value of R1 back in its WB stage (cycle 5). I2 would incorrectly read the old value of R1.

Solution 1: Stalling
The simplest solution is to make I2 wait. We can insert "bubbles" or NOP (No-Operation) cycles into the pipeline until I1's result is written to the register file.

A RAW hazard causing two stall cycles. Instruction I2 is frozen in the ID stage until I1 completes its WB stage, allowing the correct value of R1 to be read.

This works, but it defeats the purpose of pipelining by reducing throughput. For every such dependency, we lose performance.

Solution 2: Operand Forwarding (or Bypassing)
A much better solution is to not wait for the WB stage. The result of the ADD operation is available at the end of the EX stage in the EX/MEM pipeline register. We can add special hardware paths to forward this result directly to the input of the ALU for the SUB instruction, bypassing the register file entirely.

Forwarding paths from the output of the EX and MEM stages back to the ALU inputs. This allows results to be used by subsequent instructions before they are formally written back to the register file.

Let's see how this elegant solution works in practice.

An Important Exception: The Load-Use Hazard
Forwarding works perfectly for ALU-to-ALU dependencies. However, there's a special case it can't fully solve: a dependency on a LOAD instruction.

• Example:

  I1: LW R1, 0(R2)    ; R1 <- Memory[R2+0]
  I2: ADD R3, R1, R4  ; R3 <- R1 + R4
  

The data being loaded by LW is only available at the end of the MEM stage. Forwarding can send this value from the MEM/WB pipeline register to the ADD instruction's EX stage. However, the ADD instruction is already one stage ahead. It needs the value at the beginning of its EX stage, but the LW instruction provides it at the end of its MEM stage. This timing mismatch forces a one-cycle stall.

This "load-use hazard" is a classic concept and a frequent source of questions. Even with full forwarding, a load followed immediately by an instruction that uses its result will incur one stall cycle.

2. Write After Read (WAR) or Anti-Dependency

This happens when an instruction tries to write to a location that a preceding instruction is supposed to read.

• Example:

  I1: SUB R4, R1, R5  ; Read R1
  I2: ADD R1, R2, R3  ; Write R1
  

The danger is that I2 might write its new value into R1 before I1 has had a chance to read the old value. In a simple 5-stage pipeline, this is not a problem because reads occur early (ID stage) and writes occur late (WB stage). However, this can become a real issue in more complex, out-of-order processors. The main solution is a technique called register renaming.

3. Write After Write (WAW) or Output Dependency

This occurs when two instructions in the pipeline are set to write to the same destination.

• Example:

  I1: ADD R1, R2, R3  ; Write R1
  I2: SUB R1, R4, R5  ; Write R1
  

The pipeline must ensure that I2 writes its result after I1, preserving the program's intended final state for R1. In a simple in-order pipeline, this is naturally handled because instructions reach the WB stage in order. This becomes a significant hazard in architectures where instructions can complete out of order.

This formal way of thinking is exactly what you need to quickly and accurately analyze code segments in the exam.

Control Hazards: The Problem of Branches

Control hazards arise from instructions that change the program counter (PC), such as branches and jumps. The pipeline is designed to fetch instructions sequentially (PC, PC+4, PC+8, ...). When a branch instruction enters the pipeline, the processor doesn't know whether the branch will be taken or not until later (typically in the EX or ID stage). By that time, it has already fetched several instructions from the wrong path if the branch ends up being taken.

Calculating the Branch Penalty
The number of cycles wasted due to a flushed instruction is called the branch penalty. As the video explains, if the branch outcome is determined in stage k of the pipeline, then k-1 instructions that were fetched incorrectly must be flushed.

Solutions to Control Hazards

1. Stall the Pipeline: The simplest method is to freeze the pipeline as soon as a branch is decoded, wait until its outcome is known in the EX stage, and then resume fetching from the correct address. This is safe but slow, as it introduces a fixed penalty for every branch.

2. Branch Prediction: A more intelligent approach is to guess the outcome of the branch and speculatively fetch instructions from the predicted path.

   • Static Prediction: Use a simple rule, e.g., "always predict branch not taken" or "predict backward branches as taken (for loops)". If the prediction is correct, there is no penalty! If it's wrong, the pipeline is flushed, and we incur the full branch penalty.
   • Dynamic Prediction: The processor keeps a small history table (Branch History Table) to track the recent behavior of branches. A 1-bit predictor remembers the last outcome (Taken/Not-Taken). A 2-bit saturating counter is more robust, as it requires two consecutive wrong predictions to change its primary guess (e.g., from "Strongly Taken" to "Weakly Taken" to "Weakly Not Taken" to "Strongly Not Taken").

3. Delayed Branch: This is a classic RISC technique you'll see in GATE questions. The compiler finds an instruction that can be executed after the branch, regardless of its outcome, and places it in the branch delay slot. The processor always executes the instruction in the delay slot. This effectively hides one cycle of the branch penalty. For a branch penalty of 2, a single delay slot reduces the effective penalty to 1.

Conclusion

In this lesson, we moved from the ideal world of pipelining to the practical realities of processor design. We meticulously examined the hazards that threaten to stall our instruction assembly line and the powerful techniques used to mitigate them.

Key Takeaways:

• Pipeline Hazards are conditions that disrupt the smooth flow of instructions. They are primarily categorized as Structural, Data, and Control hazards.
• Data Hazards involve dependencies on operands.
  • RAW (Read After Write) is the most common, solved efficiently by Operand Forwarding. A load-use hazard is a special case that still requires a 1-cycle stall.
  • WAR (Write After Read) and WAW (Write After Write) are anti- and output-dependencies, which are less problematic in simple in-order pipelines but are handled by techniques like register renaming in advanced processors.
• Control Hazards are caused by branches. The penalty for a mispredicted branch is typically the stage number where the branch is resolved minus one.
• Solutions for control hazards include stalling, branch prediction (static and dynamic), and the delayed branch technique, which uses a compiler-filled branch delay slot.

You are now equipped to analyze code segments, identify potential pipeline stalls, and understand how architectural solutions improve performance. This foundation is not just crucial for GATE but for understanding any modern high-performance processor.

In our next lesson, we will address another major performance bottleneck: memory. Even with a perfectly optimized pipeline free of hazards, its speed is ultimately limited by how fast it can fetch instructions and data. We will explore the memory hierarchy and cache, the system that bridges the speed gap between the fast processor and slow main memory.