The graphical processing unit is a processor dedicated to rendering graphics and functions as an accelerator such that it offloads the CPU when processing graphical data. The graphical processors architecture has mainly focused on SIMD instructions. Such that it can run several similar instructions simultaneously on several threads. Recently these graphical accelerators have become of interest in the field of high performance computing (HPC). Driven by the gaming industry and their never ending demands for more realistic computer graphics, the GPU has evolved from a primitive processor only able to preform restricted graphics rendering operations to being a programmable processor with huge performance capabilities. The theoretical floating-point processing power of the graphical processor has greatly exceeded that of a CPU.

\begin{figure}[H]
	\centering
		\includegraphics[width=15cm]{report/background/cpugpu.PNG}
		\caption{Image illustrating CPU and GPU transistor usage and layout from \cite{nvidia_cuda_prog_guide}, with permission from NVIDIA}
		\label{cpu-gpu-trans}
\end{figure}

\subsection*{Main aspects of CPU architecture}
The GPU is mainly thought of as an accelerator, and it is therefore important to mention that it is intended to be used in cooperation with a CPU. It is merely an addition and not a substitute. The CPU has different capabilities and as such is a more flexible processing unit. It is designed  to maximize the performance of a single thread of sequential instructions. The CPU is able to perform instruction level parallelism, and as such it can optimize its performance by executing several different instructions simultaneously (SPMD). It also supports flow control that allows it to take advantage of the instruction level parallelism (See Figure \ref{simd-spmd}). Another interesting aspect of the CPU is the use of many transistors to avoid memory latency with the use of caches, see Figure \ref{cpu-gpu-trans}. This is important in the combination of flow control and instruction level parallelism such that one does not have to access main memory every time one changes the instruction performed. And as such it is very important to optimize caching and memory access when programming on the CPU to obtain maximum performance. 

\begin{figure}[H]
	\centering
		\includegraphics[width=8cm]{report/background/simdspmd.PNG}
		\caption{Image illustrating SIMD and SPMD from \cite{nvidia_cuda_prog_guide}, with permission from NVIDIA}
		\label{simd-spmd}
\end{figure}

Recently even CPUs have been adopting parallelism and run with several cores. In this project a Quad-core processor is used, meaning that there are 4 cores in the CPU that can perform calculations. The special feature here is the way in which the caches are used. Each core has a L1 and L2 cache, and they share a L3 cache. Again one sees that the focus is on memory latency and caching of data, but it is important to know that there are three levels of caching here rather than two when programming. This also introduces more advancd scheduling and flow control units, given that the different cores must co-operate and share data. See Figure \ref{cpu-phenom} for a closer look at the architecture of the AMD Phenom used in this project.

\begin{figure}[H]
	\centering
		\includegraphics[width=7cm]{report/background/AMDPhenom.PNG}
		\caption{AMD Phenom Quad-Core Architecture. With data from \cite{amd}}
		\label{cpu-phenom}
\end{figure}

\subsection*{Main aspects of GPU architecture}
The GPU is different in that it focuses the use of the majority of its transistors for data processing and less on cache and flow control. This comes from the nature of the tasks one can perform on the GPU. Since it is mainly used for image processing one tends to perform similar operation on all pixels to be displayed. Pixels are independent from one another and so they can be processed separately, which explains the use of SIMD architecture. The main differences in the GPU and CPU is the use of memory and the access patterns used to access them. On the GPU memory is accessed coherently in the sense that when one pixel reads or writes a value to memory the next/neighboring pixel will do so as well in a few cycles. This means that by arranging the memory correctly one can hide the time of memory access with computations. Because if this simple access pattern the need of a complex flow control disappears resulting in that more transistors can be used for data processing. This is of course both an advantage for tasks that are parallelizable, but it is also limiting for tasks that demand instruction level parallelism or a lot of non coherent memory access.  

The modern GPU is a mixture of programmable and mixed-functions units, and all programmable units in the graphics pipeline now share a single programmable hardware unit. Graphical processors differentiate themselves from the computational processors in that they focus on high throughput and of many parallel process with low latency execution of a single processor. Quite often in scientific and multimedia application one is to preform similar operations on many data. The GPU supports a tremendous amount of threads that execute similar operations in parallel. The combination of low cost, high performance and programmability of the recent GPUs make them an attractive approach in an HPC context. These progressions and developments lead to the GPGPU general purpose graphical processing unit.

Since the GPU is at first and foremost a graphics rendering hardware it is natural that the first attempts to program on it used the graphics API, such as CG, which introduced challenges since the programmer had to familiarize onesself with the API and the API also introduces overhead in communication with the GPU. The interest in being able to program on the GPU in a non graphical context have lead to the development of several programming platforms that overcome the delays of the graphics API and give the programmer more control. Examples of recent platforms are OpenCL, CUDA, Brook for GPU, etc. In this project I will be focusing on the use of the Compute Unified Device Architecture (CUDA), a programming model for GPGPU developed by NVIDIA.
