Loading page…
Master the fundamental concepts of memory hierarchy 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 worksCPUs move data in cache lines (typically 64 bytes). Two independent variables sharing a line sit on the same coherence unit. When one core writes byte 0 and another writes byte 63, both cores invalidate each other's copy even though logical data differs. That is false sharing.
cLoading…
Pad structures to one hot field per line:
cLoading…
Run two threads updating adjacent ints vs padded ints and compare perf c2c or cycle counts.
For this exercise, you will demonstrate slowdown from unaligned hot fields. This task asks you to fix layout with padding and measure the speedup, a routine optimization in Java @Contended, Linux per-CPU counters, and game engine job structs.
Keep the relevant datasheet, ISA manual, or architecture textbook chapter open while you implement. When your output disagrees with the reference trace on the same program, the bug is usually a mis-decoded opcode, a stale register read, or a flag bit left unchanged after arithmetic.
For this exercise, you will use those habits while implementing the requirement in the starter code. Microarchitectural product names change across CPU generations, but the control ideas (fetch, bypass, cache lines, vector lanes) stay stable enough to debug from first principles.
Explain false sharing by simulating the MESI cache-coherence protocol. Two threads can update different variables and still fight over the cache: if the variables sit in the same cache line, every write by one core invalidates the other core's copy. Simulate per-core line states and bus transactions for a trace of reads and writes. Then show how padding the variables into separate lines makes the invalidations disappear.
cLoading…
Caches are unbounded: lines are never evicted for capacity. Every line starts I (invalid) in every core.
| Access | Own state | Result |
|---|---|---|
| read | M, E, S | hit |
| read | I | miss, BusRd. If another core has it M, that core writes back and both end S. If others have it E/S, all end S. If nobody has it, you get E |
| write | M | hit |
| write | E | hit, silently E→M (no bus traffic) |
| write | S | upgrade: BusUpgr; every other copy → I; you → M |
| write | I | miss, BusRdX. Every other copy → I (an M copy writes back first); you → M |
For each access outside a repeat:
cLoading…
The parenthesis lists every other core whose state changed, in core order, separated by , (with , writeback right after an M core's transition). It is omitted when no other core changed. A repeat block prints one line when it finishes:
cLoading…
(counts for that block only). states prints one line per touched line in ascending order: line 0x1000: c0=M c1=I. At the end:
cLoading…
An invalidation is another core's copy going to I. bus counts BusRd + BusRdX + BusUpgr. Addresses print in lower-case hex.
Input:
cLoading…
Output:
cLoading…
access(core, is_write, addr) function that implements the table.repeat blocks reuse the same function with printing switched off.Hidden tests cover read sharing (E, then S on a second reader), an S→M upgrade, the silent E→M write, a four-core trace, and a counter that is truly shared rather than falsely shared.