## 4 The GPU Architecture and CUDA Programming Model  
Before going into detail on the design options, a description of the GPU architecture and the CUDA programming model is given. The details of the programming model given below apply to the Fermi architecture of graphics cards, such as the ones used in this work. GPUs are powerful and relatively cheap parallel machines, whose initial goal was the improvement of graphics processing. Due to their high computational power, they attracted the interest of many scientists and researchers, who tried to harness the power of GPUs in order to boost the performance of their scientific applications. The first attempts to program GPUs were with the use of OpenGL. Given that many researchers used GPUs for applications other than graphics, NVIDIA introduced in 2007 the Compute Unified Device Architecture (CUDA) in order to make GPUs more friendly to programmers not familiar with graphics. The language used is an extension to the C programming language. After the introduction of CUDA, the use of GPUs was increased significantly. Many papers have been written since then, reviewing the speedups achieved and the new capabilities GPUs give in the solution of scientific problems [52]. Apart from CUDA, OpenCL is a standard that is becoming popular and is about parallel programming in general. However, at the time of writing, CUDA is more widespread, and therefore, it was our choice for writing our algorithms. Many works have been done that investigate how to get the best performance on the GPU [53, 54, 55], including one of our team's [56]. In order to obtain the best performance of a GPU, its architecture should be taken into account, and some limitations should be overcome. GPUs need a large number of threads to be executed to be well utilized and to hide the memory latency. Threads are organized into groups of threads, called blocks of threads, and blocks are organized into grids. Each block contains a three-dimension array of threads, and each grid contains a three-dimension array of blocks. Every GPU has a number of streaming multiprocessors (SM), each one containing a specific number of CUDA cores, which is related to the generation and the model of the graphics unit. All of the cores inside a multiprocessor execute the same command, while cores in different multiprocessors can execute different commands. The part of the code that is executed on the GPU is called a kernel. The programmer is responsible for defining the threads each kernel should execute, and the GPU is responsible for allocating them to its resources. A kernel can have many blocks of threads, each one containing up to 1024 threads. A single block is executed on one multiprocessor. A multiprocessor can execute up to 1536 threads and up to eight blocks simultaneously. Regarding the memory hierarchy, GPUs have a global memory that is relatively slow, but with a high capacity, a shared memory, located in every multiprocessor, which is many times faster, but with only up to 48 KB of space available, and a number of registers that are even faster. All of the threads have access to the global memory, while in the shared memory, only the threads of a block that is executed in the same multiprocessor can have access. The registers store the local variables of each thread. It is of great importance to have many active threads during the execution of the kernel and to find the best configuration of threads per block and blocks per grid in order to achieve the best performance. Furthermore, the transfers to and from the GPU are time consuming; thus, they should be avoided as far as this is possible. Another important aspect in order to obtain the best performance in the GPU is trying to avoid the divergent execution of the threads within a warp. A warp is the number of active threads in a multiprocessor, which is equal to 32.