Chapter 34 of 39

Pipelining Basics

Every processor you use today is pipelined. Pipelining is the single most important idea for making a CPU fast without making any individual circuit faster. It does not speed up any one instruction; instead it lets the CPU work on several instructions at the same time, each at a different step, like an assembly line.

In this chapter we build the idea from a simple analogy, define stages, clock cycle, latency and throughput, derive the speedup, efficiency and throughput formulas, and solve the standard GATE-style numericals: uniform and non-uniform stages, latch overhead, splitting a slow stage, and comparing pipelined with non-pipelined processors. Real pipelines also run into problems called hazards; those are the subject of the next chapter, Pipeline Hazards. Here we assume the ideal case where instructions never get in each other's way.


The Intuition: Washing Clothes

Suppose doing a load of laundry has four steps: wash (30 min), dry (30 min), fold (30 min), put away (30 min). You have four loads.

  • Sequentially: finish load 1 completely, then start load 2. Four loads take 4 x 120 = 480 minutes.

  • Pipelined: as soon as load 1 moves from the washer to the dryer, put load 2 in the washer. Every 30 minutes one load finishes. Four loads take 120 + 3 x 30 = 210 minutes.

Notice two things. Each individual load still takes 120 minutes (latency is unchanged). But the rate at which loads finish went up four times once the line is full (throughput improved). That is pipelining in one picture.


Basic Definitions

Pipelining: an implementation technique in which the execution of an instruction is divided into a sequence of stages, and the execution of multiple instructions is overlapped, with each stage working on a different instruction in the same clock cycle.

Between two stages sits a pipeline register (latch, buffer) that holds the results of one stage for the next stage to use in the following cycle. All stages move forward together on each clock edge.

          +------+   +-----+   +------+   +-----+   +------+   +-----+   +------+
input --> |Stage | ->| reg | ->|Stage | ->| reg | ->|Stage | ->| reg | ->|Stage | --> output
          |  1   |   |     |   |  2   |   |     |   |  3   |   |     |   |  4   |
          +------+   +--+--+   +------+   +--+--+   +------+   +--+--+   +------+
                        |                    |                    |
                   clock ---------------------------------------------- (common)
  • Stage delay ti: the time the logic of stage i needs.

  • Clock cycle (cycle time) τ: must be long enough for the slowest stage plus the pipeline register overhead: τ = max(ti) + latch delay.

  • Latency: time for one instruction to pass through all k stages = k x τ.

  • Throughput: number of instructions completed per unit time. In the steady state, one per cycle: 1/τ.

The Classic 5-Stage RISC Pipeline

Most textbooks (Patterson and Hennessy) use the MIPS-style 5-stage pipeline, which we will also use in the hazard chapters:

Stage

Name

Work done

IF

Instruction Fetch

Read the instruction from memory (instruction cache) at PC; PC = PC + 4

ID

Instruction Decode / register read

Decode the opcode, read source registers from the register file

EX

Execute

ALU operation, or compute the memory address for load/store

MEM

Memory access

Load reads data memory; store writes it; others do nothing

WB

Write Back

Write the result into the destination register

Other books use other stage names, for example the 4-stage FI, DA, FO, EX (Mano) or the 6-stage FI, DI, CO, FO, EI, WO (Stallings). The mathematics is the same.


The Space-Time Diagram

The standard way to visualise a pipeline is a table with clock cycles across and instructions down. Here are 5 instructions on a 4-stage pipeline (S1 to S4):

Cycle:   1   2   3   4   5   6   7   8
I1       S1  S2  S3  S4
I2           S1  S2  S3  S4
I3               S1  S2  S3  S4
I4                   S1  S2  S3  S4
I5                       S1  S2  S3  S4

Read it carefully:

  • The first instruction needs k = 4 cycles to come out (filling the pipeline).

  • After that, one instruction completes every cycle. The remaining n - 1 = 4 instructions need 4 more cycles.

  • Total = k + (n - 1) = 4 + 4 = 8 cycles, instead of n x k = 20 cycles without pipelining.

  • In cycle 4 all four stages are busy with four different instructions. That overlap is where the speed comes from.


The Formulas

Let k = number of stages, n = number of instructions, τ = pipeline clock period, and tn = time for one instruction on the equivalent non-pipelined processor.

Pipelined time       T_pipe = (k + n - 1) x tau

Non-pipelined time   T_seq  = n x t_n

Speedup              S = T_seq / T_pipe = n x t_n / ((k + n - 1) x tau)

