Loading page…
Master the fundamental concepts of cache optimization through this focused micro-challenge.
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 worksFalse sharing happens when two threads write different variables that live in the same 64-byte cache line. Each write forces the line to bounce between cores even though the threads touch disjoint data. OpenMP reductions and per-thread counters often hit this bug.
Symptoms: scaling collapses when you add cores to an embarrassingly parallel loop. Fix: pad structs or arrays so each thread's hot field occupies its own cache line.
cLoading…
perf c2c on Linux maps line conflicts to source linesalignas(64)Keep 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 demonstrate false sharing between two threads updating adjacent counters, then fix it with padding and compare timings. This exercise requires showing improved scaling after separation.
False sharing happens when threads on different cores write to different variables that happen to live in the same cache line. The coherence protocol tracks whole lines, so every write steals the line from the other core and the counters "ping-pong". Simulate MESI coherence for a set of per-core counters, and show how padding them onto separate lines makes the traffic disappear.
cLoading…
Each iteration touches every counter once, in input order. Every core starts with every line Invalid. A counter without read performs counter++ (a read then a write, so the line must end in M). A read counter only loads.
| Access | Own state | Action |
|---|---|---|
| write | M or E | hit, becomes M |
| write | S | upgrade miss: invalidate every other copy, becomes M |
| write | I | miss: coherence if another core has a copy (if that copy is M, it is also a dirty transfer), otherwise cold. Invalidate every other copy, becomes M |
| read | M, E or S | hit |
| read | I | miss (coherence/dirty transfer/cold as above). Other copies drop to S. Becomes S if someone else had it, otherwise E |
Each copy that a write invalidates counts as one invalidation sent by the writing core.
cLoading…
line N: must be a power of two, counter NAME: offset N is not 8-byte aligned, counter NAME: rejected (bad core, or more than 8 counters), and run: no counters.Input:
cLoading…
Output:
cLoading…
offset / line, so changing the line size alone changes the sharing.Hidden tests cover padding counters 64 bytes apart, a writer whose line is shared with readers (upgrade misses), four cores on two lines, a 128-byte line that turns padded counters back into false sharing, read-only sharing, and invalid input.