Chapter 03 · Reps

The Real Bottleneck — Reps

← Back to Chapter 3

Chapter 3 — Reps

Conditioning, not grading. This week you build a measurement bench, take a real cache staircase off your own machine, and learn to read it — plus the arithmetic that turns “it feels slow” into bytes, nanoseconds, joules and tokens per second.

Ground rules:

  1. Type every command and every line of code yourself. No copy-paste from the chapter. Your fingers need to learn g++ -O2 -std=c++17, the shape of an optimizer barrier, and MT/s × bus bytes cold, because in Week 8 you will be writing your own harness under time pressure.
  2. Run everything. Reading about a cache staircase is not the same as watching one appear in your own terminal. Everything here runs on Workbench L (your laptop) or Workbench B (a browser-based cloud dev environment) with a C++17 compiler and Python 3 — see Appendix A. Nothing here needs a phone.
  3. Predict before you measure. Every measurement rep: write your hypothesis down first — which knee, which direction, how big a multiple — then run it and compare. The gap between prediction and result is the entire information content of the experiment. If you look at the numbers first, you will discover you “expected” them.
  4. Record conditions, always. Every run goes into your measurement log with the machine, the compiler and its flags, whether you were plugged in, what else was running, the repetition count, the median, and the dispersion. The format is in Appendix C. A number without its conditions is not a measurement.
  5. AI policy — explain, never source. You may ask a model to explain a mechanism you did not follow. You may not ask it for a figure. Every number in anything you submit is either measured by you (with the method recorded) or cited to a primary source you actually opened. Rep 10 has you catch a fabrication on purpose. End every AI-touching rep with a one-line AI usage note.

The chapter’s code/ folder has everything you need: code/cache_walk.cpp, code/pointer_chase.cpp, code/matmul_order.cpp, code/hierarchy_plot.py and code/model-memory.csv.

Reps 1–3: Build the Bench and Take the Staircase

Rep 1 — Build the bench and take your first staircase

Build and run the strided walk, then plot it:

g++ -O2 -std=c++17 -o cache_walk code/cache_walk.cpp
./cache_walk > cache-walk.csv
python3 code/hierarchy_plot.py cache-walk.csv

Predict first — write it down before you run anything. Sketch, on paper, the curve you expect: how many flat regions, at roughly which working-set sizes the knees will fall, and the ratio between the fastest and slowest point. You do not need to be right. You need to have committed.

Now run it. Then write four things in your measurement log: (a) how many distinct plateaus you can see, (b) the working-set size at each step, (c) the fastest and slowest ns/access and the ratio between them, and (d) one sentence naming a level you think you found and one sentence saying why you are not certain. That last sentence is the whole discipline — the plotter prints “a hypothesis, not a datasheet” for a reason.

Rep 2 — Change the stride and watch the prefetcher move

Sweep the stride over the same sizes:

for s in 64 128 256 1024 4096; do
  ./cache_walk --stride $s >> stride-sweep.csv
done
python3 code/hierarchy_plot.py stride-sweep.csv

The plotter groups by stride, so you get one staircase per stride. Predict first: which stride will show the steepest DRAM step, and why? Which will look flattest in the L1 region?

Then answer three questions in writing. First: comparing stride 64 against stride 128, is your machine’s cache line 64 bytes or 128? Say which piece of evidence tells you — this is a real inference from your own data, and it is the kind of thing a language model will confidently get wrong about your specific machine. Second: put the stride-128 and stride-4096 curves side by side at your largest working set. The naive translation story says the wide stride must cost more per access, because nearly every access lands on a new page — check whether your data agrees, and report it either way. Then compute, for each stride, the bytes a single pass actually touched (working set ÷ stride × line size) and say what that arithmetic does to the experiment. (§3.8. A sweep that moves two things at once cannot attribute its result to either.) Third: at what stride does the curve stop getting worse, and what does that tell you about how much of each line you were ever using?

Rep 3 — Chase pointers: separate latency from bandwidth

g++ -O2 -std=c++17 -o pointer_chase code/pointer_chase.cpp
./pointer_chase > chase.csv
python3 code/hierarchy_plot.py chase.csv

Predict first: you already have the strided curve from Rep 1. Predict the chase curve’s spread (slowest ÷ fastest) relative to the strided one — bigger, smaller, or about the same? By how much?

Now put the two side by side. In your log, build a three-column table: working-set size, strided ns/access, chase ns/access. Then write:

  • The ratio of chase to strided at the smallest working set and at the largest. Why are these two ratios so different?
  • Which curve’s knees are sharper, and why sharpness is itself evidence about what the hardware is doing.
  • One sentence defining, in your own words, what quantity the difference between these two curves measures. (§3.6. If you cannot answer this, do not move on — it is the most examinable idea in the chapter.)

Reps 4–6: Layout, Loop Order, and the Line

Rep 4 — Loop order: make ijk lose to ikj

g++ -O2 -std=c++17 -o matmul_order code/matmul_order.cpp
./matmul_order 512
./matmul_order 768

