What “faster” means: the Iron Law, Amdahl and pipeline arithmetic

Time is the only honest metric

Whether you are buying a machine or designing one, you need a basis for comparison and a metric. The notes name two metrics, and they pull in opposite directions. Execution time (also called latency or response time) is the time needed to complete one task: lower is better. Throughput (bandwidth) is the number of tasks completed per unit of time: higher is better.

The notes' Example 1 (p. 246) is a pair of aircraft. Concorde flies at 1350 mph and crosses from Washington to Paris in 3 hours; a Boeing 747 flies at 610 mph and takes 6.5 hours. On execution time Concorde wins; on throughput, passenger-miles per hour, the 747 wins, because it carries far more people per flight. Optimising one metric can hurt the other. This lesson is about one processor running one program, so execution time is the metric; pipelining, in the last section, is a throughput technique that makes no single instruction finish sooner.

Performance is the reciprocal of execution time, and "X is \(n\%\) faster than Y" is defined as a ratio: the time of the slower machine is \(1 + n/100\) times the time of the faster one. Example 2 of the notes (p. 247): machine A runs a program in 10 s, machine B in 15 s. Is A 50% faster or 33% faster? Compute the ratio, \(15/10 = 1.5\), so A is 50% faster. The 33% is the time A saves as a fraction of B's time, \((15 - 10)/15\); it is a true number, but it is not what "faster" means in this course or in Hennessy & Patterson. "X is \(k\) times faster than Y" is the same ratio without the percentage: \(k = \text{Time}(Y)/\text{Time}(X)\).

A processor executes synchronously to a clock. The clock cycle time \(T_{CLK}\) is the duration of one cycle, in seconds; the clock frequency \(f_{CLK} = 1/T_{CLK}\) is the number of cycles per second, in hertz. The notes write \(f_{clock}\) on some pages and \(f_{CLK}\) on others; the exam's formula sheet writes \(f_{CLK}\), and so does this lesson.

Performance is the reciprocal of execution time, and "n% faster" is a ratio of times, never a difference.

The Iron Law: three numbers that multiply

Think of typing a letter. The time it takes is the number of words, times the keystrokes each word needs, times the seconds each keystroke takes. Three factors, three different people responsible: the author decides the words, the keyboard layout decides the keystrokes per word, the typist's fingers decide the seconds per keystroke. A typist twice as fast on a layout that needs 2.5 times more keystrokes per word is the slower typist.

A processor is the same product. The CPU time of a program is the number of clock cycles it takes, times the cycle time; and the number of cycles is the number of instructions executed, times the average number of cycles per instruction. (CPU time is the processor's own time on the program; the elapsed, wall-clock time adds I/O and other programs. The notes use the two names as one on p. 248; the exam asks for CPU time.)

The levers in the figure are background from Hennessy & Patterson, not from the notes: the compiler and the instruction set decide IC; the organisation (pipeline, caches, how many instructions issue per cycle) and the instruction set decide CPI; the technology and the pipeline depth decide \(T_{CLK}\). Only the product is performance, which is why architects argue in seconds and not in megahertz.

CPI, IPC and the instruction mix

CPI is the average number of clock cycles each instruction takes: total clock cycles divided by \(IC\). Its reciprocal, IPC (instructions per cycle), is the number of instructions that complete per cycle; the two say the same thing, and you will meet IPC again when a machine can finish more than one instruction per cycle.

A real program is a mix of instruction classes with different costs: a load may take 4 cycles where an ALU operation takes 1. The average CPI must weight each class by how often it occurs. Here is where the weighted form comes from.

1. Count the cycles class by class: \(I_i\) instructions of class \(i\), each taking \(CPI_i\) cycles. The program's total cycles are the sum over the classes (the bracket of the notes' eq. 16):

   \[ \text{Clock cycles} = \sum_{i=1}^{n} CPI_i \, I_i . \]

