2
$\begingroup$

I'd like to implement a high-performance implementation of a multi-threaded reduction, element-wise, on x86 CPUs. Without loss of generality, assume the reduction operation is a sum of integers (so, both commutative and associative). Each of the T threads has an array of N elements, and the final element-wise sum should end up in an output array that is the same size N as the T input arrays.

I'm looking for an algorithm that would be efficient and fast with T threads running inside a single M core multicore processor (assume T is equal to M here). All threads share the same address space.

Approach 1: My sense is that some sort of tree combination would make sense to compute the total reduction in log2(T) steps. It also seems to make sense that at any given step whereby two threads' arrays are being combined, each of those threads could participate in the reduction (each taking ~half of the output array, aligned to cache-line boundaries to eliminate false sharing on the output array). The threads do span multiple NUMA nodes, and assume the algorithm should work both for small arrays (fits within L1) and large arrays (fits within L3 but not within L1). One downside of this approach, though, is that it requires a number of extra temporary arrays to handle the accumulation at each level of the tree.

Approach 2: Another approach I'm considering is that all threads take responsibility for 1/T of the final output array (aligned to cache-line boundaries). In this approach, a thread could reduce in results from the (T-1) other arrays into the final output array. This doesn't have the memory overhead of Approach 1, and I think it has the same number of addition operations ((T-1) * N) as Approach 1 (?).

Note that I'm not memory constrained, but the extra memory allocations and cache misses would take time, and I'm trying to optimize for overall runtime performance here. Also, this should be able to leverage vectorization on the CPU in either case.

My question concerns the algorithm, but FYI, I'm using C++17 and the threads are standard std::threads mostly with std::atomics for synchronization currently.

One extra complication: the threads may arrive at different times and they all need the final resulting reduction array, so they have to wait until the full reduction is done.

Side note: I found this design document for the OpenMP implementation of reduce on GPUs (NVIDIA, specifically). My guess is that something similar for CPUs would be helpful, although I haven't been able to find that yet.

$\endgroup$
  • 2
    $\begingroup$ I am skeptical whether you're going to be able to analyze this solely on paper, rather than through experiments. I expect the performance of different solutions will depend heavily on details of the memory hierarchy and cache (which are difficult to model with standard theoretical algorithm analysis) as well as the rough size of $T$, $N$, and $M$. $\endgroup$ – D.W. Sep 27 '19 at 18:15
  • $\begingroup$ If I were to implement one as a first try, do you have a leaning towards approach 1 vs approach 2? $\endgroup$ – user110001 Sep 28 '19 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.