Predict first: both orders execute exactly N³ multiply-accumulates on identical data. Write down the speedup you expect from ikj, as a number, before you run it.

Then run it, and confirm the two checksums agree — that is your proof the two loops computed the same thing. Record the median seconds for each order and the ratio at both sizes.

Now the part that separates a good answer from a lazy one. Two distinct mechanisms make ikj faster. Name both, and say which one you think dominates on your machine and what evidence would settle it. Then rebuild at -O3 and run again. Did the gap change? If it shrank sharply, your compiler interchanged the loops for you — record that, because it is exactly the kind of thing that invalidates a benchmark comparison between two people who did not state their flags.

Rep 5 — Array of structs versus struct of arrays

Write this yourself — do not copy it. It is short, and typing it is how the layout difference gets into your hands.

// aos_soa.cpp — build: g++ -O2 -std=c++17 -o aos_soa aos_soa.cpp
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <vector>

struct P { std::uint32_t id; float x, y, z, vx, vy, vz, mass; };
static_assert(sizeof(P) == 32, "expected a 32-byte struct");

int main() {
    const std::size_t N = 4'000'000;          // 128 MB as AoS, 16 MB as SoA
    std::vector<P> aos(N);
    std::vector<std::uint32_t> soa(N);
    for (std::size_t i = 0; i < N; ++i) { aos[i].id = std::uint32_t(i); soa[i] = std::uint32_t(i); }

    double ta = 0, tb = 0; std::uint64_t s1 = 0, s2 = 0;
    for (int rep = 0; rep < 3; ++rep) {       // last pass wins: the first is the warm-up
        auto t0 = std::chrono::steady_clock::now();
        std::uint64_t a = 0; for (const auto& p : aos) a += p.id;
        auto t1 = std::chrono::steady_clock::now();
        std::uint64_t b = 0; for (std::uint32_t v : soa) b += v;
        auto t2 = std::chrono::steady_clock::now();
        ta = std::chrono::duration<double>(t1 - t0).count();
        tb = std::chrono::duration<double>(t2 - t1).count();
        s1 = a; s2 = b;
    }
    std::printf("aos %.4f s (%.1f GB/s)   soa %.4f s (%.1f GB/s)   ratio %.2f   sums %llu %llu\n",
        ta, N * 32.0 / ta / 1e9, tb, N * 4.0 / tb / 1e9, ta / tb,
        (unsigned long long)s1, (unsigned long long)s2);
    return 0;
}

Predict first: compute, by hand, the useful-bytes-per-line ratio for each loop assuming a 64-byte line, and predict the speedup from that ratio alone. Then run it.

Write down your predicted ratio, the measured ratio, and — the interesting part — why they differ. Note the two GB/s figures the program prints: if both loops land near the same achieved bandwidth, then both are memory-bound and the whole difference is bytes moved, which is the cleanest possible demonstration of §3.2. If the SoA figure is much lower, your SoA loop stopped being memory-bound and became limited by something else — say what, and how you would test it.

Two more written answers. Why does this version accumulate a std::uint32_t field into a std::uint64_t rather than summing a float into a double? (Try the float version and watch the ratio collapse. Integer addition is associative, so the compiler is free to vectorize the reduction; floating-point addition is not, so it is stuck with a serial dependency chain — and a loop bound by a dependency chain is not measuring memory at all.) And: name one realistic access pattern for which AoS would be the better layout, and say why. A student who cannot name one has learned a rule instead of an idea.

Rep 6 — Count the useful bytes in a cache line

No code. Paper and head only. Assume a 64-byte line, then redo the last one for a 128-byte line.

For each of the following, compute useful bytes per line and the resulting multiplier on effective bandwidth versus a perfectly packed traversal:

  1. Summing one float field out of a 32-byte struct.
  2. Walking a double array with a stride of 8 elements.
  3. Reading every element of a contiguous std::uint8_t array.
  4. Following a linked list whose nodes are 24 bytes and are allocated in random order.
  5. Summing one float field out of a 32-byte struct, on a machine with 128-byte lines.

Then answer in one sentence each: which of these is the prefetcher able to help with, and which is not? And: for case 4, why does the node size barely matter to the answer?

Reps 7–8: The Arithmetic an Architect Does in Their Head

Rep 7 — The bandwidth arithmetic by hand, then Little’s Law

No tools. Show your working.

  1. Compute the theoretical peak bandwidth of a 64-bit LPDDR interface at 8533 MT/s, in GB/s. Then the same interface at 128-bit and 256-bit widths.
  2. A workload streams 40 MB of data once per frame at 60 frames per second. What sustained bandwidth does it need? What fraction of the 64-bit figure from (1) is that? Would you be comfortable shipping it? Say what else you would need to know before answering.
  3. Little’s Law. With a DRAM latency of 100 ns and 64-byte lines, how many outstanding line requests are needed to saturate the 64-bit interface? Now recompute for the 256-bit interface at the same latency. Write one sentence about what that second number implies for a program that is not aggressively parallel.
  4. From your own Rep 3 data, take the largest working set’s ns/access. Assuming one 64-byte line per access, what achieved bandwidth does the pointer chase reach? Express it as a percentage of the 64-bit theoretical peak. Write one sentence about why that number is not an indictment of the memory system.