2. Divide by the instruction count to get the average cycles per instruction:

   \[ CPI = \frac{\sum_i CPI_i\, I_i}{IC} = \sum_i CPI_i \,\frac{I_i}{IC} . \]

3. The ratio \(I_i / IC\) is the frequency \(F_i\) of class \(i\): the fraction of the executed instructions that belong to it. The frequencies sum to 1. That gives the formula-sheet form (eq. 19–20):

   \[ CPI = \sum_{i=1}^{n} CPI_i\, F_i , \qquad F_i = \frac{I_i}{IC} . \]

4. Put it back into the Iron Law and the two routes agree: \(IC \times CPI\) with the weighted CPI is exactly \(\sum_i CPI_i\, I_i\), the class-by-class cycle count, so both give the same CPU time once multiplied by \(T_{CLK}\).

The notes' Example 3 (pp. 249–250) is the first instance: 100 instructions at 500 MHz with this mix.

CPI is \(2.23\), and the time is \(100 \times 2.23 \times 2\) ns \(= 446\) ns: 223 cycles of 2 ns each. Nothing was added for a pipeline fill, because this is the general bookkeeping: the cycles per class already include whatever each class costs.

The exam's version: CPU1 against CPU2

Exercise 3 of the 10 June 2025 paper is this same table, twice. CPU1 runs at 500 MHz, CPU2 at 200 MHz; both execute a kernel of 100 instructions with the frequencies and cycle counts below. The paper asks for the average CPI of each CPU, the CPU time of each, and "how much is CPU1 faster than CPU2?". The two right-hand columns are the ones you add on the answer sheet.

\(CPI_1 = 2.7\) and \(CPI_2 = 2.4\): CPU2 has the better CPI. Now the cycle times: 500 MHz is 2 ns, 200 MHz is 5 ns. \(\text{CPUtime}_1 = 100 \times 2.7 \times 2\) ns \(= 540\) ns; \(\text{CPUtime}_2 = 100 \times 2.4 \times 5\) ns \(= 1200\) ns. CPU1 is \(1200/540 = 2.22\) times faster, that is 122% faster in the formula sheet's \(n\%\) form. The first puzzle of the hook is solved: the clock is 2.5 times faster, but the CPI is \(2.7/2.4 = 1.125\) times worse, and \(2.5 / 1.125 = 2.22\). Look at the ALU and LOAD rows to see where the worse CPI comes from: an ALU operation costs 2 cycles instead of 1, a load 8 instead of 6. A faster clock means more, shorter cycles for the same work, and memory does not get faster when the clock does. That trade-off is the whole memory block of this course, from lesson 22 on.

CPU time = IC × CPI × T_CLK: a change in any one factor is worth exactly as much as the same change in any other.

MIPS: a rate of instructions, not of work

MIPS, millions of instructions per second, is the throughput of instructions. The notes give two equivalent forms (eq. 21–22), and you should be able to pass from one to the other: substitute \(\text{CPU time} = IC \times CPI / f_{CLK}\) into the second and the \(IC\) cancels.

Why do the notes warn that "higher MIPS does not necessarily mean better performance"? Because MIPS does not account for what an instruction does. Hennessy & Patterson's classic case (background, not in the notes) is a machine with optional floating-point hardware. With floating point emulated in software a program executes 10 million instructions at CPI 1.2 on a 1 GHz clock: 12 ms, 833 MIPS. With the FP unit the same program is 4 million instructions at CPI 2.5: 10 ms, 400 MIPS. The faster configuration has the lower MIPS, because each of its instructions does more. That is the third puzzle of the hook. In general MIPS depends on the instruction set, varies from program to program on the same machine, and can even vary inversely with performance.

When is MIPS harmless? When the two machines run the same program with the same instruction set, so that \(IC\) is the same: then the MIPS ratio equals the ratio of the times. The June 2025 pair is that case, \(185/83 = 2.22\), the same 2.22 as before. In the exam, compute the CPU times anyway: that is what the question asks for, and the time ratio is the definition of "faster".

