Search Knowledge

© 2026 LIBREUNI PROJECT

Computer Architecture/Performance and parallel hardware
Page 13 of 20

Performance Models

CPI, latency, throughput, Amdahl's law, and measurement discipline.

Lesson briefPerformance and parallel hardware · 8 h · 3 outcomes

Required knowledge

  • Programming in a systems language
  • Binary arithmetic and basic digital logic

Learning outcomes

  • Relate instruction count, CPI, frequency, latency, throughput, AMAT, Amdahl, and roofline quantities with units.
  • Identify bottlenecks and sensitivity to workload, serial fraction, bandwidth, and measurement boundaries.
  • Design a reproducible experiment whose counters and uncertainty could falsify the proposed performance model.

Assessment target

Given two implementations and measured counts, compute wall time and model sensitivity, then specify the observation that would overturn the optimization choice.

Scope boundary

  • Silicon-level process simulation (SPICE, transistor threshold voltages, wire RC delays) is abstracted into clock cycle times and setup/hold margins.
  • Non-Uniform Memory Access (NUMA) cache-coherent interconnect topologies are treated in subsequent multicore modules.
  • Speculative side-channel vulnerability modeling (Spectre, Meltdown) is deferred to specialized security modules.

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 ICIC instructions, average cycles per instruction CPICPI and clock frequency ff idealized CPU time is

T=IC⋅CPIf=IC⋅CPI⋅Tcycle.T=\frac{IC\cdot CPI}{f}=IC\cdot CPI\cdot T_{cycle}.

The formula is a decomposition, not a causal explanation. ICIC 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 IC=3⋅109IC=3\cdot10^9 cycles =3⋅109=3\cdot10^9 and CPI=1CPI=1 If a second implementation retires 2.4 billion instructions in 1.4 seconds at 2.5 GHz, its cycles are 3.5⋅1093.5\cdot10^9 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.

CPI=CPIbase+αbrpbr+αloadpload+αL1pL1+⋯CPI=CPI_{base}+\alpha_{br}p_{br}+\alpha_{load}p_{load}+\alpha_{L1}p_{L1}+\cdots

is useful only when α\alpha represents the relevant frequency and pp 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 CPI\text{CPI} Does it increase, decrease, or remain constant?
  • Does total execution time TT improve or degrade? Commit your reasoning before opening the analysis below.
Show hintExpand

Calculate CPI=Cycles/Instructions\text{CPI} = \text{Cycles} / \text{Instructions} before and after removing 50 fast instructions when 50 slow loads remain.

Reveal analysisExpand

Analysis: The average CPI\text{CPI} 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: 50(1)+50(20)=105050(1) + 50(20) = 1050 cycles. Original CPI=1050/100=10.5\text{CPI} = 1050 / 100 = 10.5
  • New program: The 50 ALU ops are eliminated. Remaining instructions: 50 loads.
  • New cycles: 50(20)=100050(20) = 1000 cycles. New CPI=1000/50=20.0\text{CPI} = 1000 / 50 = 20.0 Average CPI\text{CPI} nearly doubled from 10.510.5 to 20.020.0 yet total execution time dropped from 1050 cycles to 1000 cycles. Optimizing for CPI alone is a classic pitfall: total wall-clock time T=IC⋅CPI/fT = IC \cdot \text{CPI} / f 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 2+(99)(0.5)=51.52+(99)(0.5)=51.5 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

0 / 4 answered

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.

1
Pipelining deep instruction execution paths causes latency and throughput to become mathematically identical.
2
Latency measures the total elapsed time required for a single operation to complete from initiation to retirement.
3
High-throughput request batching architectures inherently reduce 99th-percentile tail latency for latency-sensitive queries.
4
Throughput measures the total volume of independent operations successfully completed per unit of time.

Amdahl’s law and bottlenecks

If fraction pp of the original execution time is improved by factor ss total speedup is

S=1(1−p)+p/s.S=\frac{1}{(1-p)+p/s}.

