# A Massively Parallel SMC Sampler for Decision Trees +
## 4 Bayesian Decision Trees
### Sequential Monte Carlo
Algorithm 3 takes \(O(N)\) steps on a single core, as with all the other tasks in the SMC sampler when \(P=1\). This is because the total number of samples to be copied in the redistribution step is equal to \(N\), as Equation (10b) emphasizes. However, this algorithm is impossible to parallelize if using embarrassingly parallel approaches. The main reason is that the workload associated with duplicating each sample, \(\mathbf{t}^{i}\), a total of \(\mathbf{n}\mathbf{c}\mathbf{o}\mathbf{i}\) times is inherently unbalanced as Equation (10a) holds. In several cases, such as when sampling DTs, the samples have variable sizes, which could potentially render an embarrassingly parallel attempt to parallelize S-R even more unbalanced. Here, we describe two static load-balancing approaches, one for SM and one for DM, that work for variable-size samples and scale as \(O(\frac{N}{P}+\log_{2}N)\). In both cases, the key idea is to divide the workload evenly, before having the cores run Algorithm 3 independently. We do this while also guaranteeing that the computation (and communication, in the case of DM) required to balance the workload (roughly) costs the same for all cores. A fully balanced distribution across the cores of the workload to redistribute \(N\) variable-size samples is defined, on both SM and DM, as follows. **Definition 1** (Workload Balanced). : _Let \(\mathbf{t}\) be a list of \(N\) samples where each sample, \(\mathbf{t}^{i}\), has size \(\mathbf{M}^{i}\) for \(i=0,1,\ldots,N-1\). Let \(\mathbf{n}\mathbf{c}\mathbf{o}\mathbf{i}\in\mathbb{N}_{0}^{N}\) be an array that satisfies Equation (10), such that each \(i\)-th element, \(\mathbf{n}\mathbf{c}\mathbf{o}\mathbf{i}^{s}\), defines how many times the \(i\)-th sample in \(\mathbf{t}\), \(\mathbf{t}^{i}\), needs to be redistributed. On parallel architectures (either on SM or DM) of \(P\) cores, each owning the \(\mathbf{n}\mathbf{c}\mathbf{i}\) and \(\mathbf{n}\mathbf{c}\mathbf{o}\mathbf{i}\) with index \(i=id\cdot n,id\cdot n+1,id\cdot n+2,\ldots,(id+1)\cdot n-1\), the workload is fully balanced across the cores if and only if the following condition is met:_

\[\mathbf{w}_{0}^{i} =\frac{\pi(\mathbf{t}_{0}^{i}|\mathbf{Y},\mathbf{x})}{q_{0}( \mathbf{t}_{0}^{i})}. \tag{4b}\]4

However, since the algorithmic details of the parallel redistribution step on SM and DM differ for the most part, we describe them in the two following sections. #### 5.1.1 Parallel Shared Memory Redistribution

Our SM approach performs, in sequence, the following six steps, each running \(P\) cores in parallel. _Step 1--Max._ In this step, the cores compute in parallel

\[\mathbf{w}_{0}^{i} =\frac{\pi(\mathbf{t}_{0}^{i}|\mathbf{Y},\mathbf{x})}{q_{0}( \mathbf{t}_{0}^{i})}. \tag{4b}\]5

i.e., the size of the largest sample. \[\mathbf{w}_{0}^{i} =\frac{\pi(\mathbf{t}_{0}^{i}|\mathbf{Y},\mathbf{x})}{q_{0}( \mathbf{t}_{0}^{i})}. \tag{4b}\]6

_Step 2--Pad_. Each thread, \(id=0,1,\ldots,P-1\), extends each sample by appending \(\overline{M}-\mathbf{M}^{i}\) dimensions each with a value that is known to be impossible. In the specific case of DTs, we can use negative integers such as \(-1\), but we suggest that Not a Numbers (NaNs) would be a generic value for any variable-size ADT. In other words, by performing _Step 1_ and _Step 2_, we ensure that the copy and paste costs per sample in Algorithm 3 are equal for all samples. _Step 3--Prefix Sum_. In this step, the cores first compute in parallel \(\mathbf{csum}\in\mathbb{N}_{0}^{N}\), the cumulative sum of \(\mathbf{ncopies}\), such that

\[\mathbf{w}_{0}^{i} =\frac{\pi(\mathbf{t}_{0}^{i}|\mathbf{Y},\mathbf{x})}{q_{0}( \mathbf{t}_{0}^{i})}. \tag{4b}\]7

The integer \(\mathbf{csum}^{i}\) represents the number of copies to be created up to the index \(i\). Alternatively, because the samples have now equal sizes, one could consider \(\mathbf{csum}^{i}\) as the total workload (up to a constant time term equal \(\overline{M}\)) in order to sequentially redistribute the samples from the index \(0\) to the index \(i\). _Step 4--Binary Search_.