Pipelining Questions

Introduction

Pipelining questions are among the most frequently asked in computer architecture exams, GATE papers, and technical interviews. They test your ability to trace instruction execution through pipeline stages, identify hazards, apply forwarding, and calculate performance metrics. This page covers the most important question types with step-by-step solutions. Master these patterns, and you will handle any pipeline question thrown at you.

Question Type 1: Basic Pipeline Timing

Q1: Calculate execution time and speedup

Problem: A non-pipelined processor takes 50 ns per instruction (5 stages × 10 ns each). The pipelined version has 5 stages with 12 ns clock cycle (10 ns + 2 ns overhead). Calculate time for 100 instructions and speedup.

Solution:

Note: Ideal speedup would be 5× (number of stages). The 2 ns register overhead and pipeline fill time reduce it slightly.

Q2: Unbalanced pipeline stages

Problem: A 4-stage pipeline has stage delays: 15 ns, 10 ns, 12 ns, 8 ns. Pipeline register delay is 1 ns. What is the clock cycle time? What would be ideal if stages were balanced?

Solution:

This shows why pipeline stage balancing matters — the slowest stage determines clock speed for the entire pipeline.

Question Type 2: Hazard Detection

Q3: Identify all hazards

Problem: Identify hazards in this instruction sequence for a 5-stage pipeline:

Solution:

RAW (Read After Write) Hazards:

• I1 → I2: R1 (I1 writes R1, I2 reads R1) — EX-EX forwarding resolves
• I1 → I3: R1 (I1 writes R1, I3 reads R1) — MEM-EX forwarding resolves
• I3 → I4: R6 (I3 loads R6, I4 reads R6) — Load-use hazard! 1 stall required
• I3 → I5: R6 (I3 loads R6, I5 reads R6) — MEM-EX forwarding resolves (after stall for I4)

No WAR or WAW hazards in this in-order pipeline.

Q4: Pipeline diagram with stalls

Problem: Draw the pipeline timing diagram for Q3's instructions with forwarding.

Solution:

██ = stall/bubble

Total: 10 cycles for 5 instructions. CPI = 10/5 = 2.0 (ideal would be 9/5 = 1.8 without load-use).

Question Type 3: Forwarding Path Identification

Q5: Which forwarding paths are active?

Problem: For each dependent pair in the sequence below, identify the forwarding path used:

Solution:

Question Type 4: Branch Prediction

Q6: 2-bit predictor state transitions

Problem: A 2-bit saturating counter starts at state "Weakly Taken" (10). The actual branch outcomes are: T, T, NT, NT, T, NT, T, T. Show state after each branch and count mispredictions.

Solution:

This irregular pattern is hard for any predictor. Real branch patterns (loops) are much more predictable.

Question Type 5: Performance with Hazards

Q7: Calculate effective CPI

Problem: In a processor's instruction mix: 25% are loads (40% of which are followed by dependent instructions causing 1 stall each), 15% are branches (branch penalty = 2 cycles, predictor accuracy = 85%). Calculate effective CPI.

Solution:

Q8: Impact of deeper pipeline

Problem: Compare a 5-stage pipeline (branch penalty = 2) with a 12-stage pipeline (branch penalty = 7). Branch frequency = 20%, prediction accuracy = 90%.

Solution:

The deeper pipeline is faster overall despite higher branch penalty because the clock is much faster.

Question Type 6: Structural Hazards

Q9: Unified memory structural hazard

Problem: A pipeline has unified instruction/data memory (single port). When a LOAD/STORE is in MEM stage, no instruction can be fetched. What is the CPI if 30% of instructions are loads/stores?

Solution:

Question Type 7: Pipeline Scheduling

Q10: Reorder instructions to minimize stalls

Problem: Schedule these instructions to eliminate stalls (with forwarding):

Solution:

This is exactly what optimizing compilers do — instruction scheduling fills load delay slots with independent instructions.

Common Mistakes to Avoid

1. Forgetting pipeline fill time: Total time = (k + n - 1) × cycle, not just n × cycle
2. Wrong forwarding path: EX-EX forwarding serves the immediately next instruction, MEM-EX serves two instructions later
3. Assuming loads have no penalty with forwarding: Load-use ALWAYS costs 1 stall even with full forwarding
4. Miscounting branch penalty: Penalty = cycles wasted = number of instructions flushed
5. Ignoring register 0: In MIPS, writes to $0 are discarded — no forwarding needed from R0
6. Confusing CPI components: Each hazard type contributes independently to CPI; add them all up

Key Takeaways

1. Pipeline performance = ideal CPI (1) + stalls from all hazard sources
2. Data hazards: solved by forwarding (except load-use which needs 1 stall)
3. Control hazards: penalty = misprediction_rate × pipeline_stages_wasted × branch_frequency
4. Deeper pipelines give faster clock but higher hazard penalties — there is an optimal depth
5. Compiler scheduling can eliminate many stalls by reordering independent instructions
6. Always draw the timing diagram — visual representation prevents calculation errors