Pipelining Concepts, Pipelined Data Path, and Hazard Handling

What is Pipelining? (In Simple Words)

In a normal, non-pipelined CPU, an instruction must finish completely before the next instruction can even begin.

Pipelining is a smart technique where multiple instructions overlap during execution, exactly like an industrial assembly line.

• While Instruction 1 is executing math in the ALU,
• Instruction 2 is fetching its data numbers from memory,
• And Instruction 3 is being decoded at the exact same time!

💡 Real-Life Indian Student Analogy:
Think of washing clothes at your hostel: (1) Washing, (2) Drying, (3) Ironing.

• Without Pipeline: You wash Load 1, dry Load 1, iron Load 1. Only then do you start Load 2 (Takes 3 hours per bucket!).
• With Pipeline: As soon as Load 1 moves into the dryer, you put Load 2 into the washing machine! The machines never sit empty. Your work gets done 3 times faster!

1. 4-Stage Instruction Pipeline

A standard CPU instruction pipeline is divided into 4 sequential hardware stages:

Space-Time Diagram (4 Instructions across Clock Cycles):

Notice what happens at Cycle 4: the pipeline is completely full, and one finished instruction exits the CPU on every single clock cycle!

2. Speedup (S) of Pipelining

Let:

• k = Number of stages in the pipeline (e.g. 4 stages).
• n = Total instructions to execute (e.g. 1,000 instructions).
• τ = Clock cycle time.

The Formulas:

1. Time without Pipeline (tₙ):
   tₙ = n × k × τ
2. Time with Pipeline (tₚ):
   tₚ = (k + n - 1) × τ
3. Speedup Ratio (S):
   S = tₙ / tₚ = (n × k) / (k + n - 1)

📌 Maximum Theoretical Speedup:
When executing a large program (n is very big), the formula simplifies to:
S ≈ k
This means a 4-stage pipeline makes your processor up to 4 times faster!

3. Pipeline Hazards and How to Fix Them

In real computer hardware, situations arise that pause or break the smooth flow of the pipeline. These roadblocks are called Pipeline Hazards (or stalls/bubbles).

A. Data Hazards (Data Dependency)

Happens when Instruction 2 needs a value produced by Instruction 1:

I1: ADD R1, R2, R3    ; Calculates R1 in EX stage (Cycle 4)
I2: SUB R4, R1, R5    ; Tries to read R1 in FO stage (Cycle 3)!

• Here I₂ tries to read R₁ before I₁ has even finished writing it (Read After Write - RAW conflict).

Solutions:

1. Stalling (Pipeline Bubbles): The hardware pauses I₂ for 2 cycles until R₁ is ready.
2. Data Forwarding (Bypassing): A special internal wire routes the calculated answer directly from the ALU output of I₁ straight into the ALU input of I₂ without waiting for registers!

B. Control Hazards (Branch / Jump Hazards)

When a program hits an if-else or loop jump (JMP target), the CPU does not know which path the code will take until the condition is evaluated. If it fetched the wrong branch, the pipeline must be emptied (Pipeline Flush), wasting clock cycles.

Solutions:

1. Branch Prediction:
   • The CPU guesses the most likely path.
   • For example: Loop jumps backward are usually taken 90% of the time.
2. Delayed Branch:
   • The compiler puts a useful instruction right after the branch so no cycle is wasted.

💡 DAVV Exam Preparation Tips

5-Mark Question: “What is pipelining? Derive the formula for speedup ratio S of a k-stage pipeline executing n tasks.”

• Define pipelining with the assembly line laundry analogy.
• State the formulas clearly:
  • tₙ = n × k × τ (Non-pipelined time)
  • tₚ = (k + n - 1) × τ (Pipelined time)
  • S = (n × k) / (k + n - 1) (Speedup ratio)
• Conclude that as n → ∞, maximum speedup S = k.

10-Mark Question: “Explain the 4-stage instruction pipeline. What are pipeline hazards? Explain Structural, Data, and Control hazards along with their mitigation strategies (Data Forwarding and Branch Prediction).”

• Draw the 4-stage space-time chart across 7 clock cycles (FI, DA, FO, EX).
• Explain the 3 hazards:
  • Structural (resource conflict)
  • Data (RAW conflict)
  • Control (branch jumps)
• Explain Data Forwarding (passing values directly from ALU to ALU).
• Explain Branch Prediction (guessing whether a jump is taken).