Amdahl's law: only the fraction moves the ceiling

A 60-minute commute: 24 minutes (40%) on the motorway, 36 minutes on city streets. You buy a car ten times faster on the motorway. The motorway part shrinks from 24 minutes to 2.4; the city part stays 36; the trip now takes 38.4 minutes. Speedup: \(60/38.4 = 1.56\). Now imagine a teleporter for the motorway. The trip still takes 36 minutes: speedup 1.67. Nothing you do to the motorway can beat 1.67. To go faster you must attack the 36 minutes you did not touch.

That is Amdahl's law. \(F\) is the fraction of the original execution time affected by the enhancement, \(S\) the speedup of that part alone. The notes give the result; here is where it comes from.

1. Call the old execution time \(T\). The enhancement touches a part worth \(F\,T\); the rest, \((1 - F)\,T\), is untouched.

2. The touched part becomes \(S\) times faster, so it now takes \(F\,T / S\). The new time is the notes' eq. 23:

   \[ T' = (1 - F)\,T + \frac{F\,T}{S} \] \[ T' = \Big[(1 - F) + \frac{F}{S}\Big]\, T . \]

3. The overall speedup is old time over new time; \(T\) cancels (eq. 24):

   \[ \text{Speedup} = \frac{T}{T'} = \frac{1}{(1 - F) + \dfrac{F}{S}} . \]

4. Let \(S \to \infty\): the term \(F/S\) vanishes and only the untouched part is left (eq. 26). This is the ceiling, and it depends on \(F\) alone:

   \[ \text{Speedup}_{\max} = \frac{1}{1 - F} . \]

5. The inverse question, "which \(F\) do I need for a target speedup with a given \(S\)?": solve eq. 24 for \(F\).

   \[ F = \frac{1 - \dfrac{1}{\text{Speedup}}}{1 - \dfrac{1}{S}} . \]

The notes' Example 4 (p. 252) is the commute in disguise: a unit 10 times faster on computation, and the CPU busy with computation 40% of the time. \(1/(0.6 + 0.04)\), that is \(1/0.64 = 1.5625\), about 1.56; with \(S \to \infty\), \(1/0.6 = 1.67\). "Even if the improvement is 10×, the overall speedup is only about 1.56×." The two bars below are the before and after of this example.

The exam likes the inverse question. The quiz of 8 January 2026, as the notes' exam chapter reproduces it (pp. 502–503), asks which fraction of the execution time must be enhanced, with \(S = 10\), to obtain an overall speedup of 4. Step 5 of the derivation:

that is about 83%. Not 40%, and not "4/10": almost the whole program has to be touched.

Hence the design rule the notes state, make the common case fast: it is \(F\), not \(S\), that decides. A modest 1.5× on 90% of the time gives \(1/(0.1 + 0.6) = 1.43\); a spectacular 100× on 20% of the time gives \(1/(0.8 + 0.002) = 1.25\). And the returns diminish: once the touched part is small, every further improvement of it is worth less, and the untouched part is the new bottleneck.

You will meet the same formula once more, near the end of the course: on a multiprocessor \(F\) is the fraction of the program that runs in parallel and \(S\) the number of cores, and 95% parallel code on 100 cores gives \(1/(0.05 + 0.0095) = 16.8\), not 100.

Speedup = 1 / ((1 − F) + F/S), never above 1 / (1 − F): the part you did not improve sets the ceiling.

Pipeline arithmetic: cycles = IC + 4 + stalls

Lesson 1 built the five-stage pipeline; this section counts its cycles the way the exam does. First, what pipelining buys and what it does not. It increases instruction throughput: once the pipeline is full, one instruction completes per cycle. It does not reduce the latency of a single instruction, which still walks through all five stages; in fact the latency grows slightly, for two reasons the notes list on p. 253. Imbalance among the stages: the clock cycle must fit the slowest stage, so the faster stages idle for part of every cycle. Overhead of pipeline control: the pipeline registers between the stages, their set-up time and the clock skew add to every cycle. So \(T_{CLK}\) must be at least the time of the slowest stage plus the register overhead (the notes write a plain "greater than"); that overhead is why five stages do not divide the cycle by five. Designers balance the stages, and sometimes split a slow one in two, which is how pipelines get deeper.

One iteration, counted by hand

Take the kind of loop body every exam paper uses, numbered I0 to I4 as the papers number instructions (older papers write $F2 and $R1; the 2026 paper drops the dollar sign, and so does this course).

LOOP: LD    F2, 0(R1)     ; I0
      FADD  F4, F2, F2    ; I1
      SD    F4, 0(R1)     ; I2
      ADDUI R1, R1, 8     ; I3
      BNE   R1, R2, LOOP  ; I4

Machine assumptions, stated the way a paper states them: the 5-stage pipeline IF ID EX ME WB of lessons 1 and 2 with forwarding; one instruction fetched per cycle; the FADD occupies EX for one cycle like any ALU operation (lesson 7 gives floating point its own longer pipeline); \(m = 5\) instructions per iteration and \(k = 2\) stall cycles per iteration: one load-use stall at I1 (the FADD needs F2 one cycle too early) and one branch stall at I4. Why exactly those two is the business of lesson 2 and lesson 4; here only their number matters. First the iteration as if nothing stalled.

Now the real iteration, with its two stalls. The load-use bubble holds I1 in ID during cycle 4 and freezes everything behind it; the branch stall does the same in cycle 8. Each stall pushes every later write-back one cycle to the right.

Count the last write-back: cycle 11. In general, instruction number \(j\) is fetched in cycle \(j\) plus the stalls before it and completes four cycles later, so the last of \(IC\) instructions completes in cycle \(IC + 4 + \text{stalls}\). This is the counting rule of the course, the notes' eq. 2 and eq. 27, and it is on the formula sheet with the same "+4".

The notes' Example 6 (p. 28, repeated as Example 5 on p. 254) has exactly the numbers of this iteration: \(IC = 5\), 2 stall cycles, 500 MHz. Cycles \(5 + 2 + 4 = 11\); \(CPI = 11/5 = 2.2\); \(\text{MIPS} = 500/2.2 = 227\). And without the stalls? Not CPI 1.

Use the "+4" when the question is about the 5-stage pipeline: "how many cycles, which CPI, which MIPS for this code with or without forwarding". The other families of exercises count differently.

Loops: one iteration against the whole run

A loop with \(m\) instructions per iteration, \(k\) stall cycles per iteration and \(n\) iterations is the exam's favourite shape, and the formula sheet carries two sets of numbers for it. The per-iteration figures treat one iteration as if it ran alone, fill included (notes eq. 30–33): \(IC_{iter} = m\), cycles \(= m + k + 4\), \(CPI_{iter} = (m + k + 4)/m\), and MIPS from that CPI. For the loop above: 11 cycles and \(CPI_{iter} = 2.2\), the numbers you just counted. The whole run is different, because the fill is paid once, not \(n\) times.

1. Over \(n\) iterations the instruction count is \(IC = m\,n\). Each iteration costs its \(m\) issue cycles and its \(k\) stall cycles; the fill is paid once (eq. 34–35):

   \[ \text{Clock cycles} = m\,n + k\,n + 4 . \]

2. Divide by the instruction count. The exact CPI of the run depends on \(n\):

   \[ CPI(n) = \frac{m\,n + k\,n + 4}{m\,n} \] \[ CPI(n) = 1 + \frac{k}{m} + \frac{4}{m\,n} . \]

3. Let \(n \to \infty\): the last term, the fill spread over all the instructions, goes to zero (eq. 36). What remains is the asymptotic CPI, which the formula sheet writes \(CPI_\infty = CPI_{AS}\):

   \[ CPI_{AS} = \frac{m + k}{m} = 1 + \frac{k}{m} \] \[ \text{MIPS}_{AS} = \frac{f_{CLK}}{CPI_{AS} \times 10^6} . \]

4. Read the result: \(k/m\) is the number of stall cycles per instruction. So the asymptotic CPI of a loop is "1 + stall cycles per instruction", the realistic CPI of the notes' eq. 39, and the only way to improve it is to cut \(k\) or to make \(m\) larger for the same \(k\).

Ideal and realistic CPI, and the speedup of a pipeline

The notes close the chapter with two short formulas (eq. 38–39): the ideal CPI of a pipelined processor is 1, one instruction per cycle after the fill; the realistic CPI is \(1 + \) stall cycles per instruction, and the stalls come from four sources: structural hazards (a resource conflict), data hazards (a dependence), control hazards (a branch) and memory stalls (a cache miss). You have just seen the same formula as \(1 + k/m\). One correction to that page is worth points.

How much does a pipeline buy? Compare the average time per instruction on an unpipelined machine with the pipelined one. The notes' p. 256 derives it in four lines; one of them is misprinted.

1. By definition (eq. 40), the speedup is the ratio of the average execution times per instruction, and each is a CPI times a cycle time (the instruction count is the same and cancels):

   \[ \text{Speedup} = \frac{CPI_{unp} \times T_{clk,unp}}{CPI_{pipe} \times T_{clk,pipe}} . \]

2. Ignore the register overhead and assume balanced stages: the two cycle times are equal and cancel too. What is left is the ratio of the CPIs, and the pipelined CPI is \(1 + \) stall cycles per instruction (eq. 41, corrected):

   \[ \text{Speedup} = \frac{CPI_{unp}}{CPI_{pipe}} \] \[ \text{Speedup} = \frac{CPI_{unp}}{1 + \text{stalls / instruction}} . \]

3. Assume every instruction takes the same number of cycles on the unpipelined machine, and that this number is the number of stages (the stages are the same work, done one after the other). Then \(CPI_{unp}\) is the pipeline depth (eq. 42):

   \[ \text{Speedup} = \frac{\text{depth}}{1 + \text{stalls / instruction}} . \]

4. With no stalls the speedup is the depth (eq. 43): a 5-stage pipeline can give at most 5×, and only without stalls, with balanced stages and with no register overhead. For the loop above, \(k/m = 0.4\): \(5/1.4 = 3.57\); with one stall removed, \(5/1.2 = 4.17\).

5. If the only stalls are branch stalls, the stall cycles per instruction are the branch frequency times the branch penalty (eq. 44–45, "PSCIB"):

   \[ \text{Speedup} = \frac{\text{Pipeline depth}}{1 + b \times p} . \]

   With 20% branches costing 3 cycles each, \(5/1.6 = 3.125\); cut the penalty to 1 and the pipeline is back to 4.17. That is the next lesson's job.

Why do deeper pipelines not simply give bigger speedups? Two reasons hidden in the assumptions. Each new stage adds its register overhead to the cycle, so the clock does not shrink in proportion. And the stall penalties grow with the depth: a branch resolved \(p\) stages after fetch costs \(p\) cycles, a load's value appears later in a longer pipeline. The arithmetic that promises depth-fold speedups charges for the depth in the denominator.

Back to the three puzzles

CPU1 beats CPU2 with the worse CPI because CPU time is \(IC \times CPI \times T_{CLK}\): the clock factor, 2.5, beats the CPI factor, 1.125, and their quotient is 2.22. It is not 2.5 times faster because its instructions cost more cycles on the faster clock, the CPI factor again. And the 833-MIPS machine loses because MIPS counts instructions, and it executes 2.5 times more of them for the same work. Three puzzles, one formula.

Cycles = IC + 4 + stalls, paid once for the fill and once per stall; for a loop the fill fades and CPI → 1 + k/m.