## 1 Introduction
### Problem Definition and Related Work  
Although the particles can be sampled in embarrassingly parallel fashion, resampling is hard to parallelize _globally_, i.e., in such a way that the result for \(P>1\) processing units (or cores, as referred to in this paper) is identical to that achieved using a single core. This is because of the difficulties in parallelizing the constituent _redistribution_ step, whose textbook implementation achieves an \(O(N)\) time complexity on one core. In order to bypass the need to parallelize resampling, one could use multiple PFs in parallel, each performing resampling locally, i.e., when each core performs resampling independently without considering the content of the other cores' particles. However, this approach has shown accuracy, scalability and model-dependent applicability issues [15; 16; 17]. On Shared Memory (SM) architectures, it has been shown that a global redistribution of the particles takes \(O(\log_{2}N)\) computations by using a static load balancing approach, in which, all cores perform independently up to \(N\) binary searches in order to achieve a perfect workload balance. Examples are found in [12; 13; 18; 19] on GPU and mainstream CPUs. High Performance Computing (HPC) applications, however, need to use Distributed Memory (DM) architectures to overcome the limitations in modern SM of a low memory capacity and Degree Of Parallelism (DOP). On DM, parallelization is more complicated, as the cores cannot directly access the other cores' memory without exchanging messages. Three master-worker solutions for DM (along with mixed versions of them) are presented in [20]: Centralized Resampling (C-R), Resampling with Proportional Allocation (RPA) and Resampling with Non-proportional Allocation (RNA). C-R performs resampling globally, but here, a central-unit gathers the particles from all cores, performs redistribution sequentially and scatters the result back to the cores, making this algorithm scale as \(O(N)\). RPA also performs global resampling, but the network topology is randomized, as the redistribution is partly or potentially entirely (worst-case) centralized to one or a few cores, leading to a strongly data-dependent run-time and an \(O(N)\) time complexity in the worst-case. RNA has a simpler central unit and communication pattern than RPA, but sacrifices accuracy, as local resampling is performed. For the routing, RNA could use RPA or a ring topology, where the cores cyclically exchange a user-defined number of particles with their neighbors, though such an approach risks redundant communication. These master-worker approaches have been used, re-interpreted or mixed in recent work, such as in [17; 21; 22; 23; 24]. In [17; 24; 25], it is shown that such strategies may have accuracy or scalability issues, especially for a highly unbalanced workload, large \(N\) or DOP. In this paper, we then consider only _fully-balanced_ solutions, which we define as follows. **Definition 1**. : _A fully-balanced redistribution meets the following requests:_  
* _All cores perform the same pre-agreed tasks (i.e., no central unit(s) are involved) to balance the workload evenly;_
* _The number of messages for the load balancing is data-independent in order to guarantee a stable run-time, as often required in real-time applications;_
* _The redistribution of the particles is performed globally in order to ensure the same output of sequential redistribution and that no speed-accuracy trade-off is made when the DOP increases._  
In [26], it has been shown that redistribution can be parallelized in a fully-balanced fashion on DM by using a divide-and-conquer approach that recursively sorts and splits the particles. Since Bitonic Sort [27; 28; 29] is performed \(O(\log_{2}N)\) times, the achieved time complexity is \(O((\log_{2}N)^{3})\). In [17], sort is also employed recursively in a dynamic scheduler for RPA/RNA. In [30], the time complexity is reduced to \(O((\log_{2}N)^{2})\) by showing that Bitonic Sort is only needed once.