\chapter{Background and Related Work}
\label{chapter:background}


\section{Coprocessors}

For some problems, a generalized processor, like the commonly found x86 processor,
is unable to deliver either adequate results or adequately fast results
\cite{chirkin2013photon}. This can be due to a variety of concerns. Commonly for
applications dealing with graphics or simulations, it is a problem of throughput.
For other fields like computer security, coprocessors enable higher and more 
reliable levels of security \cite{santos2009towards,yee1994using}.
To remedy these concerns, specialized hardware called coprocessors are often used. These 
coprocessors allow the either the CPU or the programmer to off-load work from
the CPU to a chip more suited to the problem domain. We are most interested in
coprocessors which facilitate floating point mathematics.


\subsection{Floating Point Units}

Floating point arithmetic is at the heart of modern graphical and scientific
applications. Nearly all modern implementations of floating point math follow
the IEEE Standard\cite{ieee754}. Before the IEEE standard became widespread,
there are many complications with using one of the various floating point
arithmetic libraries. These complications were not limited to a lack of portability 
or strange rounding rules. Word lengths, exponent biases and precision varied greatly
between implementations \cite{kahan1996ieee,overton2001numerical}. Due to the complex nature
of the IEEE standard, it is almost necessary to implement the standard in hardware
for it to be usable in any application requiring it. This meant that until CPU
manufacturers had enough room on the chip to implement the standard, they
shipped a separate Floating Point Unit (FPU) to help accelerate any applications
using floating point math. Any modern CPU will now ship with FPU, and most ship with
some form of a Streaming SIMD Extensions (SSE) instruction set.

Starting with the Pentium III, CPUs began to include extra registers for use with
SSE instructions. This instruction set allows the CPU to execute many floating
point operations in a single instruction. For example, an application is
working with vectors where each vector has three values representing X, Y and Z.
Normally to add two vectors together, each value in each of the vectors would need
to be read from memory one by one, then added and then saved one by one. Using
a SIMD instruction each vector is read at once, then add at once and then
saved back to memory at once as shown in Figure~\ref{fig:simd_add}. This can be
done while the CPU is working on something else leading to massive speed 
increases when done properly. This concept of a Single Instruction Multiple Data
(SIMD) coprocessor is the driving idea for the architecture of the Graphics 
Processing Unit.

\begin{figure}
\begin{center}
\includegraphics[height=\textheight,width=\textwidth,keepaspectratio]{figures/SIMD.pdf}
\end{center}
\caption{An example of the difference between a Scalar addition of a vector and SIMD addition of a vector}
\label{fig:simd_add}
\end{figure}


\subsection{Graphic Processing Units}

Initially rendering tasks were handled in software using the CPU. Commonly, an
FPU was used to help provide newer and better graphical techniques at an
acceptable level of performance. However as the focus of the graphical techniques
moved from 2D to 3D, specialized coprocessors were designed to keep up with
increasingly high standards of performance. The design
settled on a massively parallel SIMD architecture in which many pipelines are 
used to take geometry data, in the form of vertices, and transform it into color
values to be displayed on the screen. Figure~\ref{fig:gl_pipe} shows
a simplified version of this pipeline.  This SIMD architecture enables many simple
processors to work together to produce output simultaneously.

\begin{figure}
\begin{center}
\includegraphics[height=\textheight,width=\textwidth,keepaspectratio]{figures/graphics_pipeline.png}
\end{center}
\caption{A simplified illustration of the graphics pipeline\cite{groff2010pipeline}}
\label{fig:gl_pipe}
\end{figure}

Initially the design of GPUs was that vertex processors would handle transforming
vertices into the required perspective. From there vertices are rasterized into
the view port, and a fragment processor would calculate the color for each pixel of
the screen. Initially this functionality was mostly fixed with only some small changes able
to made, using an Application Programming Interface (API) like OpenGL
\cite{schreiner2013open} or Direct3D \cite{gee2008introduction}. As the demands
of these API became wider and wider in scope, the fixed functionality of the
pipeline was opened up. Programs called shaders could be written for the vertex
and fragment processors. Shader programs initially were limited but overtime
have become more expressive and are the backbone of nearly all modern graphical
techniques. Each API provides a language to write the shader programs and over
time these languages \cite{gray2003microsoft,glslguide,mark2003cg}.
As time progressed, addition stages were added to pipeline. Each new shader
processor enabling application programmers more functionality. For example, the 
geometry shader enabled new geometry to be procedurally generated on the GPU
critical for effects like Marching Cubes\cite{crassin2007opengl} to be efficiently
done on the GPU. In addition to improving the programmablity of the GPU, other
techniques like framebuffer objects\cite{green2005opengl} and transform feedback
\cite{transformfeedback} allow application programmers to save results from the
GPU back to the CPU for use in further rendering techniques.

\subsection{General Purpose Graphic Processing Units}