The unimproved fraction limits the result. If memory accounts for 40% and is made twice as fast, S=1/(0.6+0.2)=1.25S=1/(0.6+0.2)=1.25 If serialization accounts for 70% and becomes free, the maximum speedup is 1/0.3≈3.331/0.3\approx3.33 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.

Interactive exploration

Expose Amdahl’s serial ceiling

Vary the parallel fraction and processor count; the curve approaches a ceiling fixed by the serial work.

4.71× speedup
4.71×serial ceiling
Expose Amdahl’s serial ceiling
4.71×serial ceiling

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 PpeakP_{peak} operations per second and sustainable bandwidth is BB attainable performance is bounded by

P≤min⁡(Ppeak,B⋅I),P\le\min(P_{peak},B\cdot I),

where II 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 0.82/5≈0.510.8\sqrt{2/5} \approx 0.51 ms. A Welch interval with about eight degrees of freedom and t0.975≈2.31t_{0.975} \approx 2.31 gives a 95% interval of roughly 1.0±1.171.0 \pm 1.17 ms, or [−0.17,2.17][-0.17, 2.17] 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 [0.8,1.2,0.9,1.1,1.0][0.8, 1.2, 0.9, 1.1, 1.0] ms: mean 1.0 ms, sample standard deviation 0.16 ms, standard error 0.07 ms, and a 95% interval of about [0.80,1.20][0.80, 1.20] 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 Pdyn=αCV2fP_{dyn}=\alpha C V^{2} f with leakage and static power omitted. A core runs at 2.0 GHz and 1.0 V with Pdyn=10P_{dyn}=10 W. To reach 3.0 GHz, the design raises the supply to 1.2 V. With IPC and instruction count unchanged, throughput rises by 3.0/2.0=1.5×3.0/2.0=1.5\times but power rises by (1.2/1.0)2×(3.0/2.0)=2.16×(1.2/1.0)^2 \times (3.0/2.0)=2.16\times to 21.6 W. Performance per watt therefore falls to 1.5/2.16≈0.691.5/2.16 \approx 0.69 of its original value, about 31% lower, and energy per instruction rises by 2.16/1.5=1.442.16/1.5=1.44 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 fA=2.0 GHzf_A = 2.0\text{ GHz} Tcycle=0.5 nsT_{cycle} = 0.5\text{ ns} Base CPI=1.0CPI = 1.0
    • Branch instructions: 20% of workload, branch penalty is 2 cycles, misprediction rate pbr=5%p_{br} = 5\%
    • Memory load instructions: 25% of workload, L1 D-cache miss rate pmiss=8%p_{miss} = 8\% miss penalty 40 cycles.
  • Proposed Processor (Arch-B): Deeper pipeline allows clock frequency to increase to fB=3.0 GHzf_B = 3.0\text{ GHz} Tcycle=0.333 nsT_{cycle} = 0.333\text{ ns}
    • 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 20 ns20\text{ ns}

Step 1: Compute Effective CPI for Arch-A: CPIA=CPIbase+fbr⋅pbr⋅Penaltybr,A+fload⋅pmiss⋅Penaltymem,ACPI_A = CPI_{base} + f_{br} \cdot p_{br} \cdot \text{Penalty}_{br, A} + f_{load} \cdot p_{miss} \cdot \text{Penalty}_{mem, A} CPIA=1.0+(0.20⋅0.05⋅2)+(0.25⋅0.08⋅40)=1.0+0.02+0.80=1.82.CPI_A = 1.0 + (0.20 \cdot 0.05 \cdot 2) + (0.25 \cdot 0.08 \cdot 40) = 1.0 + 0.02 + 0.80 = 1.82.

