Self-checkedTier 1 12 min readcoa.pipeline-performance

Pipeline speedup and CPI calculations

The arithmetic of pipeline performance: cycles and time for n instructions, speedup against a non-pipelined machine, efficiency and throughput, unequal stages and register overhead, deeper pipelines and their limit, and CPI and speedup when stalls are added.

Why it exists

Once the structure of a pipeline is clear, GATE asks you to put numbers on it: how many cycles for $n$ instructions, how much faster than the non-pipelined machine, what the clock becomes with unequal stages, what happens when instructions stall, and what a deeper pipeline buys. These are formula questions and they are easy to get wrong by one cycle or by the wrong baseline. This page collects the formulas, the assumptions behind each, and worked examples whose numbers are computed by program.

Prerequisites

Instruction pipelining

You need stages, pipeline registers, the space-time diagram and the $k + n - 1$ count from instruction pipelining.

Precise definitions

Let $k$ be the number of stages, $n$ the number of instructions, $\tau$ the clock period of the pipeline.

Time for $n$ instructions.

Pipelined, no stalls: $T_{pipe} = (k + n - 1)\,\tau$ .
Pipelined, with $s$ stall cycles in total: $T_{pipe} = (k + n - 1 + s)\,\tau$ .
Non-pipelined, if an instruction takes $k$ cycles of the same length $\tau$ : $T_{non} = n\,k\,\tau$ . More generally, with stage delays $t_1, \ldots, t_k$ and no registers, $T_{non} = n\,(t_1 + \cdots + t_k)$ .

Speedup $= T_{non} / T_{pipe}$ .

Equal stages, same clock, no stalls: $S = \dfrac{n\,k}{k + n - 1}$ . It is below $k$ and increases with $n$ ; for $n \to \infty$ , $S \to k$ .
Unequal stages: $\tau = \max_i t_i + d_{reg}$ and the large- $n$ speedup is $S_\infty = \dfrac{t_1 + \cdots + t_k}{\max_i t_i + d_{reg}}$ .

Efficiency and throughput.

Efficiency $= S / k$ : the fraction of the ideal $k$ -fold speedup achieved, equivalently the fraction of stage-cycles doing useful work.
Throughput $= \dfrac{n}{(k + n - 1)\,\tau}$ instructions per unit time, tending to $1/\tau$ .

CPI (cycles per instruction). For a pipeline in steady state

$\text{CPI}_{pipe} = 1 + \text{stall cycles per instruction},$

where the stall cycles per instruction add up the contributions of each cause: for each, (fraction of instructions affected) $\times$ (stall cycles each). The ideal pipeline has CPI $= 1$ . (For a finite $n$ the measured $\text{cycles}/n$ also includes the fill time $k - 1$ , which becomes negligible for large $n$ .)

Speedup with stalls. For a non-pipelined machine with CPI $_{non}$ and clock period $\tau_{non}$ and a pipelined one with CPI $_{pipe}$ and period $\tau_{pipe}$ ,

$S = \frac{\text{CPI}_{non}\,\tau_{non}}{\text{CPI}_{pipe}\,\tau_{pipe}}.$

If the clocks are the same and the non-pipelined machine takes $k$ cycles per instruction, then $S = k/(1 + \text{stall cycles per instruction})$ .

Depth of the pipeline. Splitting a total logic delay $T$ evenly into $k$ stages with register delay $d$ per stage gives a period $T/k + d$ , so the large- $n$ speedup over the unpipelined logic is

$S_\infty(k) = \frac{T}{T/k + d} < \frac{T}{d},$

which grows more slowly than $k$ and saturates at $T/d$ . Meanwhile each stall or branch penalty costs more cycles in a deeper pipeline, so the useful depth is limited.

How it works

