The pipeline idea: stages, latches, cycle time, k + n − 1 cycles

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Row-wise miss ratio for elements of size s and blocks of size B? from Lesson 4.3.4
• Effective CPI with cache misses? from Lesson 4.3.2
• What sets the clock cycle time of a datapath? from Lesson 0.2.3

1 · The Hook

🎣

Washing, drying and folding one load of laundry takes 90 minutes. Four loads take 6 hours if you wait for each to finish, but about 2½ hours if the washer starts load 2 while the dryer handles load 1. A CPU can do the same with instructions: fetch the next one while decoding this one while executing the one before. That is pipelining, and it is in nearly every GATE paper.

2 · Predict First

🤔

A pipeline has 4 stages, each taking one clock cycle. The first instruction enters at cycle 1. In which cycle does the 10th instruction finish?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

The first finishes at cycle 4; after that one instruction finishes every cycle: 4 + 9 = cycle 13. In general k + n − 1 = 4 + 10 − 1.

Stages

Split the work of one instruction into k stages (for example fetch, decode, execute, write back). Each stage is a separate piece of hardware, so k different instructions can be in the k stages at the same time.

Pipeline registers (latches)

Between stages sit pipeline registers that hold each instruction's partial results at the clock edge, so every stage works on its own instruction for the whole cycle.

The clock

All stages move in step, so the cycle must fit the slowest stage: cycle time τ = max(stage delays) + latch delay.

Time for n instructions

• The first instruction needs k cycles to pass through (filling the pipeline).
• After that, one instruction completes every cycle.

Pipelined time = (k + n − 1) × τ. Non-pipelined time = n × (sum of stage delays) (one instruction at a time, no latches).

Space–time diagram

Rows = instructions, columns = cycles, cells = the stage the instruction is in. It is the tool for every pipeline question.

4 instructions, 4 stages: 4 + 4 − 1 = 7 cycles.

Latency vs throughput

Pipelining does not make one instruction faster (its latency is k cycles, even slightly more than before because of latch delays). It raises throughput: completed instructions per unit time.

4 · Visual

Without pipelining (each instruction does all 4 stages before the next starts):
I1 [S1 S2 S3 S4]
I2              [S1 S2 S3 S4]
I3                           [S1 S2 S3 S4]          3 x 4 = 12 cycles

With pipelining:
I1 [S1 S2 S3 S4]
I2    [S1 S2 S3 S4]
I3       [S1 S2 S3 S4]                              4 + 3 - 1 = 6 cycles

5 · Worked Examples

Example 1 Easy

A 5-stage pipeline, one cycle per stage. How many cycles for 100 instructions?

Solution

5 + 100 − 1 = 104.

Example 2 Medium

Stage delays 20, 30, 25, 25 ns; latch delay 5 ns. Cycle time of the pipeline? Time for one instruction without pipelining?

Solution

Pipelined τ = 30 + 5 = 35 ns. Non-pipelined: 20 + 30 + 25 + 25 = 100 ns.

Example 3 GATE

Same pipeline. How long do 50 instructions take, pipelined and non-pipelined?

Solution

Pipelined: (4 + 49) × 35 = 1,855 ns. Non-pipelined: 50 × 100 = 5,000 ns.

6 · GATE Traps

⚠️

• The first instruction takes k cycles; total is k + n − 1, not k × n.
• The cycle time is set by the slowest stage plus the latch delay.
• Non-pipelined time uses the sum of stage delays (no latches).
• Pipelining improves throughput, not the latency of one instruction.

7 · Memory Hook

🧠

"Fill once, then one per tick." k cycles to fill, then n − 1 more: k + n − 1.

8 · Connect the Dots

Phase 4 sped up memory; Phase 5 speeds up the CPU's instruction flow. Next: speedup, efficiency and throughput formulas, and what happens with unequal stages and splitting the slowest stage.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markCycles

An 8-stage pipeline (one cycle per stage) runs 200 instructions. Total cycles?

Numerical answer: ________

Q2NAT1 markCycle time

Stage delays 12, 15, 9, 14 ns and latch delay 1 ns. Pipeline cycle time (ns)?

Numerical answer: ________

Q3NAT2 marksTotal time

With the stages of the previous question, how long do 100 instructions take pipelined (ns)?

Numerical answer: ________

Q4MCQ1 markLatency

Compared with the non-pipelined design, the time for a single instruction to pass through a pipeline is usually:

• (A) zero
• (B) about the same or slightly longer
• (C) k times shorter
• (D) half as long

Q5NAT2 marksNon-pipelined time

Same stages (12, 15, 9, 14 ns). Time for 100 instructions without pipelining (ns)?

Numerical answer: ________

10 · Rule Card

• Pipeline: k stages, pipeline registers between them; all move each cycle.
• τ = max stage delay + latch delay.
• Pipelined time = (k + n − 1)τ; non-pipelined = n × Σ stage delays.
• Space–time diagram: instructions × cycles.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

pipelinestagepipeline register (latch)cycle time τfill timek + n − 1space–time diagramlatency vs throughput

12 · Answer Vault