Interleaving Pages Across Nodes for Aggregate Bandwidth

Every other placement policy in this cluster tries to put a page near the thread that will use it. Interleaving does the opposite on purpose: it spreads pages evenly over every node in a mask, accepting that roughly half the accesses will be remote on a two-node machine, in exchange for using every node’s memory controllers at once.

The trade only makes sense for one shape of workload, and identifying that shape is most of the skill.

The bandwidth ceiling of a single node

A node’s memory bandwidth is bounded by the number of DRAM channels attached to it and by the width of the fabric link that carries traffic to other nodes. Local accesses use the channels; remote accesses use the link in both directions. Neither resource is shared with the other node’s local traffic in a way the kernel can arbitrate.

A single thread streaming through an array on its own node can saturate only a fraction of the node’s channels, because one core’s outstanding-miss capacity limits how many requests it can have in flight. A single thread streaming through an array on another node is further limited by the link. Many threads on the same node streaming through the same node’s memory can saturate the channels, and then adding threads does nothing.

So there are two distinct ceilings: per-core, set by the miss handling capacity of the core, and per-node, set by the memory controllers. Interleaving addresses the second by ensuring that a large streaming workload’s pages are distributed so that each node’s controllers are used by the threads running on that node. It does nothing for the first.

The cycle is indexed by page offset

Under MPOL_INTERLEAVE, the node for a page is computed from the page’s position, not chosen by a counter that advances as pages are allocated. The kernel forms the page offset of the faulting address within the segment that contains it, adds the segment’s own starting page offset, and reduces the sum modulo the number of nodes in the mask. The node standing at that position in the mask is the one the page is allocated from, and if that node cannot satisfy the request the allocator falls through the usual node ordering rather than moving to the next slot of the cycle.

Because the answer depends only on the address, placement is reproducible: two threads faulting the same range, in any order and at any time, compute the same node for a given page. A range faulted by one thread and a range faulted by eight threads receive the same distribution, and the distribution does not depend on scheduling, which is what makes interleaving predictable in a way first-touch placement is not.

The granularity of the distribution follows the page size. With base pages over two nodes, the stride between successive pages on the same node is two pages, so a sequential stream alternates nodes every 4 KiB and each node’s controller sees every other request. With 2 MiB pages, one slot of the cycle is consumed per huge page, so a sequential walk stays on one node for 2 MiB before moving to the other. The aggregate is the same in principle, but the temporal pattern is coarser: a thread walking a huge-page-interleaved array spends long stretches entirely local and long stretches entirely remote.

Firmware-level interleaving, configured in the memory controller rather than by the kernel, has the same property with a different granularity: it hashes physical addresses across channels and nodes at cache-line or page granularity, and the operating system cannot see or change it. When that is enabled, every physical address is already spread, and a kernel policy that also interleaves compounds the effect.

One context does advance through the node set in allocation order rather than by address: page-cache pages, such as the pages that back a memory-mapped file, are interleaved with a per-task node counter that wraps through the mask, so their distribution follows the order in which they were first read rather than any offset. The temporary interleave policy the kernel applies over all memory during boot works the same way. Neither is what a program reaches for ordinary data: a policy installed on a range through mbind, which is the case that matters for a large anonymous array, is the address-indexed form.

Cycle length, phase, and what the mapping controls

The distribution is a function of the area’s geometry as much as of the node set. A mapping whose pages begin at an offset that is not a multiple of the node count starts its cycle at a different node, so two mappings of the same file at different offsets can be spread identically in aggregate while each of them begins on a different node. Any code that reasons about which node a given page will land on has to use the mapping’s own offset, not the file’s.

The modulo also means that the number of nodes in the mask, not the number of nodes in the machine, sets the cycle length. A mask naming three of four nodes distributes over three and leaves the fourth unused, and the phase of the cycle shifts whenever the mask changes.

The policy is attached the same way as any other: a call on the range, with the node mask, and nothing else. What differs is only how the target node for each page is derived from the mask.

#include <numa.h>

/* Spread a range across all nodes the task is allowed to use. */
int interleave_all(void *addr, size_t len)
{
    struct bitmask *nodes = numa_get_mems_allowed();
    int rc = mbind(addr, len, MPOL_INTERLEAVE,
                   nodes->maskp, nodes->size + 1, 0);
    numa_free_nodemask(nodes);
    return rc;
}

Passing flags of zero means the policy applies to future faults only. A range already populated keeps its pages where they are, which is usually what a caller wants when the range was just reserved, and usually not what a caller wants when the range is a reused buffer. Passing MPOL_MF_MOVE instead asks for the existing pages to be migrated to match the new distribution, at the cost described in Page Migration: What a Move Between Nodes Costs.

Where interleaving helps, and where it hurts

The workload that benefits is a streaming one: a scan, a reduction over a large array, a memcpy between two buffers, a matrix operation whose operands are larger than any single node’s memory. In these, access is sequential and there is no reuse to exploit, so locality buys nothing and spreading buys channel parallelism. The best case is that every node’s controllers are busy simultaneously and the aggregate bandwidth approaches the sum of the per-node bandwidths, minus the remote traffic that the spreading itself creates.

The workload that suffers is any pointer-chasing structure: a tree, a linked list, a hash table with chained buckets. Each dereference is a dependent load, so latency is exposed rather than overlapped. With pages spread over two nodes, roughly half of the dereferences that miss the cache cross the fabric, and the structure’s traversal time rises by the weighted average of local and remote latency. Spreading is strictly harmful here, because the structure is not bandwidth-bound and gains nothing from channel parallelism.

Between these extremes sit workloads whose behavior depends on size. A structure that fits in one node’s cache benefits from local placement; the same structure at a size that exceeds one node’s memory cannot be local, and interleaving then makes the access cost uniform rather than leaving half the accesses fast and half slow. Uniformity has value in its own right: a system where every access costs the same is easier to reason about and has better tail behavior than one where most accesses are fast and some are three times slower.

Comparing the policies on one axis

The table below places the four common policies on the axis that separates them: what the policy optimizes, and what it gives up.

Policy	Placement target	Optimizes	Gives up
default	faulting node	latency for the touching thread	balance across nodes
bind	nodes in mask, nearest first	predictability, locality	ability to use memory outside the mask
preferred	one node, fallback to faulting node	locality with a safety valve	uniform placement
interleave	round-robin over mask	aggregate bandwidth	per-access latency

The axis is not quality; it is what the workload needs. A database buffer pool that fits in one node and is read by threads on that node wants bind. A large in-memory table read by threads spread over all nodes wants interleave, because no placement can make all of them local and uniform cost is better than uneven cost. The measurement that distinguishes the cases is the remote access ratio per thread, covered in Measuring Remote Access with Hardware Counters.

Interaction with the page cache and file mappings

The page cache complicates it in a different way. A shared file mapping is not governed by a range policy at all: allocation for a page of it follows the policy of whichever task causes the allocation, which may not be the task that installed a policy on the mapping. Placement of a memory-mapped file is therefore decided by the first reader across the whole system, not by the policy of any particular process. The same holds for tmpfs and shared memory objects: the page is allocated when first written, on the node of the writing task under that task’s policy, and every later mapping inherits that placement. Interleaving a shared region therefore works only if the region is faulted by a task whose task policy interleaves, and only for the pages that task faults first. The broader question of how policies attach to address ranges and propagate is the subject of Where a Memory Policy Attaches.