The animation is the same 6-instruction run with two instructions held up (I3 for 2 extra cycles, I5 for 1). Each stall cycle is amber; the blocked instructions behind it are grey. The pipeline needs $5 + 6 - 1 + 3 = 13$ cycles instead of 10, which is the rule "every stall cycle adds one cycle to the total". The counter under the diagram shows the cycles per completed instruction (CPI) so far; it is high at the start because of the fill time and settles towards $1 + \text{stalls per instruction}$ only for long runs.

The same pipeline when two instructions are held up: start

Pipeline simulated, not typed

cycle	1	2	3	4	5	6	7	8	9	10	11	12	13
I1
I2
I3
I4
I5
I6

MEM

cycles so far

completed

cycles per completed instruction

Step 0

Same pipeline, but I3 must stay in ID for 2 extra cycles and I5 for 1 extra cycle (for example because each is waiting for a result; the hazard pages explain why and how to shorten the wait). Every instruction behind a held one is blocked as well.

0 / 13

computed by script: cycle-by-cycle simulation of an in-order pipeline. python3 scripts/gen-coa-pipe-traces.py

Worked examples

EX 1Speedup and its limit

Easy

For a 5-stage pipeline with equal stages and no stalls, the speedup over the non-pipelined machine is $5n/(n + 4)$ : for $n = 6$ it is $30/10 = 3$ , for $n = 100$ it is $500/104 \approx 4.81$ and for a million instructions it is about $4.99998$ . It can never reach 5, and for a short run it is much lower: the fill time is a large part of the total. Efficiency for $n = 6$ is $3/5 = 60\%$ . (The numbers are in the table of the previous page, example 1.)

EX 2Unequal stages and register overhead

Medium

Five stages take 12, 8, 10, 14 and 6 ns; each pipeline register adds 1 ns. Find the clock, the latency and the speedup for 100 instructions and for a very long run.

#include <stdio.h>
 
int main(void) {
    /* five stage delays in ns and a pipeline register delay of 1 ns */
    double delay[5] = {12, 8, 10, 14, 6}, latch = 1;
    double sum = 0, slowest = 0;
    for (int i = 0; i < 5; i++) {
        sum += delay[i];
        if (delay[i] > slowest) slowest = delay[i];
    }
    double clock = slowest + latch;
    long n = 100;
    printf("one instruction without a pipeline: %.0f ns\n", sum);
    printf("pipeline clock: %.0f ns (slowest stage %.0f + register %.0f)\n", clock, slowest, latch);
    printf("latency of one instruction in the pipeline: %.0f ns\n", 5 * clock);
    printf("%ld instructions: %.0f ns without, %.0f ns with, speedup %.4f\n", n, n * sum, (5 + n - 1) * clock, n * sum / ((5 + n - 1) * clock));
    printf("speedup for very many instructions: %.4f\n", sum / clock);
    return 0;
}

one instruction without a pipeline: 50 ns
pipeline clock: 15 ns (slowest stage 14 + register 1)
latency of one instruction in the pipeline: 75 ns
100 instructions: 5000 ns without, 1560 ns with, speedup 3.2051
speedup for very many instructions: 3.3333

Reading it. The non-pipelined machine takes the sum of the delays, 50 ns. The pipelined clock is the maximum plus the register, 15 ns, so even for infinitely many instructions the speedup is $50/15 = 3.33$ , well under $k = 5$ , because the stages are unbalanced and the register costs time. For 100 instructions: $T_{pipe} = (5 + 99) \times 15 = 1560$ ns against $100 \times 50 = 5000$ ns.

EX 3How deep should a pipeline be?

Medium

The logic takes 50 ns in total. Split evenly into $k$ stages with a 1 ns register in each:

#include <stdio.h>
 
int main(void) {
    /* 50 ns of logic split evenly into k stages, each pipeline register costing 1 ns */
    double total = 50, reg = 1;
    int ks[4] = {5, 10, 25, 50};
    for (int i = 0; i < 4; i++) {
        double clock = total / ks[i] + reg;
        printf("k = %2d stages: clock %.2f ns, speedup limit %.2f (the ideal would be %d)\n", ks[i], clock, total / clock, ks[i]);
    }
    return 0;
}