Step 2: Compute Effective CPI for Arch-B: CPIB=CPIbase+fbr⋅pbr⋅Penaltybr,B+fload⋅pmiss⋅Penaltymem,BCPI_B = CPI_{base} + f_{br} \cdot p_{br} \cdot \text{Penalty}_{br, B} + f_{load} \cdot p_{miss} \cdot \text{Penalty}_{mem, B} CPIB=1.0+(0.20⋅0.05⋅6)+(0.25⋅0.08⋅60)=1.0+0.06+1.20=2.26.CPI_B = 1.0 + (0.20 \cdot 0.05 \cdot 6) + (0.25 \cdot 0.08 \cdot 60) = 1.0 + 0.06 + 1.20 = 2.26.

Step 3: Compare Wall-Clock Execution Time: For an instruction trace of IC=109IC = 10^9 instructions: TA=IC⋅CPIAfA=109⋅1.822.0×109 Hz=0.910 seconds.T_A = \frac{IC \cdot CPI_A}{f_A} = \frac{10^9 \cdot 1.82}{2.0 \times 10^9\text{ Hz}} = 0.910\text{ seconds}. TB=IC⋅CPIBfB=109⋅2.263.0×109 Hz=0.753 seconds.T_B = \frac{IC \cdot CPI_B}{f_B} = \frac{10^9 \cdot 2.26}{3.0 \times 10^9\text{ Hz}} = 0.753\text{ seconds}.

