## 4 Novel \(O(\log_{2}N)\) fully-balanced Redistribution
### Algorithmic Details and Theorems
#### 4.2.1 Rotational Nearly Sort  
**Theorem 1**. : _Given an array of \(N\) particles, \(\mathbf{x}\), and their copies to be created, \(\mathbf{ncopies}\), whose elements are evenly distributed across the \(P\) cores of a DM, Algorithm 2 (performed by each core \(p\), \(\forall p=0,1,...,P-1\)) describes the steps to safely shift the elements in \(\mathbf{x}\) and \(\mathbf{ncopies}\) to achieve property (9), and performs that in \(O(\log_{2}N)\) parallel time for \(P=N\)._  
Proof of Theorem 1.: The first process to carry out is to nearly sort the particles locally by calling Sequential Nearly Sort (S-NS) (see Algorithm 3), which iteratively moves the \(i\)-th particle to the left/right side of the output array if \(\mathbf{ncopies}^{i}\) is positive/zero. We note that this routine only takes \(O(\frac{N}{P})\) iterations, since every DM core owns \(\frac{N}{P}\) particles. This will start moving the particles locally to the left before doing so globally. The particles within the core \(p\) must now shift to the left by as many positions as the number of zero elements in \(\mathbf{ncopies}\) owned by the cores with a lower rank. Let \(\mathbf{zeros}\in\mathbb{Z}^{P}\) be the array that counts the number of \(\mathbf{ncopies}^{i}=0\) within each core; each element of \(\mathbf{shifts}\in\mathbb{Z}^{P}\) (the array to keep track of the remaining shifts) can be initialized as follows:  
\[\mathbf{shifts}^{p}=\sum_{\hat{p}=0}^{p-1}\mathbf{zeros}^{\hat{p}} \tag{12}\]  
Equation (12) can be parallelized by using a parallel exclusive cumulative sum (after each core \(p\) has initialized \(\mathbf{zeros}^{p}\) to the sum of zeros within its memory, at the end of S-NS). It is well covered in the literature that the cumulative sum (also known as prefix sum or scan) takes \(O(\frac{N}{P}+\log_{2}P)\) computations [35, 36]. We now want to express \(\mathbf{shifts}^{p}\) in binary notation and shift the particles by increasing power-of-two numbers of positions, depending on the bits of \(\mathbf{shifts}^{p}\), from the Least Significant Bit (LSB) to the Most Significant Bit (MSB). This translates to using a bottom-up binary tree structure that will complete the task in \(O(\log_{2}N)\) time. If \(P<N\), then we first need to perform an extra leaf stage, in which, the cores send all of the particles to their neighbor if the bitwise AND of \(\mathbf{shifts}^{p}\) and \(\frac{N}{P}-1\) is positive. In simple terms, the leaf stage masks the \(\log_{2}\frac{N}{P}\) LSBs of \(\mathbf{shifts}^{p}\) and performs the rotations referring to those bits in one operation per particle. Hence, during this step, each core sends and receives up to \(\frac{N}{P}\) particles, meaning that the leaf stage takes \(O(\frac{N}{P})\). Figure 3: RoSS redistribution—example for \(N=8\) and \(P=4\). Each \(\mathbf{x}^{i}\) is actually a real vector, but marked with a letter for brevity. After the leaf stage, the actual tree-structure routine can start. At every \(k\)-th stage of the tree (for \(k=1,2\),..., \(\log_{2}P\)), any core \(p\) will send to its partner \(p-2^{k-1}\) all its particles (i.e., \(\mathbf{x}\) and \(\mathbf{ncopies}\)) and \(\mathbf{shifts}^{p}-\frac{N}{P}2^{k-1}\) (i.e., the number of remaining shifts after the current rotation) if the bitwise AND of \(\mathbf{shifts}^{p}\) and \(\frac{N}{P}2^{k-1}\) is positive; this corresponds to checking a new bit of \(\mathbf{shifts}^{p}\), precisely the one which is significant at this stage. We note that, in order to balance the communication at all stages, the cores are set to send particles to reject (i.e., having \(\mathbf{ncopies}^{i}=0\)) if the LSBs are \(0\). Hence, this phase takes \(O(\frac{N}{P}\log_{2}P)\) because each core sends and receives \(\frac{N}{P}\) particles \(\log_{2}P\) times. Before the leaf stage, the particles in the memory of core \(p\) must shift at most from one end to the other end, i.e., by \(\mathbf{shifts}^{p}\leq N-1\) positions. Any non-negative integer \(\mathbf{shifts}^{p}\leq N-1\) can always be represented in base-2 by \(\log_{2}N\) bits.