Deep pipelining trade-offs: Visual walkthrough — Hardware deep dive

Step 1 — What "doing work" costs: one long job

WHAT. Picture a single instruction as one long strip of work — like a plank of wood that takes time to travel through a machine. Call the total travel time $T_{0}$ .

WHY start here. Before we can split work, we must agree what the unsplit thing costs. Everything later is measured against this one number.

PICTURE. In the figure, the amber bar is the whole job. Its length is the time $T_{0}$ . There are no dividers yet — the machine does the entire job in one go, then starts the next plank only when the first has fully exited.

If we feed instructions one-at-a-time through this un-split machine, one result comes out every $T_{0}$ seconds. That rate — one every $T_{0}$ — is the baseline we want to beat.

Step 2 — Cutting the plank: what a "stage" and a "register" are

WHAT. Now we slice the plank into $k$ equal pieces with dividers. Each piece is a stage. To pipeline $k$ stages you insert a divider between each neighbouring pair — that is $k - 1$ pipeline registers (a design that also latches the very inputs and outputs uses $k + 1$ ; the count grows with $k$ either way). Each divider latches (freezes and remembers) the partial result at the tick of the clock.

WHY do this. If four workers each own one quarter of the plank, then at any instant four planks are in the machine at once — one per worker. That overlap is the whole point of pipelining. But overlap only works if there's a gate between workers so plank #2 doesn't crash into plank #1's leftovers. That gate is the register — and note it only appears once you have two stages to separate. At $k = 1$ there is nothing to divide, so there are no registers and no toll.

PICTURE. The single amber bar is now $k$ white segments separated by cyan divider-gates. Each cyan gate costs a little slab of time $t_{reg}$ — it is not free to freeze and hand off a value.

Step 3 — The clock can only tick as fast as the slowest slice

WHAT. If the plank is cut into $k$ equal pieces, each piece of logic takes $τ = T_{0} / k$ . But every piece (for $k \geq 2$ ) also sits behind a gate, so the real time a stage needs is:

one clock tick T_{cycle} = logic in the slowest slice τ + the gate’s fixed toll t_{reg}

WHY the plus, and why the slowest. The clock is a single drumbeat for the whole machine — every gate latches on the same beat. So the drum can only beat as fast as the most loaded worker can finish and hand off. That worker needs time to do its logic and get through its gate: hence $τ + t_{reg}$ . The clock period $T_{cycle}$ is exactly that.

PICTURE. The figure zooms into one stage: a white logic block of width $τ$ followed immediately by the cyan gate of width $t_{reg}$ . The dashed amber bracket spanning both is the clock period. Notice the toll $t_{reg}$ is the same width in every stage — it does not shrink when you slice thinner.

Frequency is just the beats-per-second: $f = 1/ T_{cycle}$ . More stages $\Rightarrow$ smaller $T_{0} / k$ $\Rightarrow$ smaller period $\Rightarrow$ higher $f$ . That is the promise of deep pipelining.

Step 4 — Where the promise dies: the toll wins

WHAT. Watch what $T_{cycle} (k) = T_{0} / k + t_{reg}$ (the $k \geq 2$ branch) does as $k$ grows.

WHY this is the crux. The shrinking term $T_{0} / k$ races toward zero, but the toll $t_{reg}$ just sits there. Add it up and the cycle time flattens out onto a floor at $t_{reg}$ . Once you're near the floor, adding stages costs you real registers (area, power) and buys you almost no speed.

PICTURE. The blue curve is $T_{cycle} (k)$ for $k \geq 2$ ; the lone amber dot marks the register-free $k = 1$ point at $T_{0}$ . The curve plunges early — big wins from 2→5 stages — then bends and hugs a horizontal amber dashed line, the floor $t_{reg}$ . The gap between curve and floor is the only speed you have left to gain. Past the knee, that gap is nearly nothing.

Now the ideal speedup (still assuming no stalls). Un-pipelined does one instruction per $T_{0}$ ; pipelined streams one per $T_{cycle}$ , so:

Speedup (k) = \frac{T _{0}}{T _{cycle} ( k )} = \frac{T _{0}}{\frac{T _{0}}{k} + t _{reg}} k \to \infty \frac{T _{0}}{t _{reg}}

