Portable multicore/NUMA memory allocation/initialization best practices

Question

When memory bandwidth limited computations are performed in shared memory environments (e.g. threaded via OpenMP, Pthreads, or TBB), there is a dilemma of how to ensure that the memory is correctly distributed across physical memory, such that each thread mostly accesses memory on a "local" memory bus. Although the interfaces are not portable, most operating systems have ways to set thread affinity (e.g. pthread_setaffinity_np() on many POSIX systems, sched_setaffinity() on Linux, SetThreadAffinityMask() on Windows). There are also libraries such as hwloc for determining the memory hierarchy, but unfortunately, most operating systems do not yet provide ways to set NUMA memory policies. Linux is a notable exception, with libnuma allowing the application to manipulate memory policy and page migration at page granularity (in mainline since 2004, thus widely available). Other operating systems expect users to observe an implicit "first touch" policy.

Working with a "first touch" policy means that the caller should create and distribute threads with whatever affinity they plan to use later when first writing to the freshly allocated memory. (Very few systems are configured such that malloc() actually finds pages, it just promises to find them when they are actually faulted, perhaps by different threads.) This implies that allocation using calloc() or immediately initializing memory after allocation using memset() is harmful since it will tend to fault all the memory onto the memory bus of the core running the allocating thread, leading to worst-case memory bandwidth when the memory is accessed from multiple threads. The same applies to the C++ new operator which insists on initializing many new allocations (e.g. std::complex). Some observations about this environment:

• Allocation can be made "thread collective", but now allocation becomes mixed into the threading model which is undesirable for libraries which may have to interact with clients using different threading models (perhaps each with their own thread pools).
• RAII is considered to be an important part of idiomatic C++, but it seems to be actively harmful for memory performance in a NUMA environment. Placement new can be used with memory allocated via malloc() or routines from libnuma, but this changes the allocation process (which I believe is necessary).
• EDIT: My earlier statement about operator new was incorrect, it can support multiple arguments, see Chetan's reply. I believe there is still a concern of getting libraries or STL containers to use specified affinity. Multiple fields may be packed and it may be inconvenient to ensure that, e.g., an std::vector reallocates with the correct context manager active.
• Each thread can allocate and fault its own private memory, but then indexing into neighboring regions is more complicated. (Consider a sparse matrix-vector product $y \gets A x$ with a row partition of the matrix and vectors; indexing the unowned part of $x$ requires a more complicated data structure when $x$ is not contiguous in virtual memory.)

Are any solutions to NUMA allocation/initialization considered idiomatic? Have I left out other critical gotchas?

(I don't mean for my C++ examples to imply an emphasis on that language, however the C++ language encodes some decisions about memory management that a language like C does not, thus there tends to be more resistance when suggesting that C++ programmers do those things differently.)

Answer 1

One solution to this problem that I tend to prefer is to disaggregate threads and (MPI) tasks at the, effectively, memory controller level. I.e., remove the NUMA aspects from your code by having one task per CPU socket or memory controller and then threads under each task. If you do it that way, then you should be able to bind all memory to that socket/controller safely either via first-touch or one of the available APIs no matter which thread actually does the work of allocation or initialization. Message passing between sockets is usually quite well optimized, in MPI at the very least. You can always have more MPI tasks than this, but due to the issues you raise, I rarely recommend folks have less.

Answer 2

This answer is in response to two C++ related misconceptions in the question.

1. "The same applies to the C++ new operator which insists on initializing new allocations (including PODs)"
2. "C++ operator new takes only one parameter"

It is not a direct answer for multi-core issues you mention. Just responding to comments that classify C++ programmers as C++ zealots so that the the reputation is maintained ;).

To point 1. C++ "new" or stack allocation does not insist on initializing new objects, whether PODs or not. The class's default constructor, as defined by the user, has that responsibility. The first code below shows junk printed whether the class is POD or not.

To point 2. C++ allows overloading "new" with multiple arguments. The second code below shows such a case for allocating single objects. It should give an idea and perhaps be useful for the situation you have. operator new[] can be modified appropriately too.

// Code for point 1.

#include <iostream>

struct A
{
    // int/double/char/etc not inited with 0
    // with or without this constructor
    // If present, the class is not POD, else it is.
    A() { }

    int i;
    double d;
    char c[20];
};

int main()
{
    A* a = new A;
    std::cout << a->i << ' ' << a->d << '\n';
    for(int i = 0; i < 20; ++i)
        std::cout << (int) a->c[i] << '\n';
}

Intel's 11.1 compiler shows this output (which is of course uninitialized memory pointed by "a").

993001483 6.50751e+029
105
108
... // skipped
97
108

// Code for point 2.

#include <cstddef>
#include <iostream>
#include <new>

// Just to use two different classes.
class arena { };
class policy { };

struct A
{
    void* operator new(std::size_t, arena& arena_obj, policy& policy_obj)
    {
        std::cout << "special operator new\n";
        return (void*)0x1234; //Just to test
    }
};

void* operator new(std::size_t, arena& arena_obj, policy& policy_obj)
{
    std::cout << "special operator new (global)\n";
    return (void*)0x5678; //Just to test
}

int main ()
{
    arena arena_obj;
    policy policy_obj;
    A* ptr = new(arena_obj, policy_obj) A;
    int* iptr = new(arena_obj, policy_obj) int;
    std::cout << ptr << "\n";
    std::cout << iptr << "\n";
}

Answer 3

In deal.II we've got the software infrastructure to parallelize assembly on each cell onto multiple cores using the Threading Building Blocks (in essence, you have one task per cell and need to schedule these tasks onto available processors -- that's not how it's implemented but it's the general idea). The problem is that for the local integration you need a number of temporary (scratch) objects and you need to provide at least as many as there are tasks that can run in parallel. We see poor speedup, presumably because when a task is put onto a processor it grabs one of the scratch objects that will typically be in some other core's cache. We had two questions:

(i) Is this really the reason? When we run the program under cachegrind I see that I'm using basically the same number of instructions as when running the program on a single thread, yet the total run-time accumulated over all threads is much larger than the single-thread one. Is it really because I continually fault the cache?

(ii) How can I find out where I am, where each of the scratch objects are, and which scratch object I'd need to take to access the one that's hot in my current core's cache?

Ultimately, we haven't found answers to either of these solutions and after a couple of works decided that we lack the tools to investigate and solve these problems. I do know how to at least in principle solve problem (ii) (namely, using thread-local objects, assuming that threads remain pinned to processor cores -- another conjecture that's not trivial to test), but I have no tools to test problem (i).

So, from our perspective, dealing with NUMA is still an unsolved question.

Answer 4

Beyond hwloc there are a few tools that can report on a HPC cluster's memory environment and which can be used to set a variety of NUMA configurations.

I would recommend LIKWID as one such tool as it avoids a code based approach allowing you for instance to pin a process to a core. This approach of tooling to address machine specific memory configuration will help ensure the portability of your code across clusters.

You can find a short presentation outlining it from ISC'13 "LIKWID - Lightweight Performance Tools" and the authors have published a paper on Arxiv "Best practices for HPM-assisted performance engineering on modern multicore processor". This paper describes an approach to interpreting the data from hardware counters to develop performant code specific to your machine's architecture and memory topology.