Project 3 — The Memory Wall Lab

“For where your treasure is, there your heart will be also.” — Matthew 6:21 (ESV)

Chapter: 3 — The Real Bottleneck Due: End of Week 3 Weight: 7% of the course, like every other weekly lab. Submit: A link to a public Git repository containing report.docx, measurements.xlsx, ai-usage.txt, and your raw output files, unmodified. Workbench: Every Normal-tier requirement is completable on Workbench B (a browser-based cloud dev environment, no install, no admin rights) as well as on Workbench L (your own laptop). See Appendix A. No physical device is required anywhere in this project. Allowed tools: A C++17 compiler (g++ or clang++), Python 3 with the standard library only, the chapter’s code/ folder, your own editor, and the textbook. No profiler is required — Chapter 8 owns counters. AI policy: Use AI to explain, never to source. You may ask a model to explain set-associativity, Little’s Law, or why a KV cache grows. You may not take a figure from it. Every number in your deliverables is either measured by you, with the method recorded, or cited to a primary source you actually opened. A number that is neither scores zero on its line; a fabricated number fails the integrity line outright — see Appendix D. Every deliverable ends with the ai-usage.txt note.

The Setup

You have joined a small team building an on-device feature for a mid-range Android tablet — a note-taking application that runs a small language model locally so that nothing a user writes leaves the device. The prototype works on the team’s laptops. On the target hardware it is unusably slow, and the team is split.

One engineer wants to buy time on a device with a faster NPU, on the reasoning that the model is “compute-heavy.” One wants to rewrite the pre-processing pipeline in hand-tuned assembly, on the reasoning that the CPU is at 100% utilization the whole time. One wants to ship a smaller model and hope nobody notices. Nobody has measured anything except a stopwatch and the utilization graph.

You have read Chapter 3, so you suspect all three of them are answering the wrong question — but suspicion is not evidence, and you cannot measure the target hardware this week. What you can do is the thing every good architect does first: build a memory bench you understand completely, on hardware you have in front of you, take real data, learn to read it, and then reason carefully and explicitly about how those results would change on the target class of device.

That is this project. Measure what you can reach. Reason about what you cannot. Never confuse the two.

Setup (the starter)

Everything you need ships with the chapter:

• code/cache_walk.cpp — the strided walk. Sweeps working-set size at a fixed stride and prints ns/access as CSV.
• code/pointer_chase.cpp — the dependent random-cycle chase. Same CSV schema, but it measures latency instead of bandwidth.
• code/matmul_order.cpp — the same matrix multiply in ijk and ikj order, with checksums so you can prove they computed the same thing.
• code/hierarchy_plot.py — reads either CSV, prints an ASCII plot, and flags the steps. Standard library only.
• code/model-memory.csv — synthetic model-footprint data for the Hard tier. Read its first line before you use it.

g++ -O2 -std=c++17 -o cache_walk code/cache_walk.cpp && ./cache_walk    > cache-walk.csv
g++ -O2 -std=c++17 -o chase      code/pointer_chase.cpp && ./chase      > chase.csv
g++ -O2 -std=c++17 -o matmul     code/matmul_order.cpp && ./matmul 512  > matmul.txt

python3 code/hierarchy_plot.py cache-walk.csv
python3 code/hierarchy_plot.py chase.csv

If you did the reps, you already have all of this and most of the write-up. If you skipped them, do them first — the project assumes the bench is already in your hands.

Learning Targets

By completing this project you will demonstrate that you can:

• Build and run a correct memory microbenchmark, including defeating the optimizer, warming up, repeating, and reporting a median with dispersion.
• Infer a cache hierarchy from your own data, stating each boundary as a hypothesis supported by named evidence rather than as a fact you looked up.
• Distinguish a bandwidth result from a latency result, and explain the gap between two curves in terms of prefetching and memory-level parallelism.
• Show that loop order — not instruction count — decides the performance of a memory-bound kernel, and name every mechanism responsible.
• Reason from a machine you have to a machine you do not have, in the vocabulary of The Four Questions, and be explicit about the uncertainty in that reasoning.
• Report honestly: state conditions, separate measurement from model, cite or measure every figure, and name what your data cannot support.

Normal Tier

Goal: Measure your own machine’s memory hierarchy with all three programs, infer its structure from the data, and predict how each result would differ on a phone-class SoC.

Required features

1. Run all three programs, and commit the raw output unmodified. cache-walk.csv, chase.csv, and the matmul_order output go into the repository exactly as the programs produced them, including the # comment lines. Record the exact build command and flags you used. If you are on Workbench B, say so — a shared cloud host is a legitimate measurement condition, and naming it is part of the grade.

