Loading page…
Master the fundamental concepts of cache optimization through this focused micro-challenge.
You have read the whole brief, and the concepts above stay free on every task. Writing and running the code needs a plan.
Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it worksIntel's PREFETCHT0/PREFETCHNTA instructions move data into cache hierarchy levels with different temporal hints. PREFETCHNTA targets streaming data with minimal cache pollution. Assembly kernels in BLAS and video codecs use these when compilers cannot infer access patterns.
PREFETCHT0 brings data close for reuse. PREFETCHNTA treats data as non-temporal, helpful for one-pass scans. Mis-tuned prefetch still costs retirement bandwidth.
nasmLoading…
perf stat -e L1-dcache-load-misses before and afterKeep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.
You will write a small assembly or intrinsic loop that issues PREFETCHT0 ahead of loads and report timing impact. This exercise requires explaining when hardware prefetch already covers the access pattern.
Hardware prefetchers watch the stream of loads, per instruction (PC), and predict the next address when a PC keeps stepping by the same stride. Implement the classic reference prediction table (Chen & Baer). Run it on generated address traces, and compare cache misses with and without it. Arrays stride nicely, two interleaved arrays need per-PC tracking, and a linked list defeats it completely. That last case is why software prefetching and data layout still matter.
cLoading…
run simulates the whole trace twice from an empty cache: without a prefetcher, then with one. A prefetch fills its line immediately (this measures coverage, not timing). It counts as issued only if the line was not already cached. A prefetched line counts as useful the first time a demand access hits it.PC mod N. If the entry is empty or holds another PC, (re)allocate it with last = addr, stride = 0, initial, and do not predict.delta = addr - last:| State | delta == stride | delta != stride |
|---|---|---|
| initial | steady | transient, stride = delta |
| transient | steady | no-pred, stride = delta |
| steady | steady | initial (keep the stride) |
| no-pred | transient | no-pred, stride = delta |
last = addr. In steady with a nonzero stride, prefetch addr + stride * D.cLoading…
After each run with the prefetcher, list the valid table entries in index order. Errors: table: 1..64 entries, degree: 1..16, and run: empty trace.
Input:
cLoading…
Output:
cLoading…
Hidden tests cover interleaved arrays, a one-entry table where two PCs keep evicting each other, a larger degree, a negative stride, a linked-list trace, a small stride that stays inside one line, and invalid settings.