# A Massively Parallel SMC Sampler for Decision Trees +
## 4 Bayesian Decision Trees
### Sequential Monte Carlo
The * is used to emphasize that the runtime is rounded to the closest integer, as running two different methods for exactly the same runtime is challenging. In other words, the results in this section indicate that a parallel SMC sampler on both SM and DM architectures is able to compensate for the larger constant time factor than the one in parallel multi-chain MCMC by achieving better accuracy per time unit and therefore providing a more convenient runtime vs. accuracy compromise. ## 7 Conclusions

In this study, we have proposed two approaches to parallelizing an SMC sampler for Bayesian DTs: one approach is specific to SM architectures; the other approach is specific to DM architectures. Given the inherent differences between SM and DM architectures, the parallel solutions that we describe are substantially different, especially in the parallelization of the bottleneck, i.e., redistribution. However, in both cases, we have proven that it is possible to achieve optimal time complexity \(O(\log_{2}N)\). By taking advantage of multi-core architectures, our approach provides up to a 16-fold speed-up on a 32-core SM machine and up to a 200-fold speed-up on a 256-core DM cluster. On both architectures, the proposed methods significantly improve the performance of alternative approaches to Bayesian DTs, such as MCMC. More precisely, on four exemplar datasets for classification, our approach could provide roughly the same classification accuracy but up to 51 times faster on SM and up to 640 times faster on DM for the same problem size. Alternatively, in both memory architectures, we could provide substantially higher classification accuracy in the same execution time. While the results are promising, there remains considerable room for improvement in both the accuracy and execution time. For instance, the accuracy could be improved by adopting a more effective proposal distribution for ADTs, such as HINTS [47]. However, refining the proposal distribution often comes at the cost of an increased runtime. This trade-off can be addressed through several strategies. Firstly, this work has independently examined SM and DM approaches for CPUs. However, high-performance computing (HPC) commonly relies on hybrid MPI+X programming models, which increase the parallelism by combining distributed and shared memory, maximizing the computational capabilities of modern supercomputers. Another option is to take advantage of GPUs, which often outperform CPUs in highly parallelizable tasks like the sampling step of the SMC sampler. Additionally, alternative parallelization techniques for tasks in the SMC sampler could be explored. In this work, we used static load-balancing methods, but dynamic load-balancing approaches might be more suitable for the variable-size nature of DTs, potentially improving both the runtime and scalability. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Dataset** & **Method** & \(\mathbf{P}\) & \(\mathbf{N}\) & \(\mathbf{K}\) & Time & **Accuracy** \\ \hline Heart & SMC & 256 & \(2^{10}\) & 10 & 0.36 [s] * & 77.44\% \\  & Multi-Chain MCMC & 256 & \(2^{10}\) & 30 & 0.36 [s] * & 70.01\% \\ \hline Diabetes & SMC & 256 & \(2^{10}\) & 10 & 1 [s] * & 73.27\% \\  & Multi-Chain MCMC & 256 & \(2^{10}\) & 20 & 1 [s] * & 67.61\% \\ \hline Abalone & SMC & 256 & \(2^{10}\) & 10 & 4 [s] * & 22.48\% \\  & Multi-Chain MCMC & 256 & \(2^{10}\) & 12 & 4 [s] * & 20.28\% \\ \hline Students & SMC & 256 & \(2^{10}\) & 10 & 6 [s] * & 71.48\% \\  & Multi-Chain MCMC & 256 & \(2^{10}\) & 15 & 6 [s] * & 60.32\% \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Accuracy per time unit on DM. The * is used to emphasize that the runtime is rounded to the closest integer, as running two different methods for exactly the same runtime is challenging. **Author Contributions:** Conceptualization, E.D. and A.V. ; formal analysis, E.D., A.V., A.M.P., P.G.S. and S.M. ; software, E.D., A.V. and A.M.P. ; investigation, validation, visualization, and writing--original draft, E.D. and A.V. ; review and editing, E.D., A.V., A.M.P., P.G.S. and S.M.