As GPU manufacturers packed more and more vertex and fragment processors into
their GPU chips, the appeal of using the GPU for things other than graphics grew.
By using the fragment shader in conjunction with framebuffer objects, it was
possible to compute many things in parallel
\cite{hoang2008wildfire,hoang2010vfire,luebke2006gpgpu}. 
This practice called General 
Purpose GPU (GPGPU) programming allowed many scientific application programmers
to accelerate all kinds of calculations. However it required not only knowledge of the
problem domain, but also knowledge of the underlying graphic constructs and the API
to control it. Despite this limitation, GPGPU enabled some applications to achieve
performance gains\cite{fok2007evolutionary}.


\subsubsection{CUDA}

As GPGPU became more widespread GPU, manufacturers began to take note.
Starting with the G80 series of graphics cards, NVidia unveiled a new underlying
architecture called Compute Unified Device Architecture (CUDA) to ease the struggles
of programmers attempting to harness the GPU's computing power
\cite{kirk2007nvidia}. While the new architect did not change the pipeline for
graphics programmers, it did unify the processing architecture underlying the
whole pipeline. Vertex and fragment processors were replaced
with groups of Thread Processors (CUDA Cores) called Streaming Multiprocessors(SM). 
Initially with the G80 architecture, there were 128 cores grouped into 16 SMs
shown in Figure~\ref{fig:g80_arch}. The most recent architecture has 2880 cores 
grouped into 15 SMs\cite{keplerwhite}. Figure~\ref{fig:kepler_sm} shows the
evolution of the Streaming Multiprocessor architecture. In addition to the new
chip architecture, CUDA also included a new programming model which allowed
application programmers to harness the data parallelism present on the GPU. The
primary abstractions of the programming model are kernels and threads. Each
kernel is executed by many threads in parallel; CUDA threads are very lightweight
and allow many thousands of threads to be executing on a device at any given time.

\begin{figure}
\begin{center}
\includegraphics[height=\textheight,width=\textwidth,keepaspectratio]{figures/g80_arch.png}
\end{center}
\caption{A block diagram of the G80 architecture\cite{kirk2007nvidia}}
\label{fig:g80_arch}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics[height=\textheight,width=\textwidth,keepaspectratio]{figures/kepler_sm.png}
\end{center}
\caption{A block diagram of the Kepler architecture SMX\cite{keplerwhite}}
\label{fig:kepler_sm}
\end{figure}


The programming model is exposed to the application programmer by an extension of
the C programming language commonly referred to as CUDA\cite{nvidia2013guide}. 
CUDA kernels are executed by threads, each is given an ID which is used to
differentiate each thread's behavior. Unlike the previous GPGPU methods, threads
are able to access and read/write to any memory location as needed. Threads can 
be additionally be grouped into blocks by the programmer giving multiple 
benefits: shared memory and shared cache within the block reducing memory
overheads and thread synchronization enabling the programmer to more easily 
model some algorithms. Overall, CUDA gave programmers more freedom to design
algorithms and data structures specifically for the hardware of the GPU.

However CUDA comes with some trade-offs. Due to the design of the underlying
hardware, there are concerns the programmer must keep in mind. Care must be taken
to ensure that groups of executing threads (warps) access contiguous chunks of 
memory as often as possible in order to make the most memory access coalescing provided by
the hardware. Additionally since threads in a warp execute instructions in lock
step heavy use of control flow primitives (if, for, while) can cause threads in
warp to be inactive as sections of the warp take divergent paths
\cite{ryoo2008optimization}. Additionally due to its heritage from C, the low
level nature of CUDA means that the programmer must be familiar with the hardware
to get an acceptable level of performance.

\subsubsection{Thrust}

In many ways, the programming model presented by CUDA is a match to the programming
model of C. For some programmers the programming model of C++ is more desirable;
fortunately, the Thrust framework exists. Following the motivations of the
Standard Template Library (STL) of an efficient, comprehensive and extensible
approach to designing both algorithms and data structures \cite{stepanov1995standard},
Thrust provides a set of common STL operations and data structures which run on
the GPU. This allows an application programmer using C++ to accelerate common
operations like sorting, transforming and reducing\cite{nvidia2014thrust}. Thrust
provides these features while maintaining interoperablity with CUDA C; allowing
programmers easier access to hard to implement parallel primitives that have been
highly optimized like a radix sort which can provide a speed up (ranging from 2-5
times faster than a comparable sorting routine on an 8 core CPU)
\cite{satish2009designing}. These features make Thrust an appealing tool to
provide easier access to GPU acceleration for many applications.

\section{Related Work}

At the time of the writing of this thesis the use of GPUs as a massively parallel
math coprocessor is increasing. This is due not only to their increase in power
over the years but also to their increasing ubiquity. Because of this their use
is becoming more common in fields which require a large amount of throughput for
any application. For instance, CUDA has been used to accelerate N-body simulations,
providing extremely large gains against tuned serial implementations and modest
gains over tuned implementations for the CPU\cite{belleman2008high,nyland2007fast}.
