## 3 GPU Parallelization of Metaphorless Optimization Algorithms
### GPU-Based Acceleration of the Enhanced Jaya Algorithm  
No mention has been found in the existing literature of any GPU-based parallel EJAYA algorithm other than the one detailed in this section and proposed by the authors [35; 36]. While analyzing the differences between EJAYA and the original Java optimization algorithm, it becomes evident that EJAYA encompasses several additional steps and a more intricate formulation, primarily due to a more complex search method. Consequently, the GPU parallelization of EJAYA explained here demands a more elaborate approach than the original algorithm, requiring the redesign and adaptation of its methods to meet the requisites and constraints of parallel processing. The overview of the GPU-based parallel EJAYA can be observed in Algorithm 15. According to the GPU-based parallelization strategy employed, all updated candidate solutions are generated simultaneously during each algorithm iteration. This means that some parts of the implementation need to be adjusted to ensure that all essential data for the LES and GES phases (Equations (5) and (8)) are readily available for computation in the population update kernel. Consequently, to perform the LES phase, the GPU-based EJAYA requires the prior determination of the upper and lower local attraction points (\(PU\) and \(PL\)), as indicated in Equations (2) and (4). This procedure is described in Algorithm 16. ```
1:\(\prime\)* Initialization */
2:Initialize \(numVar\), popSize and \(maxIter\); \(\triangleright\) Host
3:\(X\leftarrow\textsc{Generate\_initial\_population\_kernel}()\);
4:Evaluate_fitness_values_kernel\((X)\);
5:\(X^{old}\gets X\)
6:\(i\gets 1\);
7:\(\prime\)* Main loop */
8:while\(i\leq maxIter\)do\(\triangleright\) Host
9: Determine \(X_{best,i}\) and \(X_{worst,i}\);
10:Determine_attract_points_kernel\(()\);
11:if\(P_{switch}\leq 0.5\)then\(\triangleright\) Host
12:\(X_{i}^{old}\gets X_{i}\)
13:endif
14:Permute_population_kernel\((X_{i}^{old})\);
15:\(P_{select}\leftarrow\textsc{Determine\_exploration\_strategy\_kernel}()\);
16:\(X_{i}^{new}\leftarrow\textsc{EJAYA-driven\_population\_UPDate\_kernel}(X_{i})\);
17:Evaluate_fitness_values_kernel\((X_{i}^{new})\);
18:Greedy_selection_kernel\((X_{i},X_{i}^{new})\);
19:\(i\gets i+1\);
20:endwhile
21:Output the best solution found and terminate. \(\triangleright\) Host and device
```  
**Algorithm 15** GPU-based parallel EJAYA  
Both \(PU\) and \(PL\) are single-dimensional arrays with a length the same as the problem dimension (\(numVar\)). This workload is parallelized simultaneously using a one-dimensional grid arrangement with a number of threads equal to \(numVar\), where each thread, denoted by the variable \(index\), handles the computation of a specific element within the arrays. The formulation of \(PU\) and \(PL\) necessitates the determination of two random numbers (\(rand_{PU}\) and \(rand_{PL}\)) and the population mean (\(popMean\)) prior to the kernel execution. For the GES phase of the GPU-based EJAYA, the historical population (\(X^{old}\)) is determined using Equation (6) and subsequently processed by Equation (7). The determination of the switching probability \(P_{switch}\) is conducted by the host (specifically, in line 11 of Algorithm 15). This approach is preferable as it is more computationally efficient to handle a simple instruction such as an \(if\) statement in the host rather than by the device, considering the overhead related to kernel invocation. For the permutation of the historical population, the first step involves predetermining the random permutation of the position index of the candidate solutions within the population (\(rand\_perm\gets randomize([1,popSize])\)). This permutation is then used as a template to shuffle the order of the candidates, as described in Algorithm 17. ```
1:functionPermute_population_kernel(\(X^{old}\))
2:/*Device code */
3: Determine \(index\) using \(x\) dimension of \(blockDim\), \(blockIdx\), and \(threadIdx\);
4:if\(index\leq popSize\)then
5:\(X^{old}[index]\gets X^{old}[rand\_perm[index]]\).