k =  5 stages: clock 11.00 ns, speedup limit 4.55 (the ideal would be 5)
k = 10 stages: clock 6.00 ns, speedup limit 8.33 (the ideal would be 10)
k = 25 stages: clock 3.00 ns, speedup limit 16.67 (the ideal would be 25)
k = 50 stages: clock 2.00 ns, speedup limit 25.00 (the ideal would be 50)

Reading it. The speedup limit $T/(T/k + d)$ falls further and further behind the ideal $k$ : at 50 stages the registers eat half of every cycle. It can never exceed $T/d = 50$ . This is the gain side; the cost side is that each stall costs more cycles in a deep pipeline (a 50-stage pipeline loses far more per branch misprediction than a 5-stage one).

EX 4CPI with stalls from branches and loads

Medium

On a 5-stage pipeline, 20% of instructions are branches that cost 3 stall cycles; 25% are loads and 40% of those are followed immediately by an instruction that depends on them, costing 1 stall cycle. What is the CPI and the speedup over a machine with CPI 5 and the same clock?

#include <stdio.h>
 
int main(void) {
    int k = 5;
    /* 20% of instructions are branches costing 3 stall cycles; 25% are loads, 40% of those followed at once by a dependent instruction costing 1 */
    double branch = 0.20 * 3, load = 0.25 * 0.40 * 1;
    double cpi = 1 + branch + load;
    printf("stall cycles per instruction: branches %.2f + loads %.2f\n", branch, load);
    printf("CPI = %.2f\n", cpi);
    printf("speedup over a machine with CPI %d and the same clock: %.3f\n", k, k / cpi);
    printf("efficiency %.1f%% of the ideal speedup %d\n", 100.0 * (k / cpi) / k, k);
    return 0;
}

stall cycles per instruction: branches 0.60 + loads 0.10
CPI = 1.70
speedup over a machine with CPI 5 and the same clock: 2.941
efficiency 58.8% of the ideal speedup 5

Reading it. Stall cycles per instruction are the sum over causes of (frequency) $\times$ (penalty): $0.2 \times 3 = 0.6$ and $0.25 \times 0.4 \times 1 = 0.1$ . CPI $= 1 + 0.7 = 1.7$ and speedup $= 5/1.7 = 2.94$ . The branch penalty dominates, which is why branch handling matters most (forwarding and branch prediction).

EX 5Total cycles with stalls from the diagram

GATE level

In the animation, I3 needs 2 extra cycles in ID and I5 needs 1 extra cycle in ID. The stalls delay all later instructions, so total cycles $= k + n - 1 + s = 5 + 6 - 1 + 3 = 13$ , and the speedup over the non-pipelined machine (30 cycles) is $30/13 = 2.31$ . The rule holds when the stalls happen in one stage, as here. If stalls occur in different stages and overlap in time, the total can be smaller than the plain sum, so draw the diagram instead of using the formula when the question is not as simple as this one. The 13 cycles come from the simulation, not from the formula, and agree with it.

EX 6Time to finish when the question gives the clock

GATE level

A pipeline with 4 stages of delays 8, 10, 6 and 9 ns has 1 ns registers. 50 instructions run with 5 stall cycles in total. Clock $= 10 + 1 = 11$ ns. Cycles $= 4 + 50 - 1 + 5 = 58$ . Time $= 58 \times 11 = 638$ ns. The non-pipelined time is $50 \times (8 + 10 + 6 + 9) = 1650$ ns, so the speedup is $1650/638 = 2.59$ .

Cheat box

