## 7 Numerical Simulation and Results
### Test 2: Measuring the Speed-Up of the Parallel Implementation  
The second test consists of measuring the speed-up produced by the parallel implementation of the proposed algorithm. First, the focus is on the SSSP algorithm which is the most time-consuming part of the overall framework. For the SSSP algorithm, three implementations to solve the problem shown in Figure 13 are tested. The SSSP is run for every DP and calculates the shortest path to every other DPs. The first implementation tested is the Dijkstra algorithm from the Boost C++ library [36]. This implementation is considered to be highly efficient and is used here as the reference for the sequential implementation. The second implementation is the CUDA implementation as proposed by [PERSON] et al. in [28]. The third implementation is the proposed CUDA SSSP implementation based on [PERSON] et al., but which avoids the atomic operation, which runs the SSSP instances in batch mode to increase the level of parallelism and which run multiple iteration of the while loop at Algorithm 3 before checking the number of nodes in the frontier array. The three SSSP implementations are tested on a Dell 5820 workstation equipped with a Xeon W-2195 CPU and an RTX-2080 Ti GPU. The CPU has 18 cores and a peak frequency of 3.6 GHz. The specifications for the GPU were given in Section 4. The runtime and speed-up for the SSSP implementations solving 55 instances of the SSSP problem for various map resolutions are shown in Figures 15 and 16. There are 55 instances of the SSSP problem to be solved because the map processed (the one shown in Figure 13) contains 55 DPs. The runtime for the sequential implementation on CPU is 18.0 s for the smallest resolution and 684.9 s for the largest resolution compared to 0.6 s and 45.4 s for [PERSON]'s implementation and 0.15 s and 17.4 s for the proposed CUDA implementation. This translates into speed-ups of 29.9\(\times\) and 15.1\(\times\) for [PERSON]'s implementation and 117.6\(\times\) and 39.4\(\times\) for the proposed implementation. These speed-ups clearly demonstrate the advantage of the parallel implementation on GPU. However, the reduction of speed-up as the map resolution increases is normal and is caused by the higher complexity of the parallel algorithm compared to the Dijkstra algorithm. By design, the parallel algorithm performs more calculation than the Dijkstra algorithm. This means that if the map resolution would continue to increase, there would be a point where the parallel algorithm and the Dijkstra algorithm would exhibit the same execution time and there would be no advantage for the parallelization. However, for practical map resolutions, there is a significant advantage to the parallel implementation on GPU. From the results obtained, it can also be concluded that the proposed CUDA implementation is much faster than the original parallel implementation by [PERSON] et al. [28]. This is because it avoids the atomic operation, it processes the SSSP instances in batches of 10 and it runs multiple iterations of the while loop in Algorithm 3 before calculating the number of nodes in the frontier array which is an expensive operation. Figure 15: Runtime of the three SSSP implementations tested. To assess the contribution of the parallel SSSP algorithm to the overall framework, Table 4 lists the runtime for each function composing the overall framework. It is important to note that the runtime for the parallel SSSP includes the data transfer to and from the GPU. When minimizing for time or energy, filling the cost matrix requires that the path between each pair of DPs be built so that the exact speed and power required can be calculated along the path. This step is parallelized in OpenMP on multi-core CPU using one thread per pairs. For the GA, OpenMP is also used to parallelize each step of the algorithm using one thread per candidate solution. For the other functions, they are intrinsically sequential and are therefore not parallelized.