## 4 Evaluation Methodology
### Algorithm Dependencies and Definition of Test Cases  
After the algorithm has been analyzed and divided into functional blocks, we can identify their dependencies. By _dependencies_, we mean the variables that affect the computational complexity of each block. The functional blocks discussed in Section 4.2 coincide with the steps described in Section 2.1. Their dependencies are summarized in Table 3.  
Based on the dependency analysis, we can finally determine the parallelization possibilities for each functional block. In particular, the parallelization modalities are reported below:  
* _Particle Initialization_: The parallelization is performed based on the particles.
* _Particle Prediction_: The parallelization is performed based on the particles.
* _Data Association_: The parallelization is performed based on the particles, on the previously observed landmarks, and jointly on the particles and the landmarks. Although the complexity of the data association step also depends on the number of observa  
Figure 5: Functional blocks partitioning schema.  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Step** & \(N_{p}\) & \(N_{l}\) & \(N_{o}\) \\ \hline Particle Initialization & ✓ & ✗ & ✗ \\ Particle Prediction & ✓ & ✗ & ✗ \\ Data Association & ✓ & ✓ & ✓ \\ Proposal Adjustment & ✓ & ✗ & ✓ \\ Landmark Estimation & ✓ & ✗ & ✓ \\ Resampling & ✓ & ✗ & ✗ \\ \hline \hline \end{tabular}
\end{table}
Table 3: Algorithm dependencies.  
tions, the necessity of performing feasible joint hypotheses (i.e., each observation is associated with at most one landmark) forces the developer to tackle them sequentially.
* _Proposal Adjustment_: The parallelization is performed based on the particles, on the matched observations, and jointly on the particles and the matched observations.
* _Landmark Estimation and Weight Update_: The parallelization is performed based on the particles, on the total observations, and jointly on the particles and the observations.
* _Importance Resampling_: The parallelization is performed based on the particles.  
Such parallelization modalities are then mapped onto the grid combination options available in the GPU programming paradigm:  
* Sequential--one block, one thread (\(1B1T\))
* One dimension, thread-based--one block, \(N\) threads (\(1 BNT\))
* One dimension, block-bases--\(M\) blocks, one thread (\(MB1T\))
* Two dimensions--\(M\) blocks, \(N\) threads (\(MBNT\)).  
The sensitivity analysis is carried out by varying one of the dependencies and keeping all the others constant. We perform such evaluation for all the dependencies in each step, except for the number of observations in the _Data Association_ functional block. This is because JCBB builds the association hypotheses incrementally, which implies a sequential execution on the observations. Consequently, it is impossible to assess the benefit of parallelization based on this parameter.  
Each dependency is assigned a threshold, as shown in Table 4. These thresholds are generally defined with the sole scope of binding the execution time. However, further limitations may arise depending on the memory availability of each specific device and the memory requirements of each kernel. For the sake of the completeness of our sensitivity analysis, we apply the aforementioned thresholds when possible. However, in an actual use case scenario, it is necessary to find an optimal combination between the memory availability of the hardware device, the desired precision of the estimation (proportional to the number of particles), and the map's scale.