## Appendix A \(O((\log_{2}N)^{2})\) Fully-Balanced Redistribution  
This appendix describes the fully-balanced redistribution algorithm described in [30]. This routine redistributes the particles in \(O((\log_{2}N)^{2})\) parallel time by performing the following steps. First, the particles \(\mathbf{x}\) are sorted by the values in \(\mathbf{ncopies}\). The chosen sorting algorithm is Bitonic Sort, a comparison-based parallel sorting algorithm that has been implemented on a cluster of graphics cards relatively recently [28]. For any \(P\leq N\), Bitonic Sort performs  
\[O\left(\frac{N}{P}\left(\log_{2}\left(\frac{N}{P}\right)\right)^{2}+\frac{N} {P}(\log_{2}P)^{2}\right) \tag{1}\]  
comparisons, where the first term describes the number of steps to perform Bitonic Sort locally, and the second term represents the data movement to merge the keys between the cores. Here, as in [25], Bitonic Sort is performed locally, but it is also possible to replace it with an \(O(N\log_{2}N)\) single-core sort, such as Mergesort. Quicksort is not recommended in this case, because \(\mathbf{ncopies}\) contains many zeros, which often results in Quicksort's worst-case (\(O(N^{2})\)) run-time. An example of a sorting network for Bitonic Sort is illustrated in Figure 11. The particles to be duplicated are then separated from those to be deleted. After this single sort, the algorithm moves on to another top-down routine. Starting from the root node, at each stage of the binary tree, three parallel operations are performed in sequence. First, the cores compute the inclusive cumulative sum over \(\mathbf{ncopies}\). Then, they search for a _pivot_ that perfectly divides the node into two balanced leaves; in other words, _pivot_ is the first index where the cumulative sum is equal to or greater than \(\frac{N}{2}\). To find and broadcast _pivot_ to all cores of the node, the cores use linear search locally, followed by a sum, which can be performed in parallel by using reduction. In the end, the \(\frac{N}{2}\) particles on the right side of the _pivot_ are shifted to the right side of the node. This is achieved by expressing \(r\) (the positions to shift by) in base-2 and rotating in \(O(\log_{2}N)\) steps according to the bits of \(r\). In this way, the root node gets split into two balanced leaves. This top-down routine is recursively performed \(\log_{2}P\) times until the workload is equally distributed across the cores; then, S-R is called. In this paper, as in [7], we refer to this algorithm as Bitonic-Sort-Based Redistribution (B-R). Since Bitonic Sort is used once,and cumulative sum, reduction and rotational shifts are performed \(\log_{2}P\) times each, B-R achieves an \(O((\log_{2}N)^{2})\) time complexity for \(P=N\), or equal to (A1) for any \(P\leq N\). As mentioned in Section 4.1, it would be theoretically possible to replace Bitonic Sort with AKS sort in order to make the asymptotic time complexity of the sorting phase equal to \(O(\log_{2}N)\), albeit with a large constant. However, since B-R needs a cumulative sum, a sum and rotational shifts up to \(\log_{2}N\) times, the overall computational complexity that would result from such an approach would still be \(O((\log_{2}N)^{2})\). In [30], B-R has been implemented on MapReduce. In [25], B-R has been ported to MPI. A small change to B-R can result in a further 25% improvement, as results in [7] and Section 5.1 show. This is achieved by substituting Bitonic Sort with an alternative algorithm, Nearly Sort. One does not actually need to perfectly sort the particles to divide the workload afterwards, but only needs to guarantee **ncopies** has shape (9). To achieve this property, the particles are first nearly sorted locally by calling Algorithm 3. We emphasize that doing so is faster than sorting the particles according to **ncopies**. Then, the particles are recursively merged, as in Bitonic Sort, by using the same sorting network illustrated in Figure A1.