## 5 Experimental Results  
In this section, we show the numerical results of redistribution first and then show results for a PF example. In the experiment for redistribution, we compare RoSS, the novel fully-balanced algorithm presented in this paper, with N-R and B-R, two fully-balanced redistributions that take \(O((\log_{2}N)^{2})\) steps (see Appendix A). These algorithms are compared by passing in input arrays with the same values to all algorithms: **ncopies** and \(\mathbf{x}\) with \(M=1\). To guarantee (5), **ncopies** is generated randomly by using MVR (see Equation (7)) with a log-normally distributed input \(\mathbf{\tilde{w}}\). For the PF experiment, we consider three versions of a SIR PF that only differ in terms of the constituent redistribution used. Each PF test is run for \(T_{PF}=100\) iterations. Resampling is computed every iteration so that we ensure that the frequency of redistribution is the same. The model we consider is the stochastic volatility example described in Appendix B.  
All experiments are conducted for \(N\in\{2^{16},2^{20},2^{24}\}\) particles and for up to \(P=256\) cores. Each reported run-time is the median of 20 runs collected for each \(N\), \(P\) pair.  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Task Name** & & **Sequential Time** & **Parallel Time** \\ **(Parallelization Strategy)** & **Details** & **Complexity** & **Complexity** \\ \hline IS (embarrassingly parallel) & Equations (1) and (2) & \(O(N)\) & \(O(\frac{N}{P})\) \\ Normalize (reduction) & Equation (3) & \(O(N)\) & \(O(\frac{N}{P}+\log_{2}P)\) \\ ESS (reduction) & Equation (4) & \(O(N)\) & \(O(\frac{N}{P}+\log_{2}P)\) \\ MVR (cumulative sum) & Equations (6) and (7) & \(O(N)\) & \(O(\frac{N}{P}+\log_{2}P)\) \\ Redistribution (RoSS) & Algorithm 5 & \(O(N)\) & \(O(\frac{N}{P}+\frac{N}{P}\log_{2}P)\) \\ Reset (embarrassingly parallel) & \(\mathbf{w}_{i}^{\prime}=1/N\)\(\forall i\) & \(O(N)\) & \(O(\frac{N}{P})\) \\ Estimate (reduction) & Equation (8) & \(O(N)\) & \(O(\frac{N}{P}+\log_{2}P)\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Time complexity of each task of PFs on DM.  
All algorithms in this paper are coded in C++ with OpenMPI-1.10.7 and compiled with -O3 optimization flag; double and unsigned int data types are, respectively, used for real and integer numbers. Combinations of MPI_Barrier and MPI_Wtime are used to collect the run-times for Figures 4 and 5, while TAU Performance System 2.7 is used for the profiling in Figure 6. The cluster for the experiments consists of eight machines, interconnected with InfiniBand 100 Gbps and each mounting a 2 Xeon Gold 6138 CPU that provides 40 cores running at 2 GHz. We note that the results for up to \(P=32\) DM cores have been collected by requesting (at scheduling time) cores from the same node. For \(P\geq 64\), we have requested 32 DM cores from each node. While we cannot identify any resulting artifacts in the results, we acknowledge that this feature of the hardware does potentially influence our results when comparing run-times related to \(P\leq 32\) with those for \(P\geq 64\). We emphasise that, to ensure the experimental results allow for a meaningful comparison between algorithms, all algorithms were assessed on the same hardware for each \(P\). Future work would sensibly investigate these performance differences as part of a broader study on how to maximise performance as a function of hardware configuration.  
Figure 4: Redistribution—results for increasing \(N\) and \(P\).  
Figure 5: Stochastic volatility—results for increasing \(N\) and \(P\).