# A Massively Parallel SMC Sampler for Decision Trees +
## 4 Bayesian Decision Trees
### Sequential Monte Carlo
* If only the MSB of \(\textbf{max\_shifts}^{i}\) is 1, some copies of \(\textbf{t}^{i}\) must not move, and the remaining ones must split and shift, i.e., those for which \(\textbf{csum}^{i}-i\) is higher than the power-of-2 number of positions to rotate by at any given iteration. Therefore, the values of \(\textbf{ncopies}^{i}\) and \(\textbf{csum}^{i}\) need to be reduced consequently by the number of copies of \(\textbf{t}^{i}\) that are being rotated to the right. * At the end of each rotation, as described above, each core updates \(\textbf{min\_shifts}\) and \(\textbf{max\_shifts}\) according to (24) and (25). As conducted in _Step 3--Rotational Nearly Sort_, in order to keep the cores equally busy, each core always sends arrays of \(\frac{N}{P}\) elements of **t**, \(\textbf{ncopies}\), and **csum**, regardless of the values in **ncopies**, but, for obvious reasons, the core that receives the message will have to save only the elements that have \(\textbf{ncopies}^{i}>0\). _Step 5--S-R_. After performing Rotational Split, all cores have \(\frac{N}{P}\) samples to redistribute. Therefore, each core can perform Algorithm 3 independently. _Step 6--Restore_. After redistributing, we use the same restore step as in Algorithm 5 to remove up to \(\overline{M}-1\) dimensions from each sample, i.e., those dimensions that are encoded with an impossible value during \(Pad\), such as \(-1\) s for DTs or NaNs for any ADT. Algorithm 6 summarizes these steps, and Figure 2(b) illustrates a numerical example for \(N=8\) samples and \(P=4\) cores. ```
1:t,ncopies,M,N,P,n = \(\frac{N}{P}\)
2:t \(\leftarrow\)Pad(t,\(\overline{M}\),P)
3:if\(P>1\)then
4:t,ncopies \(\leftarrow\)Rotational Nearly Sort(t,ncopies,P)
5:t,ncopies \(\leftarrow\)Rotational Split(t,ncopies,P)
6:endif
7:t \(\leftarrow\) S-R(t,ncopies,n), See Algorithm 3
8:t \(\leftarrow\)Restore(t,\(\overline{M}\),P)
```

**Algorithm 6** Parallel DM Redistribution for Variable-Size Samples

### Time Complexity Analysis

In this section, we first analyze the time complexity of the approaches described in Sections 5.1.1 and 5.1.2, and then we analyze the time complexity of a resampling step that utilizes either of them. **Lemma 1**: _Let \(\textbf{t}\) be an array of \(N\) lists, where each list, \(\textbf{t}^{i}\), for \(i=0,1,\ldots,N-1\), has a variable size, \(\textbf{M}^{i}\). Let \(\textbf{ncopies}\in\mathbb{N}_{0}^{N}\) be an array of non-negative integers for which (10) holds. On an SM architecture running \(P\) parallel cores, Algorithm 5 redistributes \(\textbf{t}\) according to **ncopies** in \(O(\frac{N}{P}+\log_{2}N)\) steps with an \(O(\overline{M})\) constant time factor for each sample._Proof. : To prove Lemma 1, we start by analyzing the time complexity of each of the steps in Algorithm 5 individually. The computation of \(\overline{M}\) in (16) can be parallelized by using parallel reduction, as the vector max operator is also reducible, as with the vector sum. Therefore, (16) scales as \(O(\frac{N}{P}+\log_{2}P)\) with a \(O(1)\) constant time factor. _Step 2_ and _Step 6_ are embarrassingly parallel, as they loop independently over the samples and extend or reduce the dimensionality of each sample by up to \(\overline{M}-1\). Therefore, these two steps scale as \(O(\overline{M}\frac{N}{P})\) or, more simply, as \(O(\frac{N}{P})\) with a constant time factor per sample of \(O(\overline{M})\). In _Step 3_, the parallel cores compute the cumulative sum of **ncopies**, which, as stated above, achieves \(O(\frac{N}{P}+\log_{2}P)\) time complexity with a \(O(1)\) constant time factor. In _Step 4_, the cores perform one independent BS each, which notoriously takes \(O(\log_{2}N)\) comparisons. In addition, each core also computes (19) once, which takes \(O(1)\). The copying procedure described in _Step 5_ requires each core to copy independently \(\frac{N}{P}\) samples, each of which has \(\overline{M}\) dimensions.