\newpage
\section{Parallelle Processors van Client tot Cloud}

\subsectionauthor[C.S. Bras]{Introductie}
Hoge performance van een computersysteem kan betekenen dat de doorvoer van onafhankelijke taken hoog is, dit is waar \textbf{\textit{multicore processors}} van pas komen. In dit hoofdstuk worden toepassingen van deze processors besproken en manieren hoe deze het best te programmeren zijn.
\subsection{De Moeilijkheid van Parallelle Programma's Maken}
Het probleem met parallellisme is niet zo zeer de hardware die hiervoor nodig is maar het feit dat programmeren voor parallelle doeleinden vele malen lastiger is dan voor niet parallelle versies. Een van de redenen hiervan is dat er een dusdanige verbetering moet zijn in de performance of het energie verbruik, ten opzichte van een sequentiële versie, om het nuttig te stellen de extra moeite te nemen om een programma parallel te laten uitvoeren. Een ander probleem dat komt kijken bij het veelvoudig parallel maken van processen is de overhead die nodig is om communicatie tussen meerdere processor cores goed te laten verlopen.

Een snelheidsverbetering bij parallelle programmatuur is makkelijker te verkrijgen wanneer het probleem mee groeit met het aantal parallelle processen. De termen \textbf{strong scaling} en \textbf{weak scaling} worden gebruikt om de snelheidswinst te beschrijven bij het niet mee schalen van een probleem en het proportioneel mee schalen van een probleem met het aantal processors, respectievelijk.


\subsectionauthor[C.S. Bras]{SISD, MIMD, SIMD, SPMD en Vector}
Parallelle hardware kan opgedeeld worden in de volgende categorieën:
	
\begin{itemize}
\item \textbf{\textit{SISD}} \textit{Single Instruction stream Single Data stream}, dit is een standaard \textit{singlecore processor}.
\item \textbf{\textit{MIMD}} \textit{Multiple Instruction streams Multiple Data streams}, dit is een standaard \textit{multicore processor}.
\item \textbf{\textit{SPMD}} \textit{Single Program, Multiple Data streams}, dit is een manier van een \textit{MIMD} processor te programmeren waarbij  een programma op meerdere processors tegelijk draait die vervolgens samenwerken door middel van conditionele statements om zo te bepalen wanneer welke processor welk stuk code uitvoert.
\item \textbf{\textit{SIMD}} \textit{Single Instruction stream Multiple Data streams}, bij een \textit{SIMD} computer wordt dezelfde instructie uitgevoerd op meerdere stukken data, ofwel een \textit{vector}, waardoor deze allemaal op het zelfde moment parallel uitgevoerd worden. \textit{SSE instructies} voor de \textit{x86 instructieset} zijn hier een vorm van.
\end{itemize}

Alle parallelle \textit{SIMD} units staan onderling gesynchroniseerd en luisteren allemaal naar dezelfde instructie die afkomstig is van een enekele \textit{program counter}. Dit lijkt vanuit het standpunt van een programmeur erg veel op \textit{SISD}.

\subsubsection{Vector}

Een zogenaamde \textit{vector architectuur} is een oudere interpretatie van \textit{SIMD}. In plaats van een grote hoeveelheid \textit{ALU's} te gebruiken om parallel addities uit te voeren, wordt de data in \textit{vector registers} geladen waarna dit sequentieel wordt bewerkt door \textit{pipelined execution units} om vervolgens weer terug gestopt te worden in het geheugen.

\subsubsection{Vector versus Scalar}

\textit{Vector} instructies hebben enkele belangrijke eigenschappen ten opzichte van \textit{scalar} instructies.

\begin{itemize}
\item Een \textit{vector} instructie bevat veel werk, wat normaal gesproken een loop zou zijn wordt nu bevat in een instructie, zo is er minder bandbreedte nodig voor het \textit{fetchen} en \textit{decoden} van instructies.

\item Door te specificeren dat er een \textit{vector} berekening moet gebeuren laat de programmeur weten dat de berekeningen niet afhangen van de resultaten binnen de \textit{vector} en zo is het niet nodig om \textit{hazards} af te vangen bij elk onderdeel binnen een \textit{vector}. Ook hoeven \textit{loop branch hazards} niet meer afgevangen te worden omdat een \textit{vector} instructie een gehele loop beschrijft.

\item \textit{Vector} architecturen en compilers maken het makkelijker efficiënte programma's te schrijven wanneer parallellisme op data niveau aanwezig is.

\item Geheugen benadering van een \textit{vector} instructie heeft een bekend patroon, wanneer de onderdelen naast elkaar in het geheugen liggen kunnen deze met slechts een keer het geheugen benaderen uitgelezen worden. Hierdoor wordt er veel \textit{latency} bespaard door niet voor elk \textit{word} apart op het geheugen te hoeven wachten.

\end{itemize}

\subsectionauthor[C.S. Bras]{Hardware Multithreading}
Bij \textit{hardware multithreading} kunnen meerdere \textit{threads} gebruik maken van de functionele delen van een enkele \textit{processor core} om zo de aanwezige hardware zo efficiënt mogelijk te gebruiken. Wanneer een \textit{thread} stil staat, stapt de processor over naar het verwerken van een ander \textit{thread}. Om dit delen mogelijk te maken moet de processor een kopie hebben van de staat van elke individuele \textit{thread}. Ook moet er een manier zijn om snel tussen textit{threads} te kunnen schakelen.

Twee veel gebruikte manieren van \textit{hardware multithreading} zijn \textbf{fine-grained multithreading} en \textbf{coarse-grained multithreading}.

\begin{itemize}
\item \textbf{\textit{Fine-grained multithreading}} schakelt tussen \textit{threads} na elke instructie. Dit resulteert in een doorschoten uitvoer van de \textit{threads}, dit wordt wel zo gedaan dat vastgelopen \textit{threads} worden overgeslagen. Om deze manier nuttig te maken moet de processor elke klok cyclus van \textit{thread} kunnen wisselen. Het nadeel van deze manier is dat individuele \textit{threads} worden uitgesmeerd en dus langer de tijd nodig hebben om uitgevoerd te worden.

\item \textbf{\textit{Coarse-grained multithreading}} is een alternatief op \textit{fine-grained multithreading} waarbij er alleen van \textit{threads} gewisseld wordt bij langdurige wachttijden. Hierdoor is er geen noodzaak om \textit{threads} wisselen binnen een klok cyclus te laten vallen. Een nadeel van deze manier is dat elke keer dat er een langdurige \textit{stall} voorkomt, de \textit{pipeline} geflushed moet worden en weer gevuld moet worden met instructies van een ander \textit{thread} voordat deze uitgevoerd worden, daarom is dit alleen bruikbaar bij langdurige \textit{stalls} waarbij vergeleken de tijd voor het vullen van de \textit{pipeline} verwaarloosbaar klein is.

\end{itemize}

Naast deze vormen is er nog een variant, \textbf{\textit{Simultaneous multithreading (SMT)}}. Dit maakt gebruik van \textit{thread-level} parallellisme. 

\subsectionauthor[C.S. Bras]{Mutlicore en Andere Gedeeld Geheugen Multiprocessors}
Hoewel \textit{hardware multithreading} voor een verbetering in performance hebben gezorgd tegen lage kosten, blijft het lastig om oude programma's om te zetten zodat deze efficiënt draaien op deze hardware. Een oplossing hiervoor is het hebben van een enkele fysieke geheugen locatie die benaderd kan worden door alle processors. Hiermee kunnen alle variabelen van een programma bereikt worden door elke processor op elk willekeurig moment. Deze vorm van een multiprocessor wordt ook wel \textbf{\textit{shared memory multiprocessor (SMP)}} genoemd.

\textit{Single address space multiprocessors} komen in twee stijlen:
\begin{enumerate}

\item \textbf{\textit{Uniform Memory Access (UMA)}} hierin is de \textit{latency} van elk \textit{word} in het geheugen hetzelfde ongeacht welke processor het opvraagt.

\item \textbf{\textit{Nonuniform Memory Access (NUMA)}} hierin ligt de \textit{latency} aan welke processor een stuk geheugen aanroept.
\end{enumerate}

Aangezien parallelle processors bewerkingen uitvoeren op dezelfde data moet er een mechanisme zijn die er voor zorgt dat twee processors niet tegelijk aan dezelfde data werken. Deze coördinatie wordt \textbf{synchronisatie} genoemd. Een manier om dit te doen is om er voor te zorgen dat een van de processors een gedeelde variabele op slot kan zetten zolang als dat deze een bewerking hier op uitvoert.
\newpage
\subsectionauthor[C.S. Bras]{Introductie tot Grafische Processing Units}
\textbf{\textit{Graphics Processing Units (GPU's)}} verschillen in de volgende opzichten van standaard \textit{CPU's}:

\begin{itemize}
\item Een \textit{GPU} is een \textit{accelerator} die als supplement wordt toegevoegd aan een \textit{CPU} en hoeft daarom ook niet alle taken te kunnen doen die een \textit{CPU} kan. Hierdoor kan de \textit{GPU} al de resources focussen op beeldverwerking en de \textit{CPU} de rest laten doen.

\item Een \textit{GPU} werkt met honderden megabytes tot gigabytes in plaats van honderden gigabytes tot terabytes. Een \textit{GPU} gebruikt dan ook geen \textit{multi level caching}. In plaats hiervan gebruiken ze \textit{hardware multithreading} om \textit{latency} van het geheugen te overkomen.

\item \textit{GPU} geheugen is gebouwd rondom hoge bandbreedte in plaats van lage \textit{latency}.

\item Doordat er gerekend wordt op veel \textit{threads} om de geheugen bandbreedte hoog te houden heeft een \textit{GPU} veel parallelle processors, veel meer dan een standaard \textit{CPU}.
\end{itemize}

\subsubsection{Introductie tot de NVIDIA GPU Architectuur}
Net zoals met een \textit{vector architectuur} werken \textit{GPU's} alleen optimaal met data-level parallelle problemen. In tegenstelling echter tot de meeste \textit{vector architecturen}, rekent een GPU ook op hardware \textit{multithreading} binnen een enkele \textit{multithreaded SIMD processor.} Aangezien NVIDIA meerdere producten aanbiedt met verschillende hoeveelheden \textit{multithreaded SIMD processors} wordt \textit{Thread Block Scheduler} hardware gebruikt om te regelen welke processor welk blok aan \textit{threads} ontvangt, zie figuur 9 voor een schematische tekening van een \textit{multithreaded SIMD processor}.

\begin{center}
\begin{figure}[H]
\noindent
\includegraphics[width=\textwidth]{Block_Diagram}
\caption{Schematische tekening van het datapad van een \textit{multithreaded SIMD processor} }
\label{fig:figure9}
\end{figure}
\end{center}

\subsubsection{NVIDIA GPU Geheugen Structuren}
In figuur 10 wordt het geheugen structuur van een \textit{NVIDIA GPU} schematisch weergegeven. Het geheugen op de chip dat lokaal is voor elke \textit{multithreaded SIMD processor} wordt \textit{Local Memory} genoemd. Dit geheugen wordt gedeeld door SIMD Lanes binnen een SIMD processor maar niet door meerdere SIMD processors. In plaats van een grote caches gebruikt een GPU kleinere \textit{streaming caches} waarbij er gerekend wordt op veel \textit{multithreaded SIMD }instructies om de \textit{latency} van het \textit{DRAM} te verbergen.

\begin{center}
\begin{figure}[H]
\noindent
\includegraphics[width=\textwidth]{Geheugen}
\caption{GPU geheugen structuur}
\label{fig:figure10}
\end{figure}
\end{center}

\subsectionauthor[C.S. Bras]{Clusters, Magazijn Grootte Computers, en andere Message-Passing Multiprocessors}
Een alternatief op het delen van adres ruimte is dat elke processor zijn eigen fysieke adres ruimte heeft. Nu moeten deze processors echter wel uitdrukkelijk communiceren via \textbf{\textit{message passing}}, ook wel gezien als de naam van dit soort processors. 

\textit{\textbf{Clusters}} zijn een collectie computers die via een netwerk aan elkaar verbonden staan om zo samen een multiprocessor te worden. Elke computer draait zijn eigen besturingssysteem en eigen processor wat weer een multiprocessor kan zijn zoals hiervoor beschreven. Het grote voordeel van een eigen geheugens hebben ten opzichte van een \textit{shared memory multiprocessor} is dat het gehele systeem niet stil gelegd hoeft te worden wanneer een individuele \textit{node} vervangen moet worden, ook is het bij een cluster makkelijk om uit te breiden zonder het programma wat hier op draait stil te hoeven leggen.

Tegenwoordig hebben grote internet bedrijven niet meer genoeg aan normale clusters, daarom zijn er \textit{Warehouse-Scale Computers (WSC)} die qua grootte een geheel magazijn innemen. Hoewel deze \textit{WSC's }overeenkomsten hebben met servers, zijn er drie grote verschillen:
\begin{enumerate}
\item \textit{Ruim, makkelijk parallellisme:} Een server ontwerper moet rekening houden of de toepassing van het systeem wel genoeg parallellisme zal hebben om een grote hoeveelheid parallelle hardware noodzaak te maken. Ook moet er rekening gehouden worden met de kosten van de communicatie hardware om gebruik te maken van dit parallellisme. Bij een \textit{WSC} echter, worden vele stukken verschillende data aangeleverd die allemaal apart bewerkt moeten worden waarbij geen verdere communicatie tussen hardware nodig is en ook verder niet afhangen van elkaar.

\item \textit{Operationele kosten:} Normaal gesproken ontwerpen server architecten een systeem voor maximale performance binnen een bepaald budget en wordt er alleen rekening gehouden met de koelingscapaciteit van de behuizing zonder dat er rekening wordt gehouden met de kosten voor de benodigde energie van het draaien van de server. Bij WSC's ligt dit echter anders aangezien deze in veel langere tijd worden afgeschreven waardoor de kosten voor het operationeel houden veel meer oplopen dan bij traditionele servers.

\item \textit{Grootte en de bijkomende problemen en voordelen hiervan:} Doordat voor een \textit{WSC} veel servers nodig zijn kan dit in bulk met korting gekocht worden. Zo is er ondanks het feit dat er weinig \textit{WSC's} zijn toch nog spraken van schaalvoordeel. Deze schaal brengt echter als problemen mee dat er rekening gehouden moet worden met het aantal falende systemen. Ook als zal er maar een klein percentage dagelijks falen, wanneer er honderdduizenden systemen zijn komt dit uiteindelijk toch neer op een relatief groot absoluut aantal.
\end{enumerate}

\subsectionauthor[C.S. Bras]{Introductie van Multiprocessor Netwerk Topologieën}
Multiprocessor chips hebben netwerken op de chip nodig om met meerdere cores te kunnen communiceren, clusters hebben lokale netwerken nodig om tussen de verschillende servers te kunnen communiceren. Dit stuk kijkt naar de voor en nadelen van beide interconnectie topologieën. In het figuur hieronder is een schematische weergave te zien van een \textit{ring} topologie, de processor knooppunten zijn zwart gekleurd en de netwerk switches worden aangegeven met blauwe cirkels. In tegenstelling tot een \textit{bus}, kan een ring meerdere data uitwisselingen tegelijk afhandelen.

\begin{center}
\begin{figure}[H]
\noindent
\includegraphics[width=\textwidth]{Ring_Topologie}
\caption{Schematische weergave van een ring netwerk topologie met processor knooppunten als zwarte vierkanten en netwerk switches als blauwe cirkels}
\label{fig:figure11}
\end{figure}
\end{center}

Doordat er veel verschillende soorten netwerktopologieën bestaan moeten er punten zijn waarop de performance kan worden vergeleken. Het eerste punt is \textit{\textbf{totale netwerk bandbreedte}}, dit is de bandbreedte van elke link vermenigvuldigd met het totaal aantal links. Dit is wat in optimale omstandigheden de hoogst haalbare bandbreedte is. Een ander punt waarop vergeleken kan worden is de \textit{\textbf{tweeëndeling bandbreedte}}, dit gaat uit van minder gunstige omstandigheden en wordt berekend door de machine in twee helften te verdelen om vervolgens de bandbreedte van de twee links die deze denkbeeldige lijn doorkruisen bij elkaar op te tellen.

Een netwerk met een kleine switch op elk knooppunt wordt een \textit{\textbf{multistage netwerk}} genoemd. In \textit{figuur 12} zijn enkele populaire vormen van \textit{multistage netwerken} te zien. 

\begin{center}
\begin{figure}[H]
\noindent
\includegraphics[width=\textwidth]{Multistagenetwork}
\caption{Populaire \textit{multistage} netwerktopologieën voor acht knooppunten. De links zijn een richting, data komt links binnen en gaat rechts weer naar buiten.}
\label{fig:figure12}
\end{figure}
\end{center}