Ideal case (balanced stages, no latch delay, t_n = k x tau):
                     S = n x k / (k + n - 1)   ->  k   as n -> infinity

Efficiency           E = S / k = n / (k + n - 1)     (fraction of stage-cycles used)

Throughput           W = n / ((k + n - 1) x tau)     ->  1 / tau  as n grows

Why the maximum speedup is k: the pipeline cuts the work into k pieces and works on k instructions at once, so at best it is k times faster. It never reaches exactly k because of the k - 1 cycles spent filling the pipeline, unbalanced stages, latch overhead and (in reality) hazards.

Careful with tn: for the non-pipelined machine, use the sum of the stage delays (the actual logic delay), not k x τ, unless the question says otherwise. A non-pipelined processor does not need to wait for the slowest stage k times, and it does not need the pipeline latches.


Worked Example 1: Balanced Stages

Problem. A 5-stage pipeline has every stage taking 2 ns (latch delay included). 100 instructions are executed. Find the time, speedup over a non-pipelined machine taking 10 ns per instruction, efficiency and throughput.

T_pipe     = (5 + 100 - 1) x 2 = 104 x 2 = 208 ns
T_seq      = 100 x 10          = 1000 ns
Speedup    = 1000 / 208        = 4.81
Efficiency = 100 / 104         = 0.9615  (96.15%)
Throughput = 100 / 208 ns      = 0.4808 instructions per ns = 480.8 MIPS

The speedup 4.81 is close to, but below, the ideal 5. With 10,000 instructions it would be 4.998.


Worked Example 2: Unbalanced Stages and Latch Delay

Problem. A 4-stage pipeline has stage delays 150, 120, 160 and 140 ns. Each pipeline register adds 5 ns. Find the time to execute 1000 instructions, the speedup over a non-pipelined processor (which needs only the sum of the stage delays), and the maximum possible speedup.

Clock period   tau = max(150, 120, 160, 140) + 5 = 165 ns

T_pipe = (4 + 1000 - 1) x 165 = 1003 x 165 = 165,495 ns
t_n    = 150 + 120 + 160 + 140 = 570 ns
T_seq  = 1000 x 570 = 570,000 ns

Speedup             = 570,000 / 165,495 = 3.44
Max speedup (n->inf) = 570 / 165       = 3.45   (not 4!)

Two lessons. First, the slowest stage sets the clock: the 120 ns stage wastes 40 ns of every cycle. Second, latency got worse: one instruction now takes 4 x 165 = 660 ns instead of 570 ns. Pipelining improves throughput, not latency.


Worked Example 3: Splitting the Slowest Stage

Problem. A 5-stage pipeline has stage delays 300, 500, 400, 300 and 250 ps, plus 20 ps per pipeline register. The designer splits the 500 ps stage into two stages of 250 ps each. For a very large number of instructions, what is the throughput improvement? What happens to the latency of one instruction?

Old clock = 500 + 20 = 520 ps      (5 stages)
New clock = max(300, 250, 250, 400, 300, 250) + 20 = 420 ps   (6 stages)

Throughput improvement (n large) = 520 / 420 = 1.238   (about 24% faster)

Latency: old = 5 x 520 = 2600 ps     new = 6 x 420 = 2520 ps

The new bottleneck is the 400 ps stage, so the gain is 520/420, not 520/270. For small programs the extra stage costs one extra fill cycle: with 10 instructions the times are 14 x 520 = 7280 ps vs 15 x 420 = 6300 ps, still a win here.


Worked Example 4: Pipelined vs Non-Pipelined Processor (GATE-style)

Problem. A non-pipelined processor runs at 2.5 GHz with an average CPI of 4. Its pipelined version has 5 stages, but because of latch delays the clock drops to 2 GHz. Assuming no stalls, what is the speedup for a large program?

Non-pipelined: time per instruction = CPI / f = 4 / 2.5 GHz = 1.6 ns
Pipelined    : ideal CPI = 1, time per instruction = 1 / 2 GHz = 0.5 ns

Speedup = 1.6 / 0.5 = 3.2

This uses the CPU performance equation from earlier chapters: time = instruction count x CPI x clock period. Pipelining reduces the CPI (towards 1) even though it slightly lengthens the clock period.


Why Not a 100-Stage Pipeline?

If speedup approaches k, why not use a huge k? Because the latch overhead does not shrink. Suppose the instruction's total logic delay is 1000 ps and each pipeline register adds 50 ps. With k equal stages, τ = 1000/k + 50 ps:

Stages k

Clock τ (ps)

Throughput gain vs k = 1

1