$T_{pipe} = (k + n - 1 + s)\,\tau$ ; $T_{non} = n k \tau$ (or $n \sum t_i$ with unequal stages).
Speedup (equal stages, no stalls) $= nk/(k + n - 1) < k$ , tending to $k$ .
$\tau = \max t_i + d_{reg}$ . $S_\infty = \sum t_i / (\max t_i + d_{reg})$ .
Efficiency $= S/k$ . Throughput $= n/T_{pipe}$ .
CPI $_{pipe}$ $= 1 + \sum (\text{frequency} \times \text{penalty})$ . Speedup $= k/\text{CPI}_{pipe}$ for equal clocks and a non-pipelined CPI of $k$ .
Depth: $S_\infty = T/(T/k + d) < T/d$ .
Check formulas with $n = 1$ : pipelined time must equal $k\tau$ .

Traps and GATE patterns

Connections

Builds on

Instruction pipelining

Unlocks

Cache performance and multilevel cachesuses Instruction pipelininguses Structural, data and control hazardsuses Forwarding, stalls and branch predictionuses Performance: CPI, MIPS and Amdahl's lawuses

Across subjects

No cross-subject links yet.

Within this subject

Instruction pipelininguses Structural, data and control hazardsuses Forwarding, stalls and branch predictionuses Performance: CPI, MIPS and Amdahl's lawuses Cache performance and multilevel cachesanalogous-to

The structure being counted is the pipeline. The stall terms come from hazards and are reduced by forwarding and branch prediction. CPI and clock together give execution time, the subject of CPI, MIPS and Amdahl's law; the same "base plus stall" structure appears in cache performance, where memory stall cycles are added to CPI.

PYQs