2. Predict before you measure, in writing. Before running each of the three experiments, record in measurements.xlsx: where you expect the knees to be, what spread you expect between the fastest and slowest point, and what speedup you expect from ikj. These predictions must be timestamped before the results — that is the honour system, and it is the same honour system a lab notebook has always run on. A project with no predictions loses this line even if every measurement is perfect.

3. Fill in measurements.xlsx properly, per Appendix C. For every experiment: what you ran, on what machine (CPU, RAM, operating system), with which compiler and flags, plugged in or on battery, what else was running, how many repetitions, the median, and a dispersion figure (range or interquartile range across your repetitions). Both C++ programs already take a median of five internally; run each program at least three separate times and report the spread between runs as well. A single number anywhere in this file is an incomplete answer.

4. Infer your cache hierarchy, in report.docx. For each level you believe you found — label them L1, L2, and last-level — give:

   • the capacity boundary (the working-set size on the plateau before the step),
   • the approximate cost per access on that plateau, from both curves,
   • the specific evidence: which rows in which file, and what ratio,
   • your confidence, and what would raise it. State plainly that these are hypotheses. If a boundary is ambiguous — two levels blurring, or a step you cannot explain — say so and say what additional experiment would resolve it. An honest “I can see three plateaus but I cannot tell whether the third is an L3 or a system-level cache” is worth more here than a confident wrong label.

5. Compare the two staircases. Put the strided and chase curves side by side in a table, compute the ratio at the smallest and largest working sets, and explain in your own words what the difference between the curves measures. Attribute the gap correctly: prefetching, memory-level parallelism, or both, and say how you know.

6. Report matmul_order honestly. Give the median seconds for each order, the ratio, and confirmation that the two checksums agree. Then name both mechanisms behind the ikj win and say which you think dominates on your machine and what would settle it. State your optimization level. If you also ran -O3 and the gap changed, report that — it is a real result about your compiler, not a mistake.

7. The graded core: predict the phone. For each of your three results, predict how it would differ on a phone-class SoC and defend the prediction. Each prediction must:

   • name which of The Four Questions it is really about (performance / energy / thermals / placement),
   • state the direction and, where you can justify it, the rough magnitude of the change,
   • give the architectural reason — cache capacities, interface width, LPDDR characteristics, thermal envelope, shared bandwidth — using the hedged figures from the chapter or a primary source you cite,
   • and name what you would need to measure on real hardware to confirm it.

   You are not expected to be right. You are expected to reason in public, with your assumptions visible.

8. A limitations section. At least two things your data cannot support, stated plainly. Candidates: associativity, whether a plateau is an L2 or a system-level cache, whether you were thermally throttled by the last run, whether a shared cloud host gave you a noisy neighbour, whether your compiler vectorized something you did not expect.

9. ai-usage.txt. Which model, for what, and where you overrode or discarded its answer. If you used none, say so and sign it. The format is in Appendix D.

Normal-tier rubric (out of 100)

Medium Tier (+up to 25% extra credit)

M1. Make a cache-hostile kernel fast — without changing its complexity

Create colstats.cpp from the listing below and build it at -O2. It computes the per-column sum and per-column maximum of an N × N row-major matrix, and it is deliberately hostile to the memory system.

// colstats.cpp — the Medium-tier starting point. Deliberately cache-hostile.
// Build: g++ -O2 -std=c++17 -o colstats colstats.cpp     Run: ./colstats [N]
#include <chrono>
#include <cstdio>
#include <cstdlib>
#include <vector>

int main(int argc, char** argv) {
    const int N = (argc > 1) ? std::atoi(argv[1]) : 4096;   // a power of two, on purpose
    std::vector<float> A(std::size_t(N) * N);
    for (std::size_t i = 0; i < A.size(); ++i) A[i] = float((i * 2654435761u) % 1000) * 0.001f;
    std::vector<double> sum(N, 0.0);
    std::vector<float>  maxv(N, -1e30f);

    auto t0 = std::chrono::steady_clock::now();
    for (int j = 0; j < N; ++j)                  // column outer
        for (int i = 0; i < N; ++i) {            // row inner: stride N floats
            const float v = A[std::size_t(i) * N + j];
            sum[j] += v;
            if (v > maxv[j]) maxv[j] = v;
        }
    double s = std::chrono::duration<double>(std::chrono::steady_clock::now() - t0).count();

    double c1 = 0, c2 = 0;
    for (int j = 0; j < N; ++j) { c1 += sum[j]; c2 += maxv[j]; }
    std::printf("N=%d  %.4f s   checksums %.6f %.6f\n", N, s, c1, c2);
    return 0;
}