1050

1.00

2

550

1.91

5

250

4.20

10

150

7.00

20

100

10.50

50

70

15.00

Going from 20 to 50 stages gives only about 1.4 times more, and the gain can never exceed 1050/50 = 21. Worse, deeper pipelines suffer more from hazards: a wrong branch guess throws away more partly executed instructions. This is why the Pentium 4's very deep pipeline (20 stages, and 31 in its later Prescott versions) was abandoned and modern cores use roughly 10 to 20 stages.


Conditions for Ideal Pipelining

The formulas above assume:

  1. All stages take the same time (balanced), so no stage idles.

  2. Every instruction passes through all stages.

  3. A new instruction can enter every cycle: no instruction depends on a result not yet produced, no two stages fight over the same hardware, and branches do not disrupt the fetch order.

The third condition is the one real programs break. Those breakages are hazards, studied next.

Instruction Pipeline vs Arithmetic Pipeline

Pipelining is not only for instruction execution. An arithmetic pipeline splits one complex operation into stages. A classic example (Mano) is floating-point addition in four stages: compare exponents, align mantissas, add mantissas, normalise the result. Several additions (for example in a vector loop) then overlap. Instruction pipelines overlap the fetch-decode-execute steps of different instructions; arithmetic pipelines overlap the sub-steps of a long arithmetic operation.


Pipelined vs Non-Pipelined: Summary Table

Point

Non-pipelined

Pipelined (k stages)

Instructions in progress at once

1

Up to k

Time for n instructions

n x tn

(k + n - 1) x τ

Latency of one instruction

tn

k x τ (equal or larger)

Ideal CPI

Several cycles (or one long cycle)

1

Hardware

Simpler

Pipeline registers, hazard handling


Common Mistakes

  • Using n x k instead of k + n - 1 for the pipelined cycle count. Only the first instruction pays the full k cycles.

  • Using the average stage delay as the clock period. The clock is set by the slowest stage plus latch delay.

  • Adding latch delay to the non-pipelined time. A non-pipelined machine has no pipeline registers; use the sum of the stage delays unless told otherwise.

  • Claiming pipelining reduces the execution time of an instruction. It reduces the time for a program (throughput), while the latency of each instruction stays the same or grows.

  • Saying the maximum speedup is always k. That holds only for perfectly balanced stages with no overhead; otherwise it is tn/τ.


GATE and Interview Questions

A 6-stage pipeline with perfectly balanced stages and no overhead executes a very large number of instructions with no hazards. What is the speedup over a non-pipelined implementation?

6. With balanced stages and n → infinity, S = nk/(k + n - 1) → k.

A 4-stage pipeline has stage delays 20, 30, 25 and 15 ns with 5 ns latch delay. How long do 50 instructions take?

Clock = 30 + 5 = 35 ns. Cycles = 4 + 50 - 1 = 53. Time = 53 x 35 = 1855 ns.

In the previous question, what is the speedup over a non-pipelined processor for 50 instructions?

Non-pipelined time per instruction = 20 + 30 + 25 + 15 = 90 ns, so 50 x 90 = 4500 ns. Speedup = 4500 / 1855 = 2.43.

What is the efficiency of a 5-stage pipeline executing 20 instructions?

E = n/(k + n - 1) = 20/24 = 0.833, i.e. 83.3% of stage-cycles do useful work; the rest are lost filling and draining the pipeline.

Does pipelining reduce latency or increase throughput?

It increases throughput. Latency of an individual instruction stays the same or increases slightly because of pipeline register delays and the slowest-stage clock.

Why does a deeper pipeline not always give a faster processor?

Latch overhead is paid in every stage, so the clock period cannot fall below the latch delay; and hazards cost more cycles in a deep pipeline (for example, more instructions are flushed on a branch misprediction).


Summary

  • Pipelining splits instruction execution into k stages separated by pipeline registers and overlaps different instructions in different stages.

  • Clock period τ = slowest stage delay + latch delay. Time for n instructions = (k + n - 1)τ.

  • Speedup = n tn / ((k + n - 1)τ); ideally it approaches k. Efficiency = n/(k + n - 1); throughput approaches 1/τ.

  • Unbalanced stages and latch delay reduce the maximum speedup to tn/τ (3.45 instead of 4 in our example).

  • Pipelining improves throughput, not latency, and deeper is not always better.

  • The ideal case assumes a new instruction can start every cycle; real programs break this through hazards.

Next, in Pipeline Hazards, we see what goes wrong when instructions depend on each other or compete for hardware, and how much it costs.