Keyboard Shortcuts

Ctrl+K
Open search
Esc
Close search / dialog
↑
Back to top

The Thing This Machine Cannot Do

22 minadvancedModule 3: Scale, and the Other ArchitecturesContinues from smp-ordering
22 min · Multiprocessor Architecture

Why this matters

A concept whose experiment produced no result is normally a concept that should be deleted. This one is not, and the reason is worth stating before any number appears: the portable content here is a distinction, and the distinction is measurable even though only half of it is.

Memory Non-Uniform Access is the case where the answer to “how far is memory?” depends on which processor asked. Two cores, identical in every respect, get different answers, and neither answer is wrong. That possibility is why a single-core machine cannot answer the question and a two-socket machine cannot answer it with the two cores it already has.

And it is conflated with coherence constantly, which is the practical cost of the confusion. Both are described as “the memory is remote”, and they are not the same phenomenon, they do not have the same mechanism, and they do not have the same fix: false sharing and a contended cache line are fixed by padding or sharding; a NUMA placement problem is fixed by getting the memory near the core that touches it, and padding makes it worse by spreading the data out.

The framing this section uses is the one the artifact prints, and it is unusual enough to be worth adopting generally: the absence is a measurement, not a gap. “There is one memory domain on this machine” is a fact read out of /sys, not a shrug about the hardware. It was established before any claim was made, it is asserted by the harness, and it constrains what every other number in the course is allowed to mean.

The model: two different questions

cache coherence a question between two CACHES. One line, one owner at a time. Solved by a protocol, and the cost is a LINE TRANSFER. THIS is what section 2 measured. NUMA a question between a CORE and a MEMORY CONTROLLER. Nothing is shared and nothing is owned; the address just DECODES differently. The cost is LATENCY and BANDWIDTH, not ownership transfer.

Four differences, and each one is enough on its own to tell the two apart in a profile:

COHERENCE NUMA how many agents? 2+ caches 1 core, N controllers what is contended? a LINE a PAGE / a mapping who loses? the writer nobody what transfers? ownership nothing; it is a of the cache line longer walk to memory and the symptom: coherence two threads on two cores get slower when they touch the same line NUMA one thread on one core gets slower when it touches memory attached to another core

The line that does the most work is the third one: in a coherence problem something is owned and has to change hands; in a NUMA problem nothing is owned and nothing changes hands. That is why no amount of padding helps a NUMA problem — padding does not move ownership, because there is none — and why it can even make things worse by spreading a working set across more pages in more places.

The other half of the model is what makes a NUMA machine hard to reason about: the answer is a function of the address, not of the program. The same instruction, the same cache state, the same everything, gets a different latency because the top bits of the address route the transaction to a different controller. There is no coherence state to inspect, because no state is involved; there is only where the bits go.

Which is exactly why the memory course could not reach it either. That course followed an address down through the TLB and the page tables and out to DRAM, and its limits block names cache coherence, NUMA and multiprocessor memory as belonging elsewhere. This is that elsewhere, and the first half of the job is to say what this machine's answer would have to look like before you notice there isn't one.

The reality: one node, one domain

$ ./smpbench | sed -n '/5. NUMA/,/ONE memory domain/p'
5. NUMA, WHICH IS ABSENT HERE
   Memory Non-Uniform Access is the case where the answer to "how far
   is memory?" depends on WHICH processor asked.  This machine has one
   socket and one memory controller group, so the phenomenon cannot
   occur -- and its absence is a measurement, not a gap.

   /sys/devices/system/node/online  "0"  -> 1 node(s)
   node0 cpulist                    "0-11"

   So: ONE memory domain.  Every core on this machine is the same
   distance from every address, and the number in section 2 is a
   statement about CACHE COHERENCE and not about distance.
 

One node. Its CPU list is 0-11 — every logical CPU on the machine, which is the kernel saying there is nowhere else to be. Every core is the same distance from every address, so a measurement on this machine of “how far is memory” would produce one number and it would be true of every core, which is precisely the property NUMA exists to violate.

