C.6.1 Ordering-Hostile Architecture

Paul has come across a number of ordering-hostile computer systems, but the nature of the hostility has always been extremely subtle, and understanding it has required detailed knowledge of the specific hardware. Rather than picking on a specific hardware vendor, and as a presumably attractive alternative to dragging the reader through detailed technical specifications, let us instead design a mythical but maximally memory-ordering-hostile computer architecture.C.4

This hardware must obey the following ordering constraints [McK05a,McK05b]:

  1. Each CPU will always perceive its own memory accesses as occurring in program order.
  2. CPUs will reorder a given operation with a store only if the two operations are referencing different locations.
  3. All of a given CPU's loads preceding a read memory barrier (smp_rmb()) will be perceived by all CPUs to precede any loads following that read memory barrier.
  4. All of a given CPU's stores preceding a write memory barrier (smp_wmb()) will be perceived by all CPUs to precede any stores following that write memory barrier.
  5. All of a given CPU's accesses (loads and stores) preceding a full memory barrier (smp_mb()) will be perceived by all CPUs to precede any accesses following that memory barrier.

Quick Quiz C.9: Does the guarantee that each CPU sees its own memory accesses in order also guarantee that each user-level thread will see its own memory accesses in order? Why or why not? End Quick Quiz

Imagine a large non-uniform cache architecture (NUCA) system that, in order to provide fair allocation of interconnect bandwidth to CPUs in a given node, provided per-CPU queues in each node's interconnect interface, as shown in Figure [*]. Although a given CPU's accesses are ordered as specified by memory barriers executed by that CPU, however, the relative order of a given pair of CPUs' accesses could be severely reordered, as we will see.C.5

Figure: Example Ordering-Hostile Architecture
\resizebox{3in}{!}{\includegraphics{appendix/whymb/hostileordering}}

Paul E. McKenney 2011-12-16