# A Massively Parallel SMC Sampler for Decision Trees +
## 2 Parallel Computer Architectures  
SM and DM architectures are fundamentally different. In this section, we briefly highlight their advantages and disadvantages, as well as the differences between the two architectures.  
In SM architectures, we have a single memory, which all the \(P\) computational resources, i.e., the cores, share and can access simultaneously. This is exemplified in Figure 0(a). The main advantage of this architecture with respect to DM is that the sharing of information between the cores can happen simply by writing data to and reading the same from shared memory locations, whose memory address needs to be known by the cores. The main disadvantages are related to the performance for two reasons. First of all, the scalability is not ideal as, when \(P\) increases, so does the memory contention when accessing the same memory locations. Addressing this requires the use of software synchronization points, e.g., barriers. The second disadvantage is that modern SM architectures do not provide large numbers of cores in comparison with DM architectures. In this work, we use OpenMP, one of the most commonly used parallel programming models for SM. OpenMP employs the #pragma omp parallel for instruction to specify which for loops to run in parallel. This instruction can be enriched with extra clauses, e.g., num_threads, to specify the number of threads to run in parallel, or reduce, to specify a parallel reduction operation occurring in the same for loop. Further details are omitted for brevity.  
DM architectures are inherently different from SM architectures and consist of \(P\) machines interconnected by a common communication network. Each machine has one processor (or core--the terms in this paper are used interchangeably to make the terminology of distributed and shared memory architectures as consistent as possible) and a private memory. Therefore, each core can only directly access its own private memory, and the sharing of information between the cores happens through message exchange across the common communication network. Figure 1b illustrates this architecture. DM provides two advantages with respect to SM architectures. The first is that memory contention is not an issue for DM, as each core only has access to its private memory, meaning that the scalability is often better in memory-intensive applications. As previously mentioned, the second advantage is that DM architectures typically have more cores, which means that, for any given application, the maximum achievable speed-up on DM is typically higher than the same on SM. On the other hand, the two disadvantages are that the communication between the cores is naturally more intensive than on SM, and DM architectures are also more expensive to use and maintain, due to the more complex infrastructure required. In this work, we use the Message Passing Interface (MPI), arguably the most commonly used parallel programming model for DM. MPI provides routines, such as MPI_Send, MPI_Recv, or MPI_Sendrecv, to send and/or receive explicit messages (of a user-specified size) between a core \(i\) and a core \(j\). Further details are omitted for brevity.  
We also note that modern supercomputers are actually hybrid memory architectures, consisting of several DM machines, each having several SM cores. In the analysis of DM in Section 6, we employ MPI across cores in different physical machines and across cores within the same physical machine, with a view to maximizing the number of DM cores. We acknowledge that, in such hardware, one could use hybrid programming models MPI+X, such as MPI+OpenMP. Exploring the performance of such an environment is, however, beyond the scope of this study, but it is certainly an interesting direction for future development.