Your task: make it substantially faster without changing its asymptotic complexity. It is O(N²) and it must stay O(N²) — you may not sample, approximate, skip work, or parallelize across threads. You may change the traversal order, block the loops, pad the row stride, restructure the accumulators, or anything else that leaves the same total work being done on the same data.

Required in report.docx, as a section (not a new file — the deliverable stems in this course are fixed):

1. A diagnosis before a fix. Name, using the chapter’s vocabulary, exactly which memory effects this kernel triggers and why. There is more than one. Compute the useful bytes per line for the inner loop, and say what the choice of a power-of-two N has to do with it.
2. Your optimization, with the code, and a one-paragraph explanation of the mechanism you targeted.
3. Proof. Before-and-after medians with dispersion, at two different values of N — one where the matrix comfortably fits in your last-level cache and one where it does not. Report the speedup at each. The checksums must be unchanged; print them and show that they match, or your “optimization” changed the computation.
4. The honest result. If your best attempt does not help much at one of the sizes, say so and explain why with evidence — a machine whose memory system is already saturated will not reward a locality fix the same way a cache-limited one will. A well-evidenced negative result with a correct explanation earns full credit here. A claimed speedup with no measurement earns none.

Hard Tier (+up to 25% additional extra credit)

H1. The memory-budget memo (the judgment piece)

Write a memo, as a section of report.docx, addressed to the team lead in The Setup. The three engineers want a faster NPU, hand-tuned assembly, and a smaller model respectively. You are going to answer them with arithmetic.

The target device: 6 GB of RAM, of which you may assume roughly 2 GB is unavailable to your process (operating system, other applications, framework and runtime), and a 64-bit LPDDR5X-class interface — use the hedged 8533 MT/s figure from §3.5 and show the bandwidth arithmetic yourself. State every assumption as an assumption.

Using code/model-memory.csv:

1. Disclose the data. Open the file. State in your memo exactly what it is and what that limits — the first line tells you, and Week 8 grades this distinction. Any conclusion you draw is a conclusion about a model, not a measurement of a product.
2. Footprint. Which rows fit in the available budget at 2K context? Recompute the KV cache at 8K context using the §3.10 formula and the layer counts documented in the file’s comment block, and say which rows stop fitting. Show the arithmetic.
3. Bandwidth ceiling. For your candidate rows, compute the bandwidth-bound tokens-per-second ceiling. State clearly that it is an upper bound and list at least three things that will make the real number lower.
4. The recommendation. Choose one precision and one context length, and defend the choice on footprint, bandwidth ceiling, and the user experience the feature actually needs. Then answer each of the three engineers directly and by name of their proposal: is a faster NPU the right purchase? Is hand-tuned assembly going to help a memory-bound kernel? Is a smaller model the same lever as a lower precision, or a different one?
5. What would change your mind. Name the single measurement on real target hardware that would most change your recommendation, and say what result would flip it.
6. What you cannot claim. One short paragraph. You have not measured the target device, and your dataset is synthetic. Say what that means for the confidence of the memo.

A memo that picks the biggest model that fits and stops has missed the point. A memo that reasons from footprint and bandwidth and the cold-start read from storage (§3.11), states its assumptions, and names the experiment that would falsify it — that is the architect’s work, and it is precisely the work that cannot be delegated to a tool that has never seen your device.

Submission

Submit one URL: a public Git repository.

What the repository must contain

1. report.docx — the main write-up: hierarchy inference, staircase comparison, matmul_order analysis, the three phone-class predictions, limitations, plus the Medium and Hard sections if you attempted them.
2. measurements.xlsx — the measurement log, tabular, per Appendix C, including your written predictions.
3. ai-usage.txt — the honest AI disclosure.
4. Raw output — cache-walk.csv, chase.csv, and the matmul_order output, unmodified, plus any Medium-tier output.

Those three document stems are fixed course-wide; do not invent others. If your work needs another document, it is a section of report.docx, which is why both the Medium and Hard tiers above are sections rather than separate files.

A suggested skeleton for the top of report.docx:

# Project 3 — The Memory Wall Lab

**Tier targeted:** Normal / Medium / Hard
**Workbench:** L / B
**Machine:** (CPU, RAM, OS)      **Compiler + flags:** (exact)
**Power state / conditions:** (plugged in? other load? shared host?)

**Inferred hierarchy (hypotheses):**
  L1  ~____ , ~____ ns/access chase, evidence: ____ , confidence: ____
  L2  ~____ , ~____ ns/access chase, evidence: ____ , confidence: ____
  LLC ~____ , ~____ ns/access chase, evidence: ____ , confidence: ____

