# A Massively Parallel SMC Sampler for Decision Trees +
## 4 Bayesian Decision Trees
### Sequential Monte Carlo
Therefore, this step, as with _Step 2_ and _Step 6_, scales as \(O(\overline{M}\frac{N}{P})\) or, more simply, as \(O(\frac{N}{P})\) with an \(O(\overline{M})\) constant time factor per sample. Hence, by summing up the individual time complexity terms described above, we can conclude that Algorithm 5 runs in \(O(\frac{N}{P}+\log_{2}N)\) with an \(O(\overline{M})\) computational cost on each sample. Let \(\mathbf{t}\) be a list of \(N\) samples where each sample, \(\mathbf{t}^{i}\), has size \(\mathbf{M}^{i}\), and let \(\mathbf{ncopies}\in\mathbb{N}_{0}^{N}\) be an array that complies with (10). On a DM architecture of \(P\) DM cores, each identified with a rank \(id=0,1,\ldots,P-1\) and owning the \(n=\frac{N}{P}\) elements of \(\mathbf{t}\) and \(\mathbf{ncopies}\) with integer indexes \(n\times id\leq i\leq n\times id+n-1\), Algorithm 6 copies \(\mathbf{t}^{i}\)\(\mathbf{ncopies}^{i}\) times, for all \(i=0,1,\ldots,N-1\), in \(O(\log_{2}N)\) time complexity with an \(O(\overline{M})\) constant time factor for each sample. Proof. : This analysis follows the same logic as the proof of Lemma 1. In other words, we once again analyze each step of Algorithm 6 individually. _Max_, _Pad_, and _Restore_ are steps in common between Algorithm 5 and Algorithm 6, and, as Lemma 1 proves, they achieve \(O(\log_{2}N)\), \(O(1)\), and \(O(1)\) time complexities, respectively, with _Pad_ and _Restore_ also considering a constant time factor of \(O(\overline{M})\). _Step 3_ and _Step 4_ both require one prefix sum at the beginning, followed by a loop of \(\log_{2}P\) iterations, where each DM core iteratively sends, receives, and updates \(\frac{N}{P}\) samples and elements of **ncopies**. Therefore, these steps both achieve \(O(\frac{N}{P}+\frac{N}{P}\log_{2}P)\) time complexity with a constant time of \(O(\overline{M})\). Algorithm 3 in _Step 5_ takes \(O(\frac{N}{P})\) iterations with a constant time of \(O(\overline{M})\). This is because, after _Step 4_, **ncopies** complies with (17). Hence, Algorithm 6 scales as \(O(\frac{N}{P}+\frac{N}{P}\log_{2}P)\) with an \(O(\overline{M})\) constant time, which tends to \(O(\log_{2}N)\) as \(P\to N\). Let \(\mathbf{t}\) be a list of \(N\) samples where each sample, \(\mathbf{t}^{i}\), has size \(\mathbf{M}^{i}\), and let \(\mathbf{\tilde{w}}\in\mathbb{R}^{N}\) be an array of normalized weights. On a parallel architecture (either SM or DM) of \(P\) cores, each owning \(\frac{N}{P}\) elements of \(\mathbf{t}\) and \(\mathbf{\tilde{w}}\), a resampling algorithm performing Equations (8) and (9), either Algorithm 5 (on SM) or Algorithm 6 (on DM), and then resetting each element of \(\mathbf{\tilde{w}}\) to \(1/N\), achieves asymptotically optimal time complexity equal to \(O(\log_{2}N)\). Proof. : As described in this section, Equation (9) and resetting the weights to \(1/N\) are embarrassingly parallel tasks, while Equation (8) and both Algorithms 5 and 6 scale as \(O(\log_{2}N)\) for \(P\to N\). This straightforwardly proves Theorem 1 by absurdity because, even if it was possible to run Algorithm 5 or Algorithm 6 in less than \(O(\log_{2}N)\) (e.g., \(O(1)\)),a resampling algorithm performing the aforementioned steps would still achieve \(O(\log_{2}N)\) time complexity, since the prefix sum in Equation (8) is optimally bound to \(O(\log_{2}N)\), as already proven in [46]. We note that Theorem 4.1 straightforwardly means that a parallel (either on SM or DM) SMC sampler for DTs running Equations (5)-(7), resampling with either Algorithm 5 (on SM) or Algorithm 6 (on DM), and with weight resetting is also asymptotically optimal. However, we do not claim that the constant time per sample is also optimal, as it is bound to \(O(\overline{M})\) in both Algorithms 5 and 6. Indeed, this paper only considers static load-balancing parallel solutions, but, given the variable-size nature of ADTs such as DTs, other solutions based on dynamic load balancing could improve the constant time.