Conclusion: Even though Arch-B suffers a 24.2% penalty in CPI 1.82→2.261.82 \to 2.26 due to worse stall penalties in cycles, the 50% frequency increase 2.0→3.0 GHz2.0 \to 3.0\text{ GHz} dominates, producing an overall speedup of 0.9100.753≈1.21×\frac{0.910}{0.753} \approx 1.21\times (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 N×NN \times N dense matrices with N=1024N = 1024

  1. Standard Triple-Loop O(N3)O(N^3):

    • Operations: 2N3=2(1024)3≈2.15×1092N^3 = 2(1024)^3 \approx 2.15 \times 10^9 floating-point operations.
    • Execution on a SIMD machine: Highly optimized BLAS achieves 80% peak compute 800 GFLOP/s800\text{ GFLOP/s} finishing in 2.68 ms2.68\text{ ms}
  2. Strassen’s Sub-Cubic Algorithm O(N2.807)O(N^{2.807}):

    • Strassen performs 7 recursive multiplications instead of 8, so the number of scalar multiplications is 710≈2.82×1087^{10} \approx 2.82 \times 10^8 at N=1024N=1024—about 3.8×3.8\times fewer than the naive algorithm’s N3N^3 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 1.97×1091.97 \times 10^9 floating-point operations at this size, only about 8% fewer than the naive algorithm’s 2N32N^3
    • Execution on the same SIMD machine: complex recursive memory layouts, matrix additions, and poor vector-register utilization lower compute efficiency to only 20% peak 200 GFLOP/s200\text{ GFLOP/s}
    • Wall time: 1.97×109200×109≈9.9 ms\frac{1.97 \times 10^9}{200 \times 10^9} \approx 9.9\text{ ms}
  3. The Mirage Breakdown:

    • The standard algorithm sustains 800 GFLOP/s800\text{ GFLOP/s} and finishes in 2.68 ms2.68\text{ ms}
    • Strassen sustains only 200 GFLOP/s200\text{ GFLOP/s} at this size its operation-count advantage is too small to compensate, so it finishes in about 9.9 ms9.9\text{ ms}
    • 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 2.82×1082.82 \times 10^8 as Strassen’s total work silently drops the additions, and reporting 200 GFLOP/s200\text{ GFLOP/s} 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 ICIC produces invalid engineering decisions.
Section Exercises

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

Constructionapplication

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.

HintExpand

Relate instruction count, cycles per instruction (CPI), and clock cycle time to total execution runtime.

Worked solutionExpand

Use T=IC⋅CPI/fT = IC \cdot CPI / f Cycle count is T⋅fT \cdot f and CPI is cycles divided by ICIC An optimization that reduces CPI by adding simple instructions (raising ICIC or lowering clock frequency ff can increase total execution runtime TT despite a numerically lower CPI.

Exercise 4.1.2: Amdahl's Law with Multiple Serial and Parallel Bottlenecks

Constructionapplication

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 4×4\times and synchronization by 2×2\times Calculate the overall speedup and identify the limiting bottleneck.

HintExpand

Compute the maximum achievable speedup when an accelerated component represents a fraction of execution time.

Worked solutionExpand

The baseline fraction sum is 0.25+0.15+0.60=1.00.25 + 0.15 + 0.60 = 1.0 The improved execution time fraction is Tnew=0.25/4+0.15/2+0.60=0.0625+0.075+0.60=0.7375T_{\text{new}} = 0.25/4 + 0.15/2 + 0.60 = 0.0625 + 0.075 + 0.60 = 0.7375 Overall speedup is S=1/0.7375≈1.356S = 1 / 0.7375 \approx 1.356 The unaccelerated compute portion (60%) now accounts for 0.60/0.7375≈81.4%0.60 / 0.7375 \approx 81.4\% of total runtime, establishing the primary bottleneck.

Exercise 4.1.3: Roofline Model Kernel Classification and Ceiling Shifts

Descriptionrecall

Using the Roofline model with memory bandwidth BB peak compute performance PpeakP_{\text{peak}} and arithmetic intensity II explain how to classify a kernel as compute-bound versus memory-bound. What architectural and code transformations raise each ceiling?

HintExpand

Compare operational intensity times memory bandwidth (I⋅BI \cdot B) against peak arithmetic throughput to classify memory-bound vs compute-bound kernels.

Worked solutionExpand

Compute the operational throughput boundary I⋅BI \cdot B If I⋅B<PpeakI \cdot B < P_{\text{peak}} the kernel is memory-bound; if I⋅B≥PpeakI \cdot B \ge P_{\text{peak}} it is compute-bound. Increasing SIMD vector width or FMA units raises the compute ceiling PpeakP_{\text{peak}} Loop tiling, register blocking, cache reuse, and data compression raise arithmetic intensity II shifting the kernel rightward along the bandwidth slope.

Exercise 4.1.4: Experimental Methodology for Cache-Bound Array Traversals

Verificationapplication

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.

HintExpand

Vary working set size across L1/L2/LLC boundaries and control for frequency scaling, page faults, compiler vectorization, and cache warmup.

Worked solutionExpand

Vary matrix dimensions such that working set sizes span 8 KB8\text{ KB} (L1-resident), 256 KB256\text{ KB} (L2-resident), 16 MB16\text{ MB} (LLC-resident), and 128 MB128\text{ MB} (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

Descriptionrecall

Explain how architectural optimizations like batching and aggressive caching can simultaneously improve average throughput while degrading 99th-percentile (p99) tail latency.

HintExpand

Consider how caching or request batching can accelerate the fast path while queuing complex or evicted requests into high p99/p99.9 percentiles.

Worked solutionExpand

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

Constructionapplication

Distinguish between pipeline latency, initiation interval, throughput, and hardware utilization. Give the exact completion time for NN independent operations traversing a kk-stage pipeline with clock period τ\tau and initiation interval II=1II = 1

HintExpand

Differentiate between total end-to-end service delay (latency), minimum input issue separation (initiation interval), and completions per second (throughput).

Worked solutionExpand

Latency is total propagation time from issue to retirement k⋅τk \cdot \tau Initiation interval IIII is the cycle delay between successive accepted inputs 1⋅τ1 \cdot \tau Throughput is retired operations per second 1/τ1/\tau Total completion time for NN operations is T(N)=(k+N−1)⋅τT(N) = (k + N - 1) \cdot \tau For N=1N=1 T=kτT = k\tau as N→∞N \to \infty incremental completion time per operation approaches τ\tau

Exercise 4.1.7: Benchmarking Methodology Critique: Best-of-Three Reporting

Generalisationtransfer

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.

HintExpand

Identify how minimum-of-three filtering suppresses system variance, thermal throttling, OS context switches, and cache eviction noise.

Worked solutionExpand

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