21 previous year questions from your book. I re-solved each one myself (21 by running or simulating, 0 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2026 · NATQ2 · page 454 of the book

The EX stage of a pipelined processor performs
the memory read operations for LOAD
instructions, and the operations for the arithmetic
and logic instructions. Let tEX denote the time
taken by the EX stage to perform the operation for
an instruction. For each instruction type, the
values of tEX and M (the number of instructions of
that type in a sequence of 100 instructions for a
program P), are given in the table below. The
duration of the pipeline clock cycle is 1
nanosecond. Assume that the latch time for the
interstage buffers in the pipeline is negligible.

When program P is executed, the number of clock
cycles for which the pipeline is stalled due to
structural hazards in the EX-stage is
.
(answer in integer).

GATE 2026 · NATQ3 · page 454 of the book

A non-pipelined instruction execution unit that
operates at 1.6 GHz clock takes an average of 5
clock cycles to complete the execution of an
instruction. To improve the performance, the system
was pipelined with a goal of achieving an average
throughput of one instruction per clock cycle.
However, it could operate only at 1.2 GHz due to
pipeline overheads. While executing a program in
the pipelined design, 30% of instructions
encountered a stall of 2 cycles due to pipeline
hazards. The speed-up obtained by the pipelined
design over the non-pipelined one for this program
is
. (rounded off to two decimal places)
Note: 1G = 109

GATE 2025 · NATQ4 · page 454 of the book

A 5-stage instruction pipeline has stage delays of 180,
250, 150, 170, and 250, respectively, in nanoseconds.
The delay of an inter-stage latch is 10 nanoseconds.
Assume that there are no pipeline stalls due to
branches and other hazards. The time taken to process
1000 instructions in microseconds is
.
(Rounded off to two decimal places)
FDIV
3.2
5
All other
instructions
Less than 1.0
35
Instruction
tEX (in ns)
M
LOAD
1.8
15
IMUL
1.5
10
IDIV
2.5
5
FADD
1.7
10
FSUB
1.7
5
FMUL
2.8
15
Computer Organization and Architecture

GATE 2024 · NATQ7 · page 455 of the book

A
non-pipelined
instruction
execution
unit
operating at 2 GHz takes an average of 6 cycles to
execute an instruction of a program P. The unit is
then redesigned to operate on a 5-stage pipeline at
2 GHz. Assume that the ideal throughput of the
pipelined unit is 1 instruction per cycle. In the
execution of program P, 20% instructions incur an
average of 2 cycles stall due to data hazards and 20%
instructions incur an average of 3 cycles stall due to
control hazards. The speedup (rounded off to one
decimal place) obtained by the pipelined design over
the non-pipelined design is

GATE 2023 · NATQ9 · page 455 of the book

Consider a 3-stage pipelined processor having a
delay of 10 ns (nanoseconds), 20 ns, and 14 ns, for
the first, second, and the third stages, respectively.
Assume that there is no other delay and the
processor does not suffer from any pipeline hazards.
Also assume that one instruction is fetched every
cycle.
The total execution time for executing 100
instructions on this processor is
ns.

GATE 2022 · NATQ10 · page 455 of the book

A processor X1 operating at 2 GHz has a standard 5-
stage RISC instruction pipeline having a base CPI
(cycles per instruction) of one without any pipeline
hazards. For a given program P that has 30% branch
instructions, control hazards incur 2 cycles stall for
every branch. A new version of the processor X2
operating at the same clock frequency has an
additional
branch
predictor
unit
(BPU)
that
completely eliminates stalls for correctly predicted
branches. There is neither any savings nor any
additional stalls for wrong predictions. There are no
structural hazards and data hazards for X1 and X2. If
the BPU has a prediction accuracy of 80%, the speed
up (rounded off to two decimal places) obtained by
X2 over X1 in executing P is
.
Computer Organization and Architecture

GATE 2021 · NATQ12 · page 456 of the book

A five-stage pipeline has stage delays of 150, 120,
150, 160 and 140 nanoseconds. The registers that
are used between the pipeline stages have a delay
of 5 nanoseconds each.
The total time to execute 100 independent
instructions on this pipeline, (assuming there are no
pipeline stalls) is
nanoseconds.

GATE 2020 · NAT · 2 marksQ13 · page 456 of the book

Consider a non-pipelined processor operating at
2.5 GHz. It takes 5 clock cycles to complete an
instruction. You are going to make a 5-stage
pipeline out of this processor. Overheads
associated with pipelining force you to operate the
pipelined processor at 2 GHz. In a given program,
assume that 30% are memory instructions, 60%
are ALU instructions and the rest are branch
instructions. 5% of the memory instructions cause
stalls of 50 clock cycles each due to cache misses

GATE 2018 · NAT · 2 marksQ14 · page 456 of the book

The instruction pipeline of a RISC processor has the
following stages: Instruction Fetch (IF), Instruction
Decode (ID), Operand Fetch (OF), Perform
Operation (PO) and Writeback (WB). The IF, ID, OF
and WB stages take 1 clock cycle each for every
instruction. Consider a sequence of 100 instructions.
In the PO stage, 40 instructions take 3 clock cycles
each, 35 instructions take 2 clock cycles each, and the
remaining 25 instructions take 1 clock cycle each.
Assume that there are no data hazards and no control
hazards.
The number of clock cycles required for completion
of execution of the sequence of instructions is

.

GATE 2017 · NATQ15 · page 456 of the book

Instruction execution in a processor is divided into
5 stages,Instruction Fetch(IF),Instruction
Decode(ID),Operand fetch(OF),Execute
(EX),and Write Back(WB).These stages
take 5,4,20, 10 and 3 nanoseconds(ns)
respectively.A pipelined implementation of the
processor requires buffering between each pair of
consecutive stages with a delay of 2 ns .Two
pipelined implementation of the processor are
contemplated:
i.A naive pipeline implementation(NP)with 5
stages and
ii.An efficient pipeline(EP)where the OF
stage is divided into stages OF1 and OF2 with
execution times of 12 ns and 8 ns respectively.
The speedup(correct to two decimal places)
achieved by EP over NP in executing 20
independent instructions with no hazards is
.
Computer Organization and Architecture

GATE 2016 · NATQ17 · page 457 of the book

Consider a 3 GHz (gigahertz) processor with a
three-stage pipeline and stage latencies τ1, τ2, and τ3
such that τ1 = 3τ2/4 = 2τ3. If the longest pipeline
stage is split into two pipeline stages of equal
latency, the new frequency is
 GHz,
ignoring delays in the pipeline registers.

GATE 2016 · NATQ18 · page 457 of the book

The stage delays in a 4-stage pipeline are 800, 500,
400 and 300 picoseconds. The first stage (with
delay 800 picoseconds) is replaced with a
functionally equivalent design involving two stages
with respective delays 600 and 350 picoseconds.
The throughput increase of the pipeline is percent.

GATE 2015 · NATQ21 · page 457 of the book

Consider a non-pipelined processor with a clock rate
of 2.5 gigahertz and average cycles per instruction of
four. The same processor is upgraded to a pipelined
processor with five stages; but due to the internal
pipeline delay, the clock speed is reduced to 2
gigahertz. Assume that there are no stalls in the
pipeline. The speedup achieved in this pipelined
processor is
,

GATE 2014 · NATQ23 · page 458 of the book

Consider two processors P1 and P2 executing the
same instruction set. Assume that under identical
conditions, for the same input, a program running
on P2 takes 25% less time but incurs 20% more
CPI (clock cycles per instruction) as compared to
the program running on P1. If the clock frequency
of P1 is 1 GHZ , then the clock frequency of P2 (in
GHz ) is    .

GATE 2014 · MCQQ25 · page 458 of the book

Consider the following processors (ns stands for
nanoseconds). Assume that the pipeline registers have
zero latency.
P1: Four – stage pipeline with stage latencies 1ns, 2
ns, 2 ns, 1 ns.
P2: Four-stage pipeline with stage latencies 1ns, 1.5
ns, 1.5 ns, 1.5 ns.
P3: Five-stage pipeline with stage latencies 0.5 ns, 1
ns, 1 ns, 0.6 ns. 1 ns.
P4: Five-stage pipeline with stage latencies 0.5 ns, 0.5
ns, 1 ns, 1 ns, 1.1 ns.
Which processor has the highest peak clock
frequency?

(a)P1
(b)P2
(c)P3
(d)P4

GATE 2014 · NATQ26 · page 458 of the book

Consider a 6-stage instruction pipeline, where all
stages are perfectly balanced. Assume that there is no
cycle-time overhead of pipelining. When an
application is executing on this 6-stage pipeline, the
speedup achieved with respect to non-pipelined
execution is 25% if the instructions incur 2 pipeline
stall cycles is
.

GATE 2011 · MCQ · 2 marksQ29 · page 459 of the book

Consider an instruction pipeline with four stages
(S1, S2, S3 and S4) each with a combinational
circuit only. The pipeline registers are required
between each stage and at the end of the last stage.
Delays for the stages and for the pipeline registers
are as given in the figure:

What is the approximate speed up of the pipeline
in steady state under ideal conditions when
compared to the corresponding non-pipeline
implementation?

(a)4.0
(b)2.5
(c)1.1
(d)3.0

GATE 2007 · MCQ · 2 marksQ35 · page 460 of the book

A non-pipelined single cycle processor operating at
100MHz is converted into a synchronous pipelined
processor with five stages requiring
2.5nsec,1.5nsec,2nsec,1.5nsec and 2.5nsec,
respectively. The delay of the latches is 0.5nsec. The
speedup of the pipeline processor for a large number
of instructions is:

(a)4.5
(b)4.0
(c)3.33
(d)3.0

GATE 2007 · MCQ · 2 marksQ37 · page 461 of the book

A processor takes 12 cycles to complete an
instruction
1.
The
corresponding
pipelined
processor uses 6 stages with the execution times of
3,2,5,4,6 and 2 cycles respectively. What is the
asymptotic speedup assuming that a very large
number of instructions are to be executed?

(a)1.83
(b)2
(c)3
(d)6

GATE 2006 · MCQ · 1 markQ38 · page 461 of the book

A CPU has a five-stage pipeline and runs at a 1
GHz frequency. Instruction fetch happens in the
first stage of the pipeline. A conditional branch
instruction computes the target address and
evaluates the condition in the third stage of the
pipeline.
The processor stops fetching new instructions
following a conditional branch until the branch
outcome is known.
A program executes 109 instructions out of which
20% are conditional branches.
If each instruction takes one cycle to complete on
average, then the total execution time of the
program is:

(a)1.0 second
(b)1.2 Seconds
(c)1.4 Seconds
(d)1.6 Seconds

GATE 2005 · MCQ · 2 marksQ42 · page 462 of the book

We have two designs D1 and D2 for a
synchronous pipeline processor. D1 has 5 pipeline
stages with execution times of 3 nsec, 2 nsec, 4
nsec, 2 nsec and 3 nsec while the design D2 has 8
pipeline stages each with 2 nsec execution time.
How much time can be saved using design D2
over design D1 for executing 100 instructions?

(a)214 nsec
(b)202 nsec
(c)86 nsec
(d)-200 nsec

Self-check

Question 1

A 6-stage pipeline with equal 2 ns stages and no stalls runs 100 instructions. How long does it take and what is the speedup over the non-pipelined machine at the same clock?

Show answer

$(6 + 99) \times 2 = 210$ ns. Non-pipelined: $100 \times 6 \times 2 = 1200$ ns. Speedup $= 1200/210 = 5.71$ .

Question 2

Stage delays 10, 12, 8, 14 ns, register 2 ns. Large- $n$ speedup?

Show answer

Sum $= 44$ ; clock $= 14 + 2 = 16$ ; speedup $= 44/16 = 2.75$ .

Question 3

15% of instructions are branches with a 2-cycle penalty, and 10% are loads with a 1-cycle load-use stall. CPI?

Show answer

$1 + 0.15 \times 2 + 0.10 \times 1 = 1.4$ .

Question 4

With CPI 1.25, a 5-stage pipeline and a non-pipelined machine at CPI 5 on the same clock, what is the speedup?

Show answer

$5/1.25 = 4$ .

Revision card

One-screen revision

$T = (k + n - 1 + s)\tau$ ; non-pipelined $nk\tau$ or $n\sum t_i$ .
$\tau = \max t_i + d_{reg}$ ; $S_\infty = \sum t_i/\tau$ ; $S < k$ .
CPI $= 1 + \sum$ (frequency $\times$ penalty); speedup $= k/$ CPI (equal clocks).
Depth limit: $S_\infty = T/(T/k + d) < T/d$ .
Check with $n = 1$ ; read the baseline.

References

·Hennessy and Patterson, Computer Organization and Design, Chapter 4 The Processor (pipeline performance) and Chapter 1 (performance)
·Hamacher, Vranesic, Zaky, Computer Organization, 5th ed., the Pipelining chapter (performance considerations)
·Stallings, Computer Organization and Architecture, Instruction pipelining chapter (pipeline performance, speedup factor)

Verification

Every number in the worked examples is produced by the C programs on this page (npm run verify:c) and by exact fractions in scripts/enum-checks/coa_pipe.py, which also proves for k up to 8 that the speedup nk/(n + k - 1) is below k, increasing in n and approaches k; the stall diagram's total (k + n - 1 + stall cycles) is re-checked against an independent tick-by-tick simulation (4000 random stall patterns) and by tests/coa-pipe-traces.test.ts. The formulas assume in-order single-issue pipelines with one-cycle stages and a clock set by the slowest stage plus register overhead; superscalar and out-of-order machines are outside this page. Where a book defines speedup against a machine with a different clock or CPI the page states the assumption. Textbook chapter titles are from memory. SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand (long C programs were not re-read line by line: they are compiled and compared by npm run verify:c, and their printed outputs were checked against the prose). No defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Instruction pipelining

Structural, data and control hazards