## 3 GPU Parallelization of Metaphorless Optimization Algorithms
### Methodology Used for GPU-Based Parallelization
Traditional methods for determining this configuration involve iterative experimentation, optimization, and profiling, which can be time-consuming. In the proposed GPU-based parallelization approach, a dynamic and generalized method to automatically determine optimal GPU hardware occupancy was developed, and its overview is presented in Algorithm 9. This process involves a function that predicts the launch configurations for each kernel using CUDA runtime methods available in devices supporting CUDA 6.5 or higher, utilizing parameters such as data size, supported block size, and kernel memory requirements. To suit the algorithmic data being processed by optimization algorithms, two kernel launch configuration functions were created, one for 1D and another for 2D thread-block kernels. This approach ensures that kernels are adaptable to diverse GPU hardware configurations and are inherently structured for horizontal scalability through the utilization of additional available threads, all achieved without the need for modifications to the parallel implementation. Although automatic methods present the potential for achieving maximum GPU occupancy, they may not consistently produce the most efficient parameters tailored to a specific hardware setup. In this study, the method for automatically determining optimal GPU hardware occupancy has undergone revision. The modification entails the incorporation of a parameter designed to constrain the suggested block size (i.e., the number of threads allocated for computation in each block used) to a multiple of the supported warp size by the GPU (see line 3 of Algorithm 9). The warp size, which denotes the minimum number of threads that can be concurrently executed in CUDA, is inherently dependent on the GPU architecture and can be automatically derived from the hardware parameters. Empirical tests have revealed that constraining the suggested block size to twice the warp size yields an additional average performance improvement of 19.8% compared to the preceding version of the automated launch configuration method when using the RTX 3090 GPU. This enhancement is primarily attributed to the facilitated coalesced memory access and optimized instruction dispatch achieved through the harmonization of block size. Figure 2: Population thread mapping showing a 2D grid kernel and its relation to data memory. ```
1:functionkernel_launch_configuration(\(kernel\_fn\), \(kernel\_args\), \(data\_dim\))
2: /* Constrain the number of threads per block */
3: \(max\_block\_size\gets 2\)\(\times\) device_warp_size;
4: /* Get the optimal launch configuration */
5: \(launch\_conf\leftarrow\)cudaOccupancyMaxPotentialBlockSize(\(kernel\_fn\), \(max\_block\_size\));
6: /* Determine threads per block */
7: \(threads\leftarrow\) Determine_threads(\(data\_dim\), \(launch\_conf\));
8: /* Calculate required blocks */
9: \(blocks\leftarrow\) Determine_blocks(\(data\_dim\), \(threads\));
10: /* Launch the kernel */
11: Launch_kernel(\(kernel\_fn\), \(kernel\_args\), \(threads\), \(blocks\)). 12:endfunction
```  
**Algorithm 9** Function to determine kernel occupancy  
While both shared memory and local memory exhibit faster access compared to global memory due to their proximity to processing units, their limited size and accessibility pose challenges when handling extensive data volumes. Therefore, the proposed GPU-based implementation prioritizes the use of larger global memory. This memory type offers substantial storage capacity, accommodating extensive datasets, variables, diverse data types, and complex data structures. Moreover, it aids in thread synchronization, ensuring that when a kernel concludes execution and the subsequent one initiates, all processed data synchronizes in the GPU global memory. In scenarios where quicker memory access is more efficient, this approach presents a drawback by potentially limiting computational task performance.