Foundations — Pipelining — 5-stage pipeline, each stage

This page is the ground floor for the pipelining topic. Before we can talk about speedup, stages, and clocks, we have to earn every symbol the parent note quietly used. We go one brick at a time — nothing appears before it is drawn and named.

0. The picture we keep coming back to

Everything below is a variation on one image: a row of workers, each doing one small task, passing work along. Hold this in your head.

1. Instruction — the "job"

The picture: one tray of laundry, one sandwich, one car body moving down the line. In this topic an instruction is the unit of work that flows through the pipeline.

Why the topic needs it: pipelining is about overlapping the steps of consecutive instructions. If you don't have a clear notion of "one job", you can't talk about overlapping many jobs.

2. Stage — one step of the job

The picture: one workstation in the assembly line — the washer, or the "add cheese" friend. Each station does only its one job, then passes the work on.

Why the topic needs it: the whole trick is that different stages use different hardware, so they can all run at the same time on different instructions. No stages → nothing to overlap.

3. The letter $k$ — how many stages

The picture: count the workstations in the row. Five stations → $k=5$.

Why a letter and not just "5"? Because we want formulas that work for any pipeline — a 3-stage one, a 14-stage one. Writing $k$ lets one formula describe them all. The moment we plug in a real machine, we replace $k$ with a number.

4. The letter $t$ — how long one stage takes

The picture: the length of one tick of a metronome. Every station finishes its piece in one $t$, then everything shifts right together.

Why the topic needs $t$: every timing formula — sequential time, pipelined time, speedup — is measured in units of $t$. It's the ruler we measure everything with.

5. The letter $n$ — how many instructions

The picture: the number of trays waiting to enter the line. Four trays → $n=4$.

Why the topic needs it: pipelining barely helps for tiny $n$ but almost triples/quadruples throughput for huge $n$. To see when pipelining wins, we must keep $n$ as an adjustable knob.

6. Reading the space-time diagram (fill and drain)

Now that we have jobs, stages, $k$, $t$, and $n$, we can read the diagram that is the derivation of speedup. Time runs left→right in units of $t$.

This picture is where $(k+n-1)$ comes from — count the columns: $k$ columns to push the first instruction out, then one extra column for each of the remaining $n-1$ instructions.

7. The fraction bar — what "speedup" means

The picture: two stopwatches side by side. If the slow one reads 20 seconds and the fast one reads 5, then $S=20/5=4$ → "four times faster".

Why a division? Dividing the old time by the new time cancels the units (the $t$'s and the seconds), leaving a pure "times faster" number that means the same on any machine.

8. The arrow $\to$ and "limit" — what happens for huge $n$

The picture: the drain and fill triangles in the space-time diagram stay the same tiny size, but the steady-state middle stretches out forever. The two little triangles become a rounding error.

Why we care: it tells us the best possible speedup. In the fraction $\frac{nk}{k+n-1}$, when $n$ is gigantic the "$k-1$" is negligible next to $n$, so the fraction settles at $k$.

Let's see the fraction climb toward this ceiling as $n$ grows.

9. Throughput vs Latency — two different questions

The picture: latency is how long a single car spends on the assembly line; throughput is how many cars roll off the end per hour. A pipeline improves the second without shortening the first.

10. Pipeline register — the tray between stations

The picture: the little tray each sandwich-friend drops the half-made sandwich onto before the next friend picks it up. Without the tray, the next sandwich would smear over the last one.

Why the topic needs it: stages share buses. Stage 2 needs what stage 1 produced, but stage 1 is already producing something new next cycle. The register freezes the value in transit. There are four of them, named for the stages they bridge: IF/ID, ID/EX, EX/MEM, MEM/WB.

The prerequisite map

Equipment checklist

Cover the right side and test yourself before moving on.

Connections

• 4.1.18 Pipelining — 5-stage pipeline, each stage (Hinglish)
• Pipeline Hazards (Data, Control, Structural)
• Forwarding and Bypassing
• Clock Frequency and CPI
• Single-cycle vs Multi-cycle Datapath
• Amdahl's Law