What follows, stated precisely rather than apologetically, is the part that constrains the rest of the course:

   * every ratio in section 2 is a COHERENCE ratio.  None of them is
     a NUMA ratio, and none of them would survive a machine with two
     nodes, where the remote case would be a DIFFERENT experiment
     rather than a bigger number.

   * the pinning in section 2 chooses between CORES, not between
     nodes.  On a two-socket machine the same code and the same
     pinning routine would measure remote memory if the second core
     were on the other socket, and the harness would still go green,
     because nothing in it checks the node.  THAT IS A REAL GAP IN
     THIS HARNESS and it is named here rather than left.

   * a reader on a multi-socket machine should extend the topology
     section to read physical_package_id -- which this file already
     reads, prints, and does not yet act on -- and add a row per
     (core, node) pair rather than per core pair.
 

Three claims and each one earns its place.

Every ratio in the placement table is a coherence ratio. 13.05× for true sharing and 10.92× for false sharing are statements about a line changing hands between two caches inside one package. On a two-node machine the “remote” version of the same experiment would not be a larger number for the same effect — it would be a different effect with a different mechanism, and reporting it as the same row would be the mistake this bullet exists to prevent.

The pinning chooses between cores, not nodes.cpu2 and cpu4 are different cores and, on this machine, trivially the same distance from memory. Copy the artifact to a dual-socket machine, run the same command, and if the second CPU happens to be on the other socket you are now measuring remote memory — and every check in the harness would still pass, because the placement check verifies CPU identity and nothing verifies memory identity.

The fix is already half-written. The artifact reads and prints physical_package_id for every CPU and then does not act on it. On this machine every value is 0 and acting on it would change nothing; on a two-socket machine the same loop with the same pinning would produce rows across sockets and the table would quietly stop being the experiment it says it is. A field that is read, printed, and not used is the strongest possible hint that the code was written on a machine where it could not matter — and this one is flagged in the artifact rather than left to be discovered.

Worked: the harness's own gap, and the sentence it is confusing

The bullet about the harness going green is worth making concrete, because a gap in a course's own verification is a different kind of embarrassing from a gap in a machine.

the harness, group B, checks: the online CPU list was read from /sys exact CPU 0 is IN the list even with no online file exact cores x threads-per-core == the CPU count exact no CPU is its own sibling exact every sibling relation is MUTUAL exact the cache list and the sibling list AGREE exact the harness does NOT check: that the two CPUs in any row are in the same node so on a two-socket machine, with the artifact unchanged and the pinning unchanged, every one of those checks passes and section 2 has silently become an experiment about remote memory.

That is not a hypothetical. The artifact's own pinning picks cpu2 and cpu4 by hard-coded number. On a machine whose CPUs are numbered with node 0 first — which is the normal arrangement and is the arrangement here — those two are in the same node. On a machine that enumerates differently, or on one where you edit the pinning to cpu2 and cpu40 because that is what you meant to do, they are not, and the number you take away is about a different question.

The honest repairs are all small and all in the same place: check the node inside the worker alongside sched_getcpu(), discard and count a repetition whose two threads are in different nodes, and add a row per (core, node) pair so that the remote case is a labelled row rather than an accidental one. None of them was done here, because on this machine there is nothing to check, and the correct thing to do with a check you cannot exercise is to say so in the output — which is what the third bullet is.

They are confused constantly, and the confusion has a name: "the memory is remote". On a one-node machine that sentence is MEANINGLESS, which is why this course can make the distinction without measuring the second half of it.

That last observation is the useful one to take away, and it is worth a moment. On this machine, “the memory is remote” cannot be a true sentence. There is no second place for memory to be. That is not a limitation on what you may conjecture about your own machine — it is a limitation on this machine, established by reading a file, and it is the reason the distinction can be taught with a hard boundary around the half that was not measured.

What a reader with a two-socket machine should do is not re-run this artifact. It is extend it, and the extension is exactly the shape of the extension that has been needed three times in this collection: read one more thing out of /sys, cross-check it against a second file that a different subsystem wrote, and turn the thing the code already reads but ignores into the thing the code acts on.