Numerator $T_{0}$ — the baseline job time we're beating
Denominator — the streaming period; as $k \to \infty$ it collapses to $t_{reg}$
The limit $T_{0} / t_{reg}$ — a hard ceiling set purely by register overhead

So even with infinite stages and zero hazards, speedup is capped. That's the register wall.

Recall Why doesn't

$k = 1$ blow up the speedup formula? At $k = 1$ what does $T_{cycle}$ equal, and why? ::: Exactly $T_{0}$ — there are no registers, so no $t_{reg}$ toll; speedup is $1 \times$ as expected.

Step 5 — The second tax: a wrong guess flushes the pipe up to the resolve stage

WHAT. Real code branches ("if this, jump there"). The processor guesses the branch outcome to keep the pipe full (see Branch Prediction). A wrong guess means every instruction it started after the branch — up until the branch's answer is known — is garbage and must be thrown away — flushed.

WHY depth makes this worse. The branch's true direction is only known once it reaches the stage that resolves it — call that stage number $b$ . Everything fetched after the branch and before it resolves (about $b - 1$ instructions) is wrong-path work. So the flush penalty is really $b - 1$ , not the full $k - 1$ .

Two honest cases:

Naive / late resolve: if the branch is only resolved at the very end, $b \approx k$ and the penalty $\approx k - 1$ — the worst case, and the one people quote for a scare.
Real designs: resolve the branch at a fixed, early stage (a dedicated branch unit), so $b$ is roughly constant and the penalty does not scale one-for-one with $k$ . Deeper pipes still hurt (fetch-to-resolve distance tends to creep up with depth), but sub-linearly, not lock-step.

PICTURE. Two side-by-side pipe diagrams. Top: a short pipe — a red X marks the branch, the shaded bubbles up to the resolve stage get flushed. Bottom: a deeper pipe — same red X; if resolve is late the crater is huge ( $k - 1$ ), if resolve is pinned early only $b - 1$ bubbles wash out. Same mistake, penalty set by where you resolve, not raw depth.

Step 6 — Data and structural hazards: the stalls that also grow (but gently)

WHAT. Control flushes aren't the only tax. Two more:

Data hazards — an instruction needs a result the one ahead hasn't produced yet (a "read-after-write" dependence). Deeper pipes push the producer's result further away in cycles, so forwarding paths lengthen and some stalls appear. See Pipeline Hazards.
Structural hazards — two instructions want the same hardware (one memory port, one ALU) in the same cycle; one must wait.

WHY acknowledge them. They do grow with depth, but sub-linearly: forwarding networks absorb most data hazards, and duplicating contended units removes most structural ones. They rarely scale like the flush penalty, but they are real and they push the optimal depth down.

PICTURE. A stacked bar of the CPI budget: the ideal $1$ , a growing amber slab for control flushes (Step 5), and two thinner, slowly-growing cyan slabs for data and structural stalls that flatten out as forwarding and duplication kick in.

Step 7 — Fill and drain: a finite pipe is never fully streaming

WHAT. The speedup of Step 4 assumed an infinite stream — one result out every tick, forever. A real program runs $N$ instructions through a $k$ -stage pipe. The first result doesn't appear until the pipe is filled ( $k$ ticks to push the first instruction all the way through), and near the end the pipe drains as the last instructions exit with no new ones behind them.

WHY it matters. Those startup/wind-down ticks are pure overhead not amortised over the whole run. For short bursts (or after every flush, which empties and refills the pipe) they bite hard — and deeper pipes have longer fill/drain.

PICTURE. A timing chart: an amber "fill" ramp of $k - 1$ idle-ish ticks before steady state, a long white steady-state band of one-per-tick, then an amber "drain" ramp of $k - 1$ ticks at the end. The deeper the pipe, the wider both amber ramps.

Step 8 — Imbalance: the real clock is set by the worst stage

WHAT. Everything so far assumed logic splits into perfectly equal pieces of $τ = T_{0} / k$ . It doesn't. Some operations are atomic (a cache lookup, a TLB hit — you can't stop halfway), so real stage delays $T_{1}, T_{2}, \dots, T_{k}$ are uneven.

WHY it matters. The clock is one drumbeat, so it must wait for the slowest stage. That gives the honest cycle time:

T_{cycle} = i max (T_{i}) + t_{reg}

