## 3 GPU Parallelization of Metaphorless Optimization Algorithms
### Principles of CUDA Programming  
GPUs have become an essential component of modern computers. Initially designed for rendering graphics, this hardware has evolved to manage a multitude of graphical elements simultaneously, such as pixels or vertices, for which a large parallel processing capacity is required. The compute unified device architecture (CUDA) [25] is a computing platform developed by NVIDIA that harnesses the power of GPUs for general-purpose parallel computing, making it possible to take advantage of the massive parallelism offered by the GPU for distinct computing tasks. The CUDA Toolkit 12.1 stack acts as a framework that abstracts the inherent complexities of GPU programming. This streamlines communication and coordination between the CPU and GPU, providing an interface to efficiently utilize GPU resources in order to accelerate specific functions within programs. The functions designed to execute highly parallelized tasks on the GPU are referred to as kernels. CUDA functions as a heterogeneous computing framework, consequently dictating a specific execution pattern within kernels. The CPU functions as the host, which is responsible for initiating kernel launches and overseeing the control flow of the program. On the other hand, the kernels are executed in parallel by numerous threads on the GPU, designated as the device. In essence, the host performs tasks that are better suited for sequential execution while the GPU handles the computationally intensive parts of the program in parallel. This relationship is illustrated in Figure 1.  
The computational resources of the GPU are organized into a grid to execute multiple kernels in parallel. This grid acts as an abstraction layer, structuring the available computational elements into blocks, each containing a set number of threads. This thread hierarchy is configurable into grids with one, two, or three dimensions, tailored to accommodate the parallelization needs of a specific kernel. The configuration parameters within the thread hierarchy play a pivotal role in determining GPU hardware occupancy, making them a critical aspect of optimizing resource utilization. Figure 1: Heterogeneous computing architecture with 1D and 2D thread hierarchy in CUDA kernels. In Figure 1, _Kernel A_ showcases a one-dimensional thread-block arrangement, while _Kernel B_ displays a two-dimensional configuration. The illustration also includes the CUDA built-in variables for accessing the grid and block dimensions (_gridDim_ and _blockDim_), block and thread indices (_blockIdx_ and _threadIdx_), and their respective coordinates (_x_ and _y_). These variables also facilitate the unique identification of individual threads within a kernel through a process known as thread indexing. The discrete nature of the host and device hardware involves separate memory spaces, preventing direct data access between them. This necessitates explicit data transfers, resulting in substantial computational overheads and performance degradation. Consequently, meticulous optimization of memory access patterns and a reduction in the frequency of data transfer are crucial to mitigating performance bottlenecks [26]. CUDA also provides access to diverse memory types within the GPU memory hierarchy, which is an important consideration for performance optimization. The memory types encompass global, shared, and local memories, each serving distinct purposes. Global memory is the largest memory segment on the device but also the slowest. It remains persistent throughout kernel execution, serves as the interface for data transfers between the host and device, and is accessible by all threads in the GPU, thus enabling global data sharing. The shared memory, though much smaller, offers greater speed but is exclusive to threads within a block, enabling efficient data exchange among them. Finally, local memory is the smallest in size and is private to individual threads, enabling them to store their specific local variables and facilitate the execution of code tailored to each thread.