NUMA effects

On a two-socket server the same read can cost 80 ns or 130 ns, depending on which socket the page lives on. Where a page lives is decided when it is first touched. This lecture models two nodes, shows how one thread initialising the data makes half of the work remote, and fixes it by letting each thread touch its own part first.

A big server has two processor sockets, and each socket has its own memory modules. A core reads its own socket's memory directly. To read the other socket's memory, the request crosses a link between the sockets, which takes longer. A machine like this is NUMA. Each socket and its memory form a node, and the node of a thread is where its core sits. In our model there are two nodes with two threads each: threads 0 and 1 on node 0, threads 2 and 3 on node 1. A local access costs 80 ns and a remote one 130 ns.

print([node_of_thread(thread, 2) for thread in range(4)])for thread_node in (0, 1):    print("thread on node", thread_node, [LOCAL_NS if page_node == thread_node else REMOTE_NS for page_node in (0, 1)])

[0, 0, 1, 1]
thread on node 0 [80.0, 130.0]
thread on node 1 [130.0, 80.0]

Each row is a thread's view: it pays 80 ns for pages on its own node and 130 ns for pages on the other one. The difference, 50 ns, looks small, but it applies to every access that reaches memory.

The operating system gives memory to a program in pages, and it chooses the node of a page at the moment the page is first used. The default rule is first touch: the page goes to the node of the thread that touches it first, and it stays there. An alternative is to interleave the pages over the nodes. The code below applies both rules to a short list of accesses written as (thread, address).

def first_touch_placement(trace, threads_per_node):    placement = {}    for thread, address in trace:        page = address // PAGE_BYTES        if page not in placement:            placement[page] = node_of_thread(thread, threads_per_node)    return placementdef interleaved_placement(trace, n_nodes):    return {page: page % n_nodes for page in {address // PAGE_BYTES for _, address in trace}}trace = [(0, 0), (0, 4096), (3, 8192), (1, 4100)]print(first_touch_placement(trace, 2))print(interleaved_placement(trace, 2))

{0: 0, 1: 0, 2: 1}
{0: 0, 1: 1, 2: 0}

Page 0 and page 1 were first touched by threads 0, which is on node 0, so they go to node 0. Page 2 was first touched by thread 3, on node 1, so it goes to node 1. The later access of thread 1 to page 1 does not move it. Interleaving ignores who touches what: page 1 goes to node 1 simply because 1 modulo 2 is 1.

A typical parallel job splits a table into chunks, one for each thread. Each thread then reads only its own chunk, so ideally every page it reads is on its own node. The functions below build that access pattern for 400 records over four threads, and count the local and remote accesses and their time for three placements. In the first, "single", one thread initialised all the data, so first touch put every page on node 0. In the second, the owners initialised their own chunks. In the third, the pages are interleaved.

def access_costs(trace, placement, threads_per_node):    local = 0    remote = 0    for thread, address in trace:        if placement[address // PAGE_BYTES] == node_of_thread(thread, threads_per_node):            local += 1        else:            remote += 1    return {"local": local, "remote": remote, "ns": local * LOCAL_NS + remote * REMOTE_NS}def partition_trace(n_records, n_threads, record_bytes):    chunk = n_records // n_threads    return [(thread, record * record_bytes) for thread in range(n_threads) for record in range(thread * chunk, (thread + 1) * chunk)]work = partition_trace(400, 4, 512)single = first_touch_placement([(0, address) for _, address in work], 2)owners = first_touch_placement(work, 2)spread = interleaved_placement(work, 2)for name, placement in (("single", single), ("owners", owners), ("interleaved", spread)):    print(name, access_costs(work, placement, 2))

single {'local': 200, 'remote': 200, 'ns': 42000.0}
owners {'local': 400, 'remote': 0, 'ns': 32000.0}
interleaved {'local': 208, 'remote': 192, 'ns': 41600.0}

With one thread initialising everything, half of the accesses are remote and the job takes 42,000 ns for 400 reads. When the owners initialise their chunks, nothing is remote and it takes 32,000 ns, about 1.3 times faster, for the very same program. Interleaving does not help here: since each thread reads a contiguous chunk, the interleaved pages put half of its data on the wrong node. Interleaving is for data that every thread reads everywhere, where no placement can be good for all of them.

The lab follows the lecture: the node of a thread, the two placement rules, the access pattern of a partitioned job, the count of local and remote accesses, and the study on the SPY records.

• Function · questionBuilds on
• node_of_thread(thread, threads_per_node)Which node does a thread run on?Integer division
• first_touch_placement(trace, threads_per_node)Where does first touch put each page?node_of_thread
• interleaved_placement(trace, n_nodes)And interleaving?Plain arithmetic
• partition_trace(n_records, n_threads, record_bytes)Which accesses does each thread make?Plain arithmetic
• access_costs(trace, placement, threads_per_node)How many local and remote accesses, and how long?node_of_thread
• study(bars)What does the wrong placement cost on the SPY records?partition_tracefirst_touch_placementaccess_costs

Next topic: where the bytes live is only half the story; how they are handed out matters too. In Allocators and memory pools a program asks for many small objects, and the order and the places in which the allocator hands them out decide how many cache lines a later traversal touches.