$T_{i}$ — the logic delay of stage $i$ (not necessarily $T_{0} / k$ )
$max_{i} (T_{i})$ — the longest stage; it alone sets the clock, wasting the slack in every shorter stage
$t_{reg}$ — same register toll as before

In the ideal even split $max_{i} (T_{i}) = T_{0} / k$ and we recover Step 3. In reality $max_{i} (T_{i}) > T_{0} / k$ , so the real clock is always slower than the even-split dream — and deeper pipes, slicing thinner, make perfect balance harder, widening the gap.

PICTURE. Left panel — imbalance: real stages have jagged lengths; the tallest bar (amber) sets the clock, and all the shorter stages waste the hatched difference. Right panel — power: $P = C V^{2} f$ , and more stages means more registers to clock; the clock network alone burned 30–40% of Pentium 4's power. See Dynamic Voltage and Frequency Scaling (DVFS) for how voltage is traded against frequency.

Step 9 — The tug-of-war and the real verdict

WHAT. Real performance is throughput = useful instructions per second, combining every effect above:

Throughput = \frac{f}{CPI} = \frac{1}{( max _{i} ( T _{i} ) + t _{reg} ) \cdot CPI ( k )}

WHY both terms fight. Deepening $k$ pushes $f$ up (Step 3) but pushes CPI up too (Steps 5–6) and fill/drain and imbalance chip at the frequency win (Steps 7–8). Throughput is their ratio, so it climbs only while the frequency win outruns the losses — then it peaks at an optimal depth (written $k_{opt}$ ) and falls.

PICTURE. Three curves over $k$ : cyan $f (k)$ rising, amber $CPI (k)$ rising, and the white throughput curve $f / CPI$ that rises, rounds off at a peak, and then droops. A vertical dashed line marks the sweet spot $k_{opt} \approx 10 - 15$ .

The one-picture summary

Everything above in a single frame: the shrinking logic slice building the register floor, the flush penalty set by the resolve stage, the data/structural stalls and fill/drain overhead, imbalance lifting the real clock, and the throughput hill that rises to $k_{opt}$ then rolls off into the wall.

Recall Retell it like Feynman (plain words, no symbols)

Imagine an assembly line. Chop it into more workstations and each worker finishes their bit sooner, so the conveyor belt can run faster — that's more clock speed. But every workstation needs a little gate to hand the part to the next worker, and that gate takes a fixed sliver of time no matter how tiny the work is. Slice thin enough and the gates are all you're paying for — the belt can't go any faster. That's the floor. (And the very first machine, one worker doing the whole part, has no gate at all — no toll.)

Worse: whenever the line guesses wrong about which way to route a part, it scraps everything already on the belt up to the point where it checks the guess — so put the checkpoint early and you scrap less. On top of that, workers sometimes wait for a part the previous worker hasn't finished (data), or fight over one shared tool (structural), and every time the belt empties it takes a while to fill back up. Add all that and past ten-to-fifteen stations the line gets slower and hotter at once. Pentium 4 built a monster 31-station line, ran it blazing fast, and got nothing extra out the end while burning way more power. Then Intel built a shorter, smarter line. That whole rise-then-fall is the deep-pipeline wall.

Recall Quick self-check

What term in $T_{cycle} = T_{0} / k + t_{reg}$ creates the speed floor? ::: The fixed register toll $t_{reg}$ — it never shrinks as $k$ grows. Why is $t_{reg}$ absent at $k = 1$ ? ::: There are no pipeline registers when the pipe isn't split, so there's no toll to pay. How many instructions does one misprediction flush, honestly? ::: About $b - 1$ , where $b$ is the stage that resolves the branch — only $k - 1$ in the worst case where resolve is at the very end. Name two stall sources besides control flushes. ::: Data hazards (waiting on a not-yet-produced result) and structural hazards (contention for shared hardware). Why does a finite run never reach the ideal speedup? ::: Fill and drain cost $k - 1$ ticks that aren't amortised, and every flush empties and refills the pipe. What sets the real clock period once stages are uneven? ::: The slowest stage: $T_{cycle} = max_{i} (T_{i}) + t_{reg}$ . In the Prescott example, why was net performance $\times 1.0$ ? ::: Frequency rose $\times 1.5$ but CPI also rose $\times 1.5$ , so $f / CPI$ stayed flat.