Rep 8 — Price a memory access in picojoules

Use the Horowitz ISSCC 2014 figures from §3.9 — 32-bit integer add ≈ 0.1 pJ, 32-bit read from an 8 KB SRAM ≈ 5 pJ, 32-bit DRAM access ≈ 1300–2600 pJ, all at 45 nm — and treat them as orders of magnitude, not exact values.

  1. A kernel performs 4 arithmetic operations per 32-bit element loaded. Estimate the energy per element if every load hits in a small SRAM, and if every load goes to DRAM. What is the ratio?
  2. How many arithmetic operations per loaded word would you need before the arithmetic energy matched the DRAM access energy? Use the low end of the DRAM range, then the high end.
  3. In two sentences, use your answer to (2) to explain why an accelerator designed to increase arithmetic intensity — operations performed per byte fetched — is an energy design and not just a speed design.
  4. State plainly, in one sentence, what these numbers do not tell you. (They are 45 nm figures. What has changed since? What has not? If you cannot support a claim about modern nodes with a source, say so — that is the correct answer.)

Reps 9–10: The AI Workload, and the AI You Cannot Trust

Rep 9 — Budget an on-device model from model-memory.csv

Read the dataset, noticing its first line:

head -n 4 code/model-memory.csv
python3 -c "
import csv
rows=[r for r in csv.DictReader(l for l in open('code/model-memory.csv') if not l.startswith('#'))]
for r in rows:
    if r['model']=='gen-3b':
        print(r['bytes_per_weight'], r['weight_mib'], r['kv_cache_mib_at_2k'], r['total_mib'])
"

Then, by hand:

  1. Verify one row’s weight_mib from parameters_millions × bytes_per_weight. Show the arithmetic. If it does not reconcile to within rounding, say so — a dataset that does not check out is a finding, not a nuisance.
  2. A device has 6 GB of RAM, of which you may assume roughly 2 GB is unavailable to your process (operating system, other apps, framework). Which rows fit? Which fit at 2K context but would not at a much longer context? Use the KV formula in §3.10 to recompute the cache at 8K for one row.
  3. Using the 68 GB/s figure from §3.5, compute the bandwidth-bound token-per-second ceiling for the four gen-7b rows. Write one sentence on what happens to that ceiling as you quantize, and one on why the ceiling is an upper bound rather than a prediction.
  4. Write the sentence you would put in a report to disclose what this dataset is. (Look at the file’s first line. Week 8 grades exactly this.)

Rep 10 — Verify a cache-size claim against a primary source

This rep is about the second AI register in this course, and it is the one that will save your grade.

  1. Pick a real, currently-shipping mobile SoC. Ask a language model for its L2 cache size per core and its memory interface width. Record the answer verbatim, including any confidence language it used.
  2. Now go find a primary source: the vendor’s own specification page, an architecture reference manual, or a published technical document from the vendor. Record the URL and what it actually says. If you cannot find the figure in a primary source, that is your result — record that you could not find it, and do not fill the gap.
  3. Compare. Was the model right, wrong, or unverifiable? Note the difference between those three outcomes, because they are not the same and only one of them is safe.
  4. Now do the same exercise on your own machine: ask the model for your laptop’s L1 and last-level cache sizes, then compare against the knees you measured in Rep 1 and Rep 3. Which source would you trust in a report, and why?
  5. Write two sentences on what a fabricated figure would have cost you if it had reached a submitted deliverable. (Appendix D treats it as an integrity failure, not a deduction — make sure you know that before Sunday.)

AI usage: required for this rep. Name the model and version, quote what it told you, and state plainly whether the primary source confirmed it.

Done? One Last Thing.

This is the project in miniature — infer a hierarchy from your own data and defend it.

Using only cache-walk.csv and chase.csv from Reps 1 and 3, write a one-page inference:

  1. The hierarchy you think you measured. For each level you believe you found: the capacity boundary (the working-set size just before the step), the approximate ns/access on the plateau, and the specific evidence in your data. Number them L1, L2, and last-level.
  2. Your confidence, per level, with a reason. Which boundaries are sharp and which are ambiguous? Where might two levels be blurring together, and what additional measurement would separate them?
  3. The conditions. Machine, compiler and flags, plugged in or on battery, what else was running, repetitions, median and dispersion. Per Appendix C.
  4. One phone-class prediction. Pick one of your three results and predict how it would differ on a phone-class SoC. Name which of The Four Questions your prediction is really about, and state what you would need to measure to confirm it.
  5. One honest limitation. Name a thing your data cannot tell you. (Candidates: associativity, whether a plateau is an L2 or a system-level cache, whether you were thermally throttled by the tenth run, whether Workbench B put you on a shared host with noisy neighbours.)

Keep this write-up. It is the spine of the report.docx the project asks for — you have already drafted it.

Up next: Project 3 — The Memory Wall Lab — measure your own machine, infer its hierarchy, and predict the phone.