Pipelining

Pipelining is a technique used in modern processors to increase instruction throughput by overlapping the execution of multiple instructions. Instead of completing one instruction fully before starting the next, pipelining divides instruction execution into stages and processes different instructions simultaneously at different stages, much like an assembly line in a factory.

This topic is highly important for GATE as it covers pipeline stages, throughput calculations, pipeline hazards, and superscalar architectures. Questions on pipeline speedup, CPI (Cycles Per Instruction), and hazard resolution are frequently asked.

Core Concept: Why Pipelining Works

In a non-pipelined processor, each instruction must pass through all stages before the next instruction begins. For a 5-stage pipeline (IF, ID, EX, MEM, WB), executing N instructions takes N x 5 clock cycles. In a pipelined processor, once the pipeline is full, one instruction completes every single clock cycle. This is possible because each stage operates independently on a different instruction simultaneously.

The time to complete N instructions in a k-stage pipeline is k + (N-1) cycles, where k is the fill time for the pipeline and (N-1) represents the remaining instructions completing one per cycle. The theoretical speedup of a k-stage pipeline over a non-pipelined processor is k, meaning a 5-stage pipeline can ideally execute 5 times faster. In practice, speedup is reduced by hazards and stalls.

Pipeline Hazards

A pipeline hazard is any condition that prevents the next instruction from executing in the next clock cycle. There are three types of hazards. Structural hazards occur when two instructions need the same hardware resource at the same time, for example, both needing memory access in the same cycle. The solution is to use separate instruction and data caches or to add duplicate units.

Data hazards occur when an instruction depends on the result of a previous instruction that has not yet completed. For example, instruction I2 reads register R1 which instruction I1 is still computing. This creates a Read After Write (RAW) hazard. The solution is data forwarding (operand bypassing) where the result from the EX stage is forwarded directly to the input of the EX stage for the next instruction without waiting for WB.

Control hazards occur due to branch instructions. When a branch is fetched, the next instruction address is unknown until the branch is resolved in the EX or MEM stage. The pipeline may have already fetched 2 to 3 wrong instructions. Solutions include branch prediction, delayed branching, and flushing the pipeline on a misprediction.

Mathematical Expression

The pipeline speedup formula compares the time taken without pipelining to the time taken with pipelining. Without pipeline: T = N x k x t, where N = instructions, k = stages, t = time per stage. With pipeline: T = (k + N - 1) x t. Speedup = Nk / (k + N - 1). For large N, speedup approaches k. When stalls are added, the effective CPI = 1 + average stall cycles per instruction.

Given:
Number of instructions N = 100
Number of pipeline stages k = 5
Clock cycle time t = 2 ns
Data hazard stalls = 0.1 stalls per instruction on average

Why this formula applies:
Pipeline completes in k + (N-1) cycles ideally; stalls add extra cycles.

Formula:
Ideal cycles = k + (N-1)
Actual cycles = k + (N-1) + (N x average_stalls)
Actual CPI = 1 + average_stalls

Substitution:
Ideal cycles = 5 + 99 = 104
Actual cycles = 104 + (100 x 0.1) = 104 + 10 = 114

Calculation:
Ideal time = 104 x 2 ns = 208 ns
Actual time = 114 x 2 ns = 228 ns
Actual CPI = 1 + 0.1 = 1.1

Final Answer: Actual execution time = 228 ns with CPI = 1.1 (10% overhead from stalls).

Exam Tip: For GATE, the pipeline speedup formula is Speedup = Nk / (k + N - 1). For large N, speedup approaches k. When stalls are present, CPI = 1 + stall_cycles_per_instruction, not just 1.

• Pipeline divides instruction execution into k stages; at steady state one instruction completes per cycle.
• Time with pipeline = (k + N - 1) cycles; speedup approaches k for large N.
• Structural hazard: resource conflict; solved by duplicating hardware or stalling.
• Data hazard (RAW): register dependency; solved by data forwarding or inserting NOP.
• Control hazard: branch uncertainty; solved by branch prediction or delayed branching.
• Superscalar: multiple pipelines, IPC greater than 1, used in Pentium and modern CPUs.

Quick Revision

• 5 stages: IF (Fetch), ID (Decode), EX (Execute), MEM (Memory), WB (Write Back).
• Ideal pipeline: CPI = 1 at steady state. With stalls: CPI = 1 + average stall cycles.
• Speedup = Nk / (k + N - 1); for large N this approaches k.
• Three hazard types: structural, data (RAW/WAR/WAW), and control.
• Data forwarding reduces RAW stalls by routing EX output back to EX input.
• Superscalar issues more than one instruction per cycle giving IPC greater than 1.
• Exam trap: Speedup equals k only for infinite N. For finite N, always use the full formula.