## 3 Parallel Computing Based on a Hybrid OpenMP-MPI Approach
### Parallelization Strategy Based on Hybrid OpenMP-MPI Approach  
A hybrid OpenMP-MPI approach is here proposed to overcome the abovementioned limits of the pure MPI approach. The underlying idea is to allocate in each node only one instance of the \(M_{D}\) memory, and then to use all the physical cores only for computation. This means that we must logically separate allocation from computation, that is forbidden in a pure MPI paradigm, which maps one-to-one cores and processes. The solution could be provided by the use of the OpenMP environment directives: the node computation is broken down among the physical cores (threads) present in the node, that share the same memory on the node thanks to the shared memory approach implemented by OpenMP. A hybrid OpenMP-MPI approach may be then implemented, based on the two following steps:  
1. as in the pure MPI paradigm, the overall computation is partitioned in MPI processes, limiting the number of the processes at node level (in the ideal case this number would be 1);
2. the computational burden of each MPI process at node level is divided (again) in several threads, in accordance with the characteristics of the OpenMP paradigm. In order to investigate the memory allocation scheme of the hybrid approach, we firstly recall that in OpenMP environment, each thread should allocate its local memory in order to face its own computation. Note that the dimension of the dummy memory per thread, \(M_{DT}\), is much lower than \(M_{D}\). In order to speed up the inter-thread computation and to fully gain from the modern CPU architecture, \(M_{DT}\) should match the local core cache size (_cache coherence_, e.g., [27]). Let us now define as \(N_{T}\) the number of threads per node: if we use one MPI process per node, and after considering that \(M_{D}\) is allocated only once, Condition (11) on the available memory for the pure MPI approach is replaced for the hybrid OpenMP-MPI one by the following:  
\[M_{AV}=M_{N}-N_{T}M_{DT}-M_{D}\geq M_{LOC}=\frac{M}{N_{N}} \tag{12}\]  
In view of comparing the two approaches, it is convenient to introduce the following speed-up parameters: \(S_{MPI}=N_{MPI}\) (for pure MPI approach) and \(S_{H}=N_{T}N_{N}\) (for hybrid OpenMP-MPI). They can be expressed from (11) and (12), as follows:  
\[S_{MPI}\leq\frac{M_{N}}{M_{D}}N_{N}-\frac{M}{M_{D}},\ \ S_{H}\leq\frac{M_{H}-M_{D}}{M_{DT}}N_{N}- \frac{M}{M_{DT}} \tag{13}\]  
The above relations set the upper bounds for the two speed-up parameters, that linearly depend on the number of nodes, \(N_{N}\): Figure 2 shows the corresponding straight lines, whose intersection occurs at:  
\[N_{N}^{*}=\frac{(M_{DT}-M_{D})M}{(M_{DT}-M_{D})M_{N}+M_{D}^{2}} \tag{14}\]  
where \(N_{N}^{*}>0\), since \(M_{N}>M>M_{D}\geq M_{DT}\geq 0\). For \(N_{N}>N_{N}^{*}\), it is always \(S_{H}>S_{MPI}\) and the distance between the two bounds increases monotonically, as shown in Figure 2.  
Figure 2: Upper bound for the speed-up parameter as a function of number of nodes \(N_{N}\): pure MPI approach (\(S_{MPI}\)) and hybrid OpenMP–MPI approach (\(S_{H}\)). Indeed, this result can be demonstrated by considering the ratio between the slopes of the straight lines--from (13), as follows:  
\[\frac{\frac{M_{N}}{M_{D}}}{\frac{M_{N}-M_{D}}{M_{DT}}}=\frac{M_{DT}}{M_{D}}\frac{ M_{N}}{M_{N}-M_{D}}<1 \tag{15}\]  
where the inequality holds since \(M_{DT}<M_{D}\), and \(M_{D}\ll M_{N}\), hence \(M_{N}/\left(M_{N}-M_{D}\right)\ \approx 1\). As clearly shown in Figure 2, this hybrid OpenMP-MPI approach provides two advantages over the pure MPI approach, as follows:  
1. resources saving--for a fixed speed-up \(S\), the required number of nodes \(N_{N}\) is lower;
2. speed-up advantage--for fixed resources (\(N_{N}\)), the speed-up, \(S\), is higher. In addition, as pointed out in the Introduction, the approach also reduces the communication burden, because the parallel routines impose a fast communication between each thread in the node.