
Parallel computing is a form of computation where many calculations are performed simultaneously. This is depending on that large problems can be divided into smaller ones such that one can calculate them concurrently.  There are several different forms of parallel computing bit-level, instruction level, data and task parallelism. Parallel computing has been around for quite a while now, but has lately been given more attention since the limitations of power consumption and physical limitations of frequency levels on computational hardware have started to stagnate. This gave birth to the multi-core CPUs and created a paradigm in computer architecture.

\begin{figure}[h]
\centering
\includegraphics[width=10cm]{report/background/Amdahlslaw.png}
\caption{Image illustrating Amdahl's law $^2$ }
\label{amdalslaw}
\end{figure}

\footnotetext[2]{http://en.wikipedia.org/wiki/File:AmdahlsLaw.svg, accessed 2009-09-08. Available to all under the license of creative commons}

\subsection*{Amdhal's Law}
When generally speaking of how effective a parallel algorithm is one usually mentions the speedup factor (how much faster a parallel algorithm runs compared to a sequential one). The potential speedup of an algorithm on a parallel platform can be measured with the help of Amdahl's law. This law states that all parallel computations are limited with a sequential part of their code and thus their speed up is limited by this part as well. Amdahl's law is stated as in Equation \ref{amdahl} \cite{Wilkinson} and illustrated in Figure \ref{amdalslaw}. S is the speedup, and P is the portion of the code that is parallelizable and is a value lesser than 1 and greater than zero.

\begin{equation}
S = \frac{1}{1-P}
\label{amdahl}
\end{equation}

\subsection*{Gustafson's Law}
Another law closely related to Amdahl's law in computer science is Gustafson's law \ref{gustafson} \cite{Wilkinson}. Here S is the speedup,  P is the number of processors and $\alpha$ is the non-parallelizable part of the program.  Amdahl has made the assumptions that the sequential part of the program is independent from amount of processors one has while Gustafson believes that this is not the case.

\begin{equation}
S(P) = P - \alpha (P-1)
\label{gustafson}
\end{equation}

\subsection*{Speed Up Limitations}
Ideally one should be able to gain linear speedup meaning that one would increase the speedup with the amount of processing units available. For example if one has two processors then it should take half the time to execute a program since two are working on the problem. But, this is rarely the case since there are some factors that limit speedup that one should look out for when programming in parallel. One is that not all problems can be parallelized at all time, they might have some sequential parts, which means that while one processor is executing the sequential part the other is idle. This results in sub-linear speedup. Another fact is that not all algorithms can be executed in parallel without extra computational cost. Some implementations might have this extra cost in the parallel version and this will also result in sub linear speedup. 

Other speedup limitations are I/O and communication time between processors. In some systems not all processors are capable of reading and writing to I/O units which means that the other processors will have to wait, resulting in lesser speedup. Often processes have to communicate with each other like in the case of border exchanging. This will result in time spent communicating which is not present in the sequential algorithm. This will also result in sub linear speedup. These effects become more evident when dealing with large datasets since one can use a lot of time reading and writing data, and more data will have to be communicated between processes.

\subsection*{Data Dependencies}

Data dependencies are a common issue in parallel programming and should be understood to perform good parallel implementations of algorithms. The fact that no program can run faster than its longest chain of dependencies will prevent a lot of speedup, this is known as the critical path. This is because some calculations normally depend on other calculations and if they are not completed then one cannot proceed to the next step i.e creating a delay. However, most algorithms do not consist of a long chain of dependent calculations and can therefore run concurrently.

\begin{equation}
I_j \cap O_i = Ø
\label{bern1}
\end{equation}

\begin{equation}
I_i \cap O_j = Ø
\label{bern2}
\end{equation}

\begin{equation}
O_i \cap O_j = Ø
\label{bern3}
\end{equation}

A good description of dependencies are the Bernstein conditions \cite{Wilkinson}. These describe when two program fragments, denoted $P_i$ and $P_j$, are independent and can be executed in parallel. For $P_i$ let $I_i$ be the input and $O_i$ be the output for the program. For $P_j$ the input will be $I_j$ and output $O_j$. Now we can say that $P_i$ and $P_j$ are independent if they satisfy the following conditions \ref{bern1}, \ref{bern2} and \ref{bern3} (from \cite{Wilkinson}).

\subsection*{Types of Parallelism}

\subsubsection*{Instruction-Level Parallelism}
Computer programs are in essence a collection of instructions. Some instructions have dependencies, such as an instruction should be performed before another can use its results and so on. The instructions of a program can be collected into groups and executed in parallel without effecting the results of the program. This is often seen in pipelining architectures. In addition to instruction level parallelism from pipelining, some processors can execute more than one instruction at a time. These are known as super scalar processors. Instructions can be grouped only if there are no data dependencies between them.

\subsubsection*{Data Parallelism}
In data parallelism one is focusing on distributing work on several computing nodes, and this is often inherent in program loops. In loops one is often performing similar functions or calculations on a large data set and if these are independent of previous states one is able to calculate these concurrently. Many scientific and engineering applications have data parallelism, it is also present in GPU applications. 

\subsection*{Classes of Parallel Computers}
There are many classes of parallel computers and they are usually not mutually exclusive. The classes are as follows: multi-core computing, symmetric multiprocessing, distributed computing, cluster computing, massive parallel processing. There are also specialized parallel computers such as FPGA (field programmable gate arrays), GPGPU, application specific integrated circuits and vector processors. I will be focusing on Multi-core CPUs and GPGPU because these are within the scope of this project. 

\subsubsection*{Multi-core CPU}
A multi-core processor is a processor with several execution units, also known as cores. This is different from a super-scalar processor in the fact that super-scalar processors issue multiple instructions per cycle from multiple instruction streams. Each core in a multi core processor can be super scalar. An interesting attribute with these multi-core processors is that they can perform simultaneous multi-threading. This means that while one execution unit is performing calculations on multiple threads and a thread is idle, another execution unit can do calculations on the idle threat.

\subsubsection*{GPGPU}
General purpose computing on the GPU is a relatively new trend in computer engineering research. The GPU is an accelerator and co-processor that has been optimized to handle graphical tasks. Computer graphics processing is generally influenced by large data parallelism operations and in particular linear algebra matrix operations. Previously the GPGPU was normally programmed using the graphics API, such as the use of textures to perform calculations. Recently several new programming languages and platforms have been developed for the purpose of general purpose computing on the GPU. NVIDIA and AMD have introduced the CUDA and CTM programming environments  respectively. Other GPU programming languages are BrookGPU, PeakStream and RapidMind. There is also the Introduction of a the Framework OpenCL for writing programs on heterogeneous platforms consisting of CPUs, GPUs and other processors.  The scope of this project extends to the use of CUDA, the programing platform developed by NVIDIA.
