New Multi-Threaded Pi Program - Faster than SuperPi and PiFast

[rcofell]

I'm getting speedups of up to 30% using numactl interleave on Linux. The speedup depends on the size - for smaller sizes, it sometimes backfires.
I'll accept any settings as valid benchmarks. Tuning the OS like this is part of the game, lol.

As far as I can tell, only Windows Server has any sort of NUMA-awareness support. But you need Win Server anyway to get more than 2 sockets in the first place.
There might be a setting somewhere in the OS that can be set to force interleaved memory allocation. If there isn't, maybe there's a special WinAPI malloc() function that does interleaved allocation. If I find it, I'll try it out.

But in any case, interleaved memory allocation isn't a "solution" to NUMA.
It lets the program get the full memory bandwidth, but it doesn't get rid of the interconnect contention and latency.

The program will still need to be redesigned to run well on NUMA.

I've been meaning to post in here for awhile, as I've got access to an 8-socket Barcelona machine (w/ ~80GB ram) here in our research group at school that I've tried running things on. The NUMA nature of the machine definitely causes sub-optimal scaling for the smaller workloads (those below 1B).

I tried numactl for 1B and performance goes from 648sec (without) to 466sec (interleave all), so it does make a noticeable difference. Almost a 1.4X speedup in this case.

For comparison (without numactl), 10B takes 5,379sec and 100M takes 110sec.

You are correct, but there's an even bigger problem with the program.
y-cruncher allocates all the memory it needs in a single gigantic malloc(). The OS will put that entire memory block on the node that called the malloc(). So the result is that most (if not all) of the memory will be concentrated in a single node.

The 4 nodes will all try to access that same memory - all of which is in one node. So not only do you have contention on the interconnect, but the aggregate memory bandwidth is only equal to that of one socket. (since all the memory is concentrated there)
If the memory is interleaved, you still don't get rid of the interconnect traffic, but at least now you have 4 sockets of memory bandwidth.

This problem does not occur in "normal" applications that do lots of small allocations. For these normal apps, the OS will bias all the allocations on the nodes that called them - so memory accesses are mostly local.
But since y-cruncher does one massive malloc() at the beginning, the OS is not able to do this.

There were several major reasons why I made the program do a single malloc() and it's own memory management as opposed to letting the OS handle it.

1. Memory allocation is expensive - (hundreds/thousands of cycles?)
2. malloc() is not thread-safe. Placing locks around it is not scalable. Even if it is thread-safe (with the right compiler options), it's still implemented with locks.
3. Memory allocation is not deterministic. The address that malloc() returns differs between program instances even with the exact same settings.
   The memory manager I put into the program is deterministic - even with multi-threading.
   It's a lot easier to hold together 100,000 lines of multi-threaded code if its deterministic.

Yeah, tying all of the memory allocation to one thread/node doesn't do so well with NUMA I imagine. Beyond just the interconnect bandwidth impact, coherency traffic must become a significant overhead as well.

Determinism definitely is desirable with parallel programs, though in what capacity are you using the deterministic malloc()? Is it mainly for debug, or structured memory/pointer accesses? As for thread-safe, are you saying just using barriers to properly synchronize isn't good enough?

At the expense of memory capacity trade-off, could you have each thread malloc() a (relatively) small buffer to work out of? In the interest of creating some locality and doing burst transfers.

More stupid questions:

will MPI or OMP help?

How is it doing the multi-threading/multi-processing now anyways?

Can threads do malloc()? (You might have actually said it already, but I'm a dummy non-programmer trying to wrap my head around programming concepts.)

I've always been under the impression/belief that multi-processing can happen ONLY if it spawns slave processes. So the whole idea of multi-threading != multi-processing in my mind (or at least it doesn't seem to be as efficient or doesn't use the full resources available to it).

I'm curious of the current implementation as well

Is it all p-thread based? MPI would definitely be the way to go for ensuring proper locality on a NUMA system, at the expense of all the icky manual data sharing. I've only done some basic use of OpenMP, so I don't know too much of the advanced details like optimizations for NUMA systems, but is it really applicable to your current algorithm?

I remember reading sometime ago about your implementation spawning a large amount of threads, do you limit the number of work threads to the available hardware threads, or go beyond? Having excessive threads would likely thrash around too much with larger NUMA systems and be counter productive.

How independent are the threads? Is there much synchronization/sharing of data between them, or does each basically work on its own independent chunk of the series and combine in a tree-reduce fashion?