**Strided vs chase spread:** ____x vs ____x — the difference measures ____
**matmul ijk : ikj:** ____ : ____  (ratio ____ , checksums agree: yes/no, -O2)
**Phone-class predictions:** (one line each; full reasoning below)
**What my data cannot support:** (two items)

Hints (Read Before You Begin)

• Do the reps first. Reps 1, 3, 4 and the “Done? One Last Thing” capstone are the Normal tier, done once already. If you skipped them you will do this project twice.
• Write the predictions down first and do not edit them. It is tempting to “correct” a prediction after seeing the data. Don’t. The wrong predictions are the most valuable lines in your log, because they are the only places you actually learned something.
• Sanity-check every number against the clock. Any per-access time far below one cycle means the optimizer deleted your loop, not that your memory is magical. §3.15’s third pitfall exists because this happens every single term.
• The plotter’s inferred boundaries are a starting point, not an answer. It flags steps above a ratio threshold; tune it with --step and see which boundaries survive. A boundary that appears at one threshold and vanishes at another is exactly the kind of thing your confidence statement should mention.
• Run the chase and the walk when the machine is otherwise quiet, and say whether it was. Then run one of them again while a browser is playing video and note the difference in your log. That contrast is free evidence about measurement conditions, and it will make Chapter 8 much easier.
• On Workbench B, expect more dispersion. You are on shared hardware with neighbours you cannot see. That is not a problem — it is a condition, and reporting it correctly is worth more than a clean number you cannot justify.
• Your phone-class predictions do not need a specific SoC. Reason from the class of device using the chapter’s hedged ranges. If you do name a specific part, every figure about it needs a primary-source citation.
• When you want a number, measure it or cite it. If neither is possible, write the sentence “I could not establish this” and move on. That sentence has never once cost a student a grade in this course. An invented figure has.

What Mastery Looks Like (Beyond the Rubric)

A great Project 3 reads like a lab notebook a colleague could pick up and continue. The predictions are there, unedited, some of them wrong. The conditions are stated so precisely that someone could reproduce the run. The hierarchy inference reads as inference — “the step between 512 KiB and 1 MiB is a factor of 3.1, which is consistent with leaving a level of roughly 512 KiB; I cannot tell from this data whether that level is private or cluster-shared” — rather than as a specification sheet copied from somewhere.

And the phone predictions are where the architecture actually shows. A weak answer says “it would be slower.” A strong one says which result moves, in which direction, for which architectural reason, framed against the right one of The Four Questions, with the confirming measurement named. Best of all is the answer that identifies a result which would move in a surprising direction, and explains why.

Coach’s Note — The engineer who wants a faster NPU is not stupid. He is answering a question about compute because compute is what the dashboard shows him. That is the ordinary shape of the mistake this whole week exists to prevent — not ignorance, but a reasonable person reading the one number that was easy to read. Your job as the architect is not to be cleverer than him. It is to go and get the number that was harder to get, and then to be honest about what it does and does not prove.

When You’re Done

1. Re-open your raw output files and confirm that every number quoted in report.docx is actually in them. Diff it. No transcription errors, no rounded-away dispersion, no figures that appeared from nowhere.
2. Read your hierarchy section back as a skeptic. Is every boundary supported by a specific row of data and a stated confidence? Strike any sentence that asserts a cache size you did not measure and did not cite.
3. Check that measurements.xlsx would let a stranger reproduce your runs: machine, compiler, flags, power state, other load, repetitions, medians, dispersion.
4. (Medium) Confirm your checksums are identical before and after the optimization. If they are not, you changed the computation, and the speedup is not a speedup.
5. (Hard) Re-read the memo and ask: does every figure trace to either the synthetic dataset (disclosed as such), your own arithmetic, or a cited primary source? Strike anything that traces to a memory.
6. Confirm ai-usage.txt is specific. “Used AI for research” is not a disclosure.
7. Commit, push, submit the repository URL.
8. Read Chapter 4 before next week — it is §3.9 with more silicon, and the midterm checkpoint lands.

A theological footnote. “For where your treasure is, there your heart will be also” (Matthew 6:21, ESV). This week you learned to read a machine’s priorities off its behaviour rather than its documentation: what it keeps close, what it re-fetches, what it quietly pays for over and over. A cache is a running argument about what will matter next, made under a limit nobody chose, and the argument is legible in the data whether or not anyone wrote it down. There is a professional discipline in that — the refusal to assume your locality is good, and the willingness to go and measure what you are actually holding near. And there is an older one underneath it, aimed at a different subject. In both cases the failure mode is quiet rather than dramatic: nothing crashes, everything still runs, and the cost is only visible to someone willing to look. Go and look.

See you next week.