UN

The Formula Toolkit

Memorize every one of these. They are all just ways to compute execution time.

1. Performance & "n times faster"
Performance=1Execution time\text{Performance} = \frac{1}{\text{Execution time}}
X is n× faster than Y  ⟹  PerfXPerfY=TimeYTimeX=nX \text{ is } n\times \text{ faster than } Y \;\Longrightarrow\; \frac{\text{Perf}_X}{\text{Perf}_Y} = \frac{\text{Time}_Y}{\text{Time}_X} = n
(the slower machine's time goes on top)
2. Clock
T=1FF=1TT = \frac{1}{F} \qquad F = \frac{1}{T}
1 MHz=106 Hz1\,\text{MHz} = 10^{6}\,\text{Hz}, 1 GHz=109 Hz1\,\text{GHz} = 10^{9}\,\text{Hz}
3. CPU Execution Time — Equation I
CPU time=CPU clock cycles×cycle time=CPU clock cyclesclock rate\text{CPU time} = \text{CPU clock cycles} \times \text{cycle time} = \frac{\text{CPU clock cycles}}{\text{clock rate}}
4. CPI (Cycles Per Instruction)
CPI=total clock cyclesinstruction countTotal clock cycles=IC×CPI\text{CPI} = \frac{\text{total clock cycles}}{\text{instruction count}} \qquad \text{Total clock cycles} = \text{IC} \times \text{CPI}
5. CPU Execution Time — Equation II (master equation)
CPU time=IC×CPI×T=IC×CPIclock rate\text{CPU time} = \text{IC} \times \text{CPI} \times T = \frac{\text{IC} \times \text{CPI}}{\text{clock rate}}
Three levers: instruction count, CPI, clock rate.
6. Weighted / Average CPI
Total cycles=∑iCPIi×Ci\text{Total cycles} = \sum_i \text{CPI}_i \times C_i
Average CPI=∑iCPIi×Ci∑iCi\text{Average CPI} = \frac{\sum_i \text{CPI}_i \times C_i}{\sum_i C_i}
With percentages: Average CPI=∑ifractioni×CPIi\text{Average CPI} = \sum_i \text{fraction}_i \times \text{CPI}_i
7. MIPS (Million Instructions Per Second)
MIPS=Instruction countExecution time×106\text{MIPS} = \frac{\text{Instruction count}}{\text{Execution time} \times 10^{6}}
⚠ Higher MIPS does NOT always mean faster. Trust execution time.
8. Amdahl's Law
New time=Unaffected+AffectedrSpeedup=OldNew\text{New time} = \text{Unaffected} + \frac{\text{Affected}}{r} \qquad \text{Speedup} = \frac{\text{Old}}{\text{New}}
If fraction ff is sped up by rr:
Speedup=1(1−f)+fr\text{Speedup} = \frac{1}{(1 - f) + \dfrac{f}{r}}
Max speedup (r→∞)=11−f=OldUnaffected\text{Max speedup } (r \to \infty) = \frac{1}{1 - f} = \frac{\text{Old}}{\text{Unaffected}}
Make the common case fast.
Unit cheat sheet:ps=10−12\text{ps} = 10^{-12} · ns=10−9\text{ns} = 10^{-9} · µs=10−6\text{µs} = 10^{-6} · ms=10−3\text{ms} = 10^{-3} · MHz=106\text{MHz} = 10^{6} · GHz=109\text{GHz} = 10^{9}. If you're given GHz (a rate) divide by it; if given ps/ns (a time) multiply.