Performance engineering begins by defining what is being measured. A processor can be faster in cycles per instruction and slower in wall-clock time if its clock is lower, or faster on one input and slower on another because its memory behavior changes. A credible performance claim names the workload, correctness condition, measurement boundary, resource metric, and baseline. Only then do equations such as CPI, AMAT, Amdahl’s law, and throughput become useful rather than decorative.
Time, instruction count, and CPI
For a program executing instructions, average cycles per instruction and clock frequency idealized CPU time is
The formula is a decomposition, not a causal explanation. depends on compiler, ISA, optimization, and input. CPI depends on pipeline width, hazards, cache behavior, branches, memory-level parallelism, and contention. Frequency depends on critical paths, voltage, temperature, and design point. Improving one term can worsen another.
If a processor retires 3 billion instructions in 1.5 seconds at 2 GHz, then cycles and If a second implementation retires 2.4 billion instructions in 1.4 seconds at 2.5 GHz, its cycles are and CPI is about 1.458. It is faster in wall-clock time despite a worse CPI because it performs fewer instructions and runs at a higher frequency. Reporting CPI alone would reverse the conclusion.
is useful only when represents the relevant frequency and the conditional penalty. Double-counting a miss penalty that is already embedded in a measured CPI produces a false diagnosis.
Pause & Predict: Does lower CPI always imply faster execution? Suppose an optimizing compiler eliminates 50% of the instructions in an inner loop. All eliminated instructions were simple 1-cycle integer additions; all long-latency memory loads remain.
- What happens to the program’s average Does it increase, decrease, or remain constant?
- Does total execution time improve or degrade? Commit your reasoning before opening the analysis below.
Show hintExpandCollapse
Calculate before and after removing 50 fast instructions when 50 slow loads remain.
Reveal analysisExpandCollapse
Analysis: The average actually increases! Suppose the original program had 100 instructions: 50 ALU ops (1 cycle each) and 50 cache-miss loads (20 cycles each).
- Original cycles: cycles. Original
- New program: The 50 ALU ops are eliminated. Remaining instructions: 50 loads.
- New cycles: cycles. New Average nearly doubled from to yet total execution time dropped from 1050 cycles to 1000 cycles. Optimizing for CPI alone is a classic pitfall: total wall-clock time is the only true figure of merit.
Latency, throughput, and queueing
Latency is the time for one operation from request to completion. Throughput is the sustainable completion rate. A pipelined multiplier may have latency four cycles and throughput one result per cycle; a nonpipelined multiplier may have latency and initiation interval both four cycles. A system can have low latency but poor throughput, or high latency with excellent throughput after filling.
Queueing adds waiting time. If a server’s utilization approaches one, small increases in offered load can produce large increases in response latency even when service time is unchanged. A network or memory benchmark that measures only peak bandwidth hides queueing effects and can overstate performance under contention. Tail latency—p95, p99, or higher—matters when a user request depends on many parallel subrequests.
Worked pipeline example. A four-stage unit has 2 ns latency per result after fill and accepts one input every 0.5 ns. For a single request, latency is approximately 2 ns; for 100 independent requests, completion time is ns. A nonpipelined unit with 2 ns service time takes 200 ns. If the requests are dependent, however, the consumer may need to wait for each two-nanosecond result and receive little benefit from throughput.
Benchmark claim under review
One warm benchmark run places CPU A eight percent ahead of CPU B. The report attributes the difference to A's wider pipeline.
Evaluate which evidentiary standards are required before accepting this causal architectural claim:
Latency versus throughput
Evaluate which statements accurately distinguish computational latency from throughput in processor pipelines:
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
Amdahl’s law and bottlenecks
If fraction of the original execution time is improved by factor total speedup is
The unimproved fraction limits the result. If memory accounts for 40% and is made twice as fast, If serialization accounts for 70% and becomes free, the maximum speedup is not infinite.
The fraction must be measured in the baseline execution, not inferred from the fraction of source code or hardware blocks. Improving cache hit rate can reduce memory time but also change overlap with computation; the simple law may need a more detailed model. Gustafson-style scaling asks a different question: as the problem grows with processor count, how much parallel work can be usefully added? Neither law replaces a workload definition.
Expose Amdahl’s serial ceiling
Vary the parallel fraction and processor count; the curve approaches a ceiling fixed by the serial work.
Even abundant parallel hardware cannot remove the execution time of the serial fraction.
Roofline and resource ceilings
For data-intensive kernels, arithmetic intensity is operations per byte transferred from a bottleneck memory level. If peak compute throughput is operations per second and sustainable bandwidth is attainable performance is bounded by
where is arithmetic intensity. A low-intensity kernel is bandwidth-bound; adding arithmetic units does little unless reuse or compression increases effective intensity. A high-intensity kernel is compute-bound until another resource—register capacity, cache bandwidth, instruction issue, or synchronization—becomes limiting.
Worked roofline example. A processor sustains 1 TB/s of relevant memory bandwidth and 4 TFLOP/s peak arithmetic. A kernel performs 2 floating operations per byte, so the bandwidth ceiling is 2 TFLOP/s and the kernel is bandwidth-bound under the model. Doubling peak compute to 8 TFLOP/s changes nothing; doubling reuse to 4 operations per byte raises the bandwidth ceiling to 4 TFLOP/s, at which point peak compute becomes the next ceiling.
Measurement design
A benchmark is an experiment, not a stopwatch call. Define the hypothesis, independent variable, dependent metric, controlled variables, repetitions, warm-up policy, and stopping rule. The timing boundary must exclude setup when measuring steady-state execution and include it when measuring end-to-end user experience. Report distribution and uncertainty, not only the fastest run.
Worked example: an experiment that could falsify a cache claim. Suppose the claim is that 32×32 tiling makes a 1024×1024 double-precision transpose faster because it lowers L1 data-cache misses.
- Hypothesis: tiling reduces L1D miss rate relative to the naive traversal, and that reduction is the mechanism behind any wall-time gain.
- Independent variable: traversal order (naive, 16×16, 32×32, 64×64) with the same matrix and element type.
- Dependent variables: median wall time over repeated runs, L1D and LLC miss rates, and memory bandwidth, measured with hardware counters.
- Controls: identical compiler and flags, single thread pinned to one core, fixed frequency governor, same input values and alignment, warm-up before measurement, and interleaved A/B/B/A ordering to spread thermal and background drift.
- Stopping rule and analysis: report all runs or their median and confidence interval, not the fastest run; use enough repetitions that the interval for the tiled-versus-naive difference is narrower than the effect the claim asserts.
Under the stated hypothesis, either reduced misses without a time improvement or a time improvement without the predicted miss reduction fails to support the proposed mechanism. These observations can suggest another ceiling or cause, such as TLB behavior or code generation, but do not identify it by themselves. Reporting only a warm, best-of-three timing cannot distinguish these cases.
Warm-up may populate instruction/data caches, trigger JIT compilation, stabilize branch predictors, or move a frequency governor. Randomized input order can prevent an algorithm from receiving a pre-sorted favorable trace, but randomization itself must be reproducible and reported.
System-level confounders can dominate small architectural effects. CPU affinity, thread count, background OS load, thermal throttling, compiler optimization flags, and heap allocator behavior must all be tightly pinned and monitored.
Use counters to test mechanisms. If a cache hypothesis predicts that row-major traversal lowers L1 misses, measure misses and bandwidth as well as time. If a branch hypothesis predicts misprediction stalls, measure branch events and compare a branchless variant. Counters are not infallible—multiplexing, sampling, speculative counting, and privilege restrictions matter—but they are stronger evidence than a narrative about “cache friendliness.”
Statistical interpretation
A mean is sensitive to outliers; a median describes a typical run; high percentiles describe tail behavior. Confidence intervals quantify uncertainty under assumptions about sampling, but repeated measurements from the same warmed system are not automatically independent. Effect size matters: a 1% improvement with 0.8% measurement variation is weak evidence unless the experiment is strengthened.
Worked example: a 1% mean gain against run-to-run variation. Five independent baseline runs give a mean of 100.0 ms with sample standard deviation 0.8 ms; five independent variant runs give 99.0 ms with the same standard deviation. The observed difference is 1.0 ms, or 1%.
Treating the runs as independent and approximately normal, the standard error of the difference is ms. A Welch interval with about eight degrees of freedom and gives a 95% interval of roughly ms, or ms. The interval includes zero, so the data do not establish the 1% gain even though the sample mean improved. If the same five input pairs are run in alternating order, the paired differences might be ms: mean 1.0 ms, sample standard deviation 0.16 ms, standard error 0.07 ms, and a 95% interval of about ms, which excludes zero. Pairing removes between-run drift but does not make repeated runs on one warmed machine independent; the report must state which design was used and check for interference. Neither analysis protects against a sample that is too small to represent the workload, and neither says anything about the tail: a 1% mean gain can coexist with a worse p99.
Benchmark suites should include representative and adversarial workloads. A compiler optimization that wins on one synthetic loop may lose on a real application because instruction-cache pressure or code size changes. A cache design that wins on a small working set may lose when the active data exceeds L2. The strongest report explains where the model predicts failure and tests that boundary.
Energy and performance per watt
Performance is not the only constraint. Dynamic energy is related to switching activity, capacitance, and voltage; leakage and static power matter at idle and high density. A higher frequency may require higher voltage and disproportionately increase power.
Memory traffic often consumes more energy than an arithmetic operation. Consequently, a cache optimization can improve both time and energy, or increase energy by fetching large unused lines.
Performance per watt is a ratio with a workload denominator. A design that finishes quickly but uses a high power burst may compare differently from one that runs longer at low power, depending on whether the system is energy-limited, thermally limited, or latency-limited. State the objective before optimizing.
Worked example: voltage-frequency scaling and performance per watt. Consider a simplified dynamic-power model with leakage and static power omitted. A core runs at 2.0 GHz and 1.0 V with W. To reach 3.0 GHz, the design raises the supply to 1.2 V. With IPC and instruction count unchanged, throughput rises by but power rises by to 21.6 W. Performance per watt therefore falls to of its original value, about 31% lower, and energy per instruction rises by or 44%. Including leakage and other static power can change the ratio in either direction: it must be measured or modeled at both operating points. The arithmetic does not prove that the higher frequency is wrong; it proves that the frequency choice must be evaluated against the stated objective, and that a 50% clock increase is not a 50% performance-per-watt increase.
Worked Trace: Multi-Component CPI Stall Decomposition & Frequency Trade-off
Consider evaluating an architectural proposal to deepen a pipeline from 5 stages to 10 stages:
- Baseline Processor (Arch-A): Clock frequency Base
- Branch instructions: 20% of workload, branch penalty is 2 cycles, misprediction rate
- Memory load instructions: 25% of workload, L1 D-cache miss rate miss penalty 40 cycles.
- Proposed Processor (Arch-B): Deeper pipeline allows clock frequency to increase to
- Deeper pipeline increases branch misprediction penalty to 6 cycles.
- Higher frequency increases L1 D-cache miss penalty to 60 cycles (main memory latency in nanoseconds is constant at
Step 1: Compute Effective CPI for Arch-A:
Step 2: Compute Effective CPI for Arch-B:
Step 3: Compare Wall-Clock Execution Time: For an instruction trace of instructions:
Conclusion: Even though Arch-B suffers a 24.2% penalty in CPI due to worse stall penalties in cycles, the 50% frequency increase dominates, producing an overall speedup of (21% faster).
Counterexample & Failure Mode: The MFLOPS / MIPS Mirage (The Algorithm vs Rate Trap)
Can a lower operation count or a higher execution rate mislead an optimization decision? Consider multiplying two dense matrices with
-
Standard Triple-Loop :
- Operations: floating-point operations.
- Execution on a SIMD machine: Highly optimized BLAS achieves 80% peak compute finishing in
-
Strassen’s Sub-Cubic Algorithm :
- Strassen performs 7 recursive multiplications instead of 8, so the number of scalar multiplications is at —about fewer than the naive algorithm’s multiplications. Total floating-point operations also include the 18 matrix additions/subtractions per level; under the common 7-multiplication/18-addition count, Strassen needs about floating-point operations at this size, only about 8% fewer than the naive algorithm’s
- Execution on the same SIMD machine: complex recursive memory layouts, matrix additions, and poor vector-register utilization lower compute efficiency to only 20% peak
- Wall time:
-
The Mirage Breakdown:
- The standard algorithm sustains and finishes in
- Strassen sustains only at this size its operation-count advantage is too small to compensate, so it finishes in about
- The lesson is not that Strassen is always slower. It is that a rate or an asymptotic exponent does not determine wall time: the comparison must count the same operations, include additions and data movement, and use the same implementation efficiency. Reporting as Strassen’s total work silently drops the additions, and reporting as a performance verdict silently drops the algorithm’s cost model.
- Rule: Optimizing for MFLOPS, MIPS, or CPI without fixing the algorithmic work and the instruction count produces invalid engineering decisions.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 4.1.1: CPU Performance Equation Derivation and Analysis
Compute CPU time, cycle count, and CPI from instruction count, frequency, and measured execution time. Explain why a lower CPI does not guarantee lower wall-clock time when instruction count or frequency differs.
HintExpandCollapse
Relate instruction count, cycles per instruction (CPI), and clock cycle time to total execution runtime.
Worked solutionExpandCollapse
Use Cycle count is and CPI is cycles divided by An optimization that reduces CPI by adding simple instructions (raising or lowering clock frequency can increase total execution runtime despite a numerically lower CPI.
Exercise 4.1.2: Amdahl's Law with Multiple Serial and Parallel Bottlenecks
Apply Amdahl’s law to a workload spending 25% of time in memory access, 15% in synchronization, and 60% in compute, when memory access is accelerated by and synchronization by Calculate the overall speedup and identify the limiting bottleneck.
HintExpandCollapse
Compute the maximum achievable speedup when an accelerated component represents a fraction of execution time.
Worked solutionExpandCollapse
The baseline fraction sum is The improved execution time fraction is Overall speedup is The unaccelerated compute portion (60%) now accounts for of total runtime, establishing the primary bottleneck.
Exercise 4.1.3: Roofline Model Kernel Classification and Ceiling Shifts
Using the Roofline model with memory bandwidth peak compute performance and arithmetic intensity explain how to classify a kernel as compute-bound versus memory-bound. What architectural and code transformations raise each ceiling?
HintExpandCollapse
Compare operational intensity times memory bandwidth () against peak arithmetic throughput to classify memory-bound vs compute-bound kernels.
Worked solutionExpandCollapse
Compute the operational throughput boundary If the kernel is memory-bound; if it is compute-bound. Increasing SIMD vector width or FMA units raises the compute ceiling Loop tiling, register blocking, cache reuse, and data compression raise arithmetic intensity shifting the kernel rightward along the bandwidth slope.
Exercise 4.1.4: Experimental Methodology for Cache-Bound Array Traversals
Design a rigorous experimental harness to test whether a 2D matrix traversal is cache-bound. Identify at least five confounding variables and how to control for them.
HintExpandCollapse
Vary working set size across L1/L2/LLC boundaries and control for frequency scaling, page faults, compiler vectorization, and cache warmup.
Worked solutionExpandCollapse
Vary matrix dimensions such that working set sizes span (L1-resident), (L2-resident), (LLC-resident), and (DRAM-bound). Control confounders by: (1) locking CPU clock governor to prevent dynamic frequency scaling; (2) pinning thread affinity to a single core; (3) pre-faulting and warming pages to eliminate page-fault overhead; (4) using identical compiler optimization flags (-O3 -fno-tree-vectorize); and (5) reading hardware performance counters (PAPI_L1_DCM, PAPI_L2_DCM) to confirm cache misses.
Exercise 4.1.5: Average Throughput versus Tail Latency Divergence
Explain how architectural optimizations like batching and aggressive caching can simultaneously improve average throughput while degrading 99th-percentile (p99) tail latency.
HintExpandCollapse
Consider how caching or request batching can accelerate the fast path while queuing complex or evicted requests into high p99/p99.9 percentiles.
Worked solutionExpandCollapse
Batching buffers incoming requests to saturate wide vector units, maximizing throughput at the cost of holding individual early requests in queues, inflating tail latency. Similarly, cache admission policies accelerate common requests but cause tail requests encountering cold evictions or lock contention to stall for milliseconds. System performance evaluation must report percentiles rather than relying exclusively on mean throughput.
Exercise 4.1.6: Pipeline Latency, Initiation Interval, and Throughput Metrics
Distinguish between pipeline latency, initiation interval, throughput, and hardware utilization. Give the exact completion time for independent operations traversing a -stage pipeline with clock period and initiation interval
HintExpandCollapse
Differentiate between total end-to-end service delay (latency), minimum input issue separation (initiation interval), and completions per second (throughput).
Worked solutionExpandCollapse
Latency is total propagation time from issue to retirement Initiation interval is the cycle delay between successive accepted inputs Throughput is retired operations per second Total completion time for operations is For as incremental completion time per operation approaches
Exercise 4.1.7: Benchmarking Methodology Critique: Best-of-Three Reporting
Critique the practice of publishing only the minimum (fastest) elapsed runtime from three experimental runs. Detail why this anti-pattern invalidates scientific reproducibility and prescribe the proper reporting protocol.
HintExpandCollapse
Identify how minimum-of-three filtering suppresses system variance, thermal throttling, OS context switches, and cache eviction noise.
Worked solutionExpandCollapse
Reporting the minimum of three runs censors natural system variance, OS scheduler preemption, thermal throttling, and cache eviction effects, presenting an unrepresentative best-case artifact. The proper protocol requires: performing at least 30 independent iterations after verified cache warmup; reporting median, interquartile range (IQR), and full percentiles (p50, p90, p99); and applying non-parametric statistical tests (e.g. Mann-Whitney U) with confidence intervals.
References & Further Reading
- Hennessy, J. L., & Patterson, D. A. (2019). Computer Architecture: A Quantitative Approach (6th ed.), Chapter 1 (“Fundamentals of Quantitative Design and Analysis”) & Appendix B. Morgan Kaufmann.
- Williams, S., Waterman, A., & Patterson, D. (2009). Roofline: An insightful visual performance model for multicore architectures. Communications of the ACM, 52(4), 65-76.
- Amdahl, G. M. (1967). Validity of the single processor approach to achieving large scale computing capabilities. AFIPS Conference Proceedings, Vol. 30, 483-485.
- Strassen, V. (1969). Gaussian elimination is not optimal. Numerische Mathematik, 13(4), 354–356. https://doi.org/10.1007/BF02165411