Apply it

  1. Read your node topology and say out loud whether this course's ratios mean anything on your machine.cat /sys/devices/system/node/online and, for each node, cat /sys/devices/system/node/nodeN/cpulist. Then compare each node's CPU list against the sibling pairs from the first concept. (Expect, on a single-socket machine, one node containing every CPU and no sibling pair crossing a boundary. Expect, on a dual-socket machine, two nodes each containing whole sibling pairs — and that is exactly why the placement rows would still be valid on a dual-socket machine, because pinning to siblings of the same core also pins within a node. The rows that would break are the ones pinning across sockets, which is worth checking deliberately.)
  2. Classify six real performance complaints. For each, name it coherence or NUMA and say what would change if you were wrong: (a) a threaded reduction is 10× slower than the serial version and adding padding to the per-thread accumulators does nothing; (b) a process is fast when it starts and slow after a large allocation; (c) two threads writing adjacent struct fields are slower than two threads writing fields 64 bytes apart; (d) a memcpy is slower on a large buffer than on a small one by more than the size ratio; (e) a thread migrates and performance collapses; (f) the machine is fast with one socket's worth of threads and slow with all of them. (Expect (c) to be the only unambiguous coherence case and expect at least one of the others to be genuinely undecidable from the symptom — which is the practical argument for the distinction being a question you ask about mechanism, not about speed.)
  3. Add the node check to a copy of the artifact, and see whether it can ever fire. Have each worker read /sys/devices/system/node/cpuN/'s node id after sched_getcpu(), print it, and add a harness check that the two workers are in the same node. (Expect the check to pass on every repetition on this machine, and expect that to be the entire point: you have written a check whose failure mode you cannot demonstrate, which is precisely the situation the privilege course's exercise 2 is about. Note the difference from a check you can break — that is what makes it weaker, and it is better to know which of your checks are which.)
  4. Prove that the distinction predicts a number, using the numbers already measured. Coherence transfers a line, so its cost should land in the last-level-cache band that the memory course's latency concept measured. NUMA transfers nothing, so its cost should land near the DRAM band that same concept measured. (Expect the coherence row’s 47.76 ticks/op to be consistent with an L3 round trip rather than with a DRAM access — at this machine’s own measured TSC rate of 2.2957 GHz that is about 21 ns — and expect that this is a bound and not an identification, because without a PMU you cannot count transfers and are inferring from the price. The prediction is falsifiable in one direction: a DRAM round trip would have put the row near 350 ticks instead of 48, so the measurement is able to rule the slow mechanism out even though it cannot count the fast one.)

Connect

Backwards, the ordering concept established the course's largest limit: a duration cannot establish a guarantee. This concept is the second-largest, and it is the one where the temptation is different. Ordering cannot be measured at all; NUMA cannot be measured here, and the second kind is much easier to fake. The defence is the same in both cases and it is the harness's: assert the absence, assert the reason, and never print a number in the space where the number is unknown.

Forward, the three-architectures concept covers the other two machines' coherence designs, and the interesting thing about it here is that all three have the same unit of sharing and the same state machine. NUMA is the thing that changes when you leave one: it is not a protocol at all, it is the address space having more than one answer to the question “where does this live.” And the harness concept is where the node gap from this section shows up as a check that is absent, which is its own small demonstration of the rule the whole course is built on.

Outward, the closest neighbours are in the memory course and they are about the same walk at two different distances. The memory course's latency concept chased an address from L1 to DRAM on one core and found the bands; every number it produced is a local number, and this concept is the one that says what happens when “local” stops meaning one thing per core. Its translation concept is where the address is split into parts, and on a NUMA machine the interesting part is the one this course cannot reach: the bits that choose the controller are decoded from the physical address, so the difference between local and remote is a property of the mapping and not of the code. Which means the fix for a NUMA problem is usually a policy decision made by the first-touching thread, and a policy decision is not a performance detail.

And for anyone building a runtime: the reason this concept exists in a course that cannot measure it is that “is it coherence or is it NUMA” is a question your scheduler will eventually have to answer automatically. You cannot answer it by measuring, on one machine, and you cannot answer it by counting, because there is no PMU. You answer it by reading the topology and by knowing which question each number answers.

render_lesson_js(&mut page)