%
% $Id: report.tex 571 2008-04-20 17:31:04Z rick $
%

\documentclass[12pt,a4paper]{article}

\frenchspacing
\usepackage[english,dutch]{babel}
\selectlanguage{dutch}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{amssymb,amsmath}
\usepackage{wrapfig}
\usepackage{lipsum}
\usepackage{float}

\floatstyle{ruled}
\newfloat{algoritm}{thp}{lop}
\floatname{algoritm}{Algoritm}

\title{\emph{n-Queens} minimale dominatie verzamelingen \\
\large{Chessboard Domination on Programmable Graphics Hardware door Nathan Cournik}}
\author{Rick van der Zwet\\
  \texttt{<hvdzwet@liacs.nl>}}
\date{\today}


\begin{document}
\maketitle
\begin{abstract}
Dit schrijven zal het paper van Nathan Cournik \emph{Chessboard Domination on
Programmable Graphics Hardware}~\cite{CDGPU2006} ---en in het speciaal de
gepresenteerde n-Queens oplossing--- vrij samenvatten in het nederlands en zal
de mening van de ondergetekende op het geheel geven.
\end{abstract}

\section{Inleiding}
\begin{figure}
  \begin{center}
    \includegraphics[width=0.5\textwidth]{pasted1.pdf}
  \end{center}
  \caption{Links; koningin kan dit patroon slaan. Rechts; ongeldige \emph{n-Queens} oplossing, opdat de koninginnen rechtsonder elkaar kunnen slaan}
  \label{fig:patroon}
\end{figure}
Vanwege het het feit dat \emph{n-Queens} een algemeen geaccepteerde termiologie
is, voor het plaatsen van $n$ koningen op een $n*n$ schaakbord zodanig dat de
koningen elkaar niet kunnen slaan, zal dit in het schrijven niet vertaald
worden. Verder zal in de tekst op diverse plekken de orginele engelse bewoordinging
staan om zo terugzoeken en refereren in het orginele paper~\cite{CDGPU2006}
makkelijker te maken.


\section{Minimale dominatie verzameling}
De minimale dominatie verzameling ({\emph{Minimum domination set}}) is
een setup waarbij elk vakje van het schaakbord door ten minste 1 koningin
geslagen kan worden of dat er een koningin op staat. Omdat een koningin een
karakteristiek patroon kan staan (zie Figuur~\ref{fig:patroon}) kan het
minimale aantal koninginnen wat nodig is ook bepaald worden dmv van
formule~\ref{eq:ondergrens}.  
\begin{equation}
y(Q_{n})\geq\frac{n-1}{2}, n\geq1
\label{eq:ondergrens}
\end{equation}


\section{Grafische Verwerking Eenheid}
De Grafische Verwerking Eenheid (\emph{Graphics Processing Unit} ook bekend als
\emph{GPU}) heeft speciale electronica om ervoor te zorgen dat deze snel de
\emph{RGB} waardes van alle beeldpunten kan berekenen in complexe beeldsystemen
met bijvoorbeeld ingewikkende (lees: tijdrovende) berekeningen voor schaduw,
reflextie en intensiteit. Om deze grote hoeveelheid gegevens te verwerken maakt
de \emph{GPU} gebruik een grote hoeveelheid parralelle processoren, welke alle
individueel een deel van de berekeningen op zich nemen.

Recente (electronica) onwikkelingen zoals \emph{CUDA}\footnote{\url{http://en.wikipedia.org/wiki/CUDA}} en (meer generieke implementaties)
\emph{OpenCL}\footnote{\url{http://en.wikipedia.org/wiki/OpenCL}} hebben ertoe
geleid dat de GPU ook door de geprogrammeerd kan worden om specifieke
berekeningen uit te voeren. Figuur~\ref{fig:werking} laat de verschillende
stappen zien die uitgevoerd moeten worden om de \emph{GPU} aan te sturen. Het
is belangrijk om te beseffen dat de \emph{GPU} een heel simpele processor is en
(dus) zeer kleine buffers en instructie set heeft. Verder is het ook cruciaal
te weten dat de \emph{GPU} \textit{niet} direct gebruik gebruik kan maken van
het hoofdgeheugen van de \emph{CPU}, maak dat de invoer en uitvoer altijd eerst
naar/van de \emph{GPU} verplaatst zal moeten worden.
\begin{figure}
  \begin{center}
    \includegraphics[width=0.4\textwidth]{pasted1.png}
  \end{center}
  \caption{\emph{GPU} werking. De verschillende \emph{GPU} processorblokken
worden \emph{kernels} genoemd. De data wordt getransporteerd door verschillende
datakanalen (\emph{streams}) en heeft de vorm van een \emph{framebuffer}, welke
intern als $n * m$ array gezien kan worden. Een \emph{kernel} kan toegepast
worden om een (deel van de) \emph{framebuffer}} \label{fig:werking}
\end{figure}

\section{Algoritme}
Het zoeken van geldige minimale dominatie verzamelingen is een stevige klus,
welke we (in het optimale geval) $n$ koninginnen hebben die we op een $n * n$
schaakbord kunnen plaatsen. Dat levert $(n * n)! - ((n * n)-n)!$ mogelijkheden op.
De \emph{GPU} zal gebruikt worden om oplossingen sneller te controlen en zal
niet gebruikt worden om effientere oplossingen te vinden.

\begin{algoritm}
\begin{verbatim}
01: klaar=nee
02: doe
03: ..bereken potentieel minimale dominatie verzameling 
04: ..plaats in framebuffer
05: ..als (alle pixels zijn gemarkeerd) dan
06: ....klaar=ja 
07: ..eindeals
08: totdat (klaar=ja)
\end{verbatim}
\caption{aanpak minimale dominatie set}
\end{algoritm}
\subsection{Computing the piece configuration}
\begin{itemize}
\item Exhaustive manner
\item Piece configuration stored on the CPU as linked links
\item Lower bound and Upper bound is respected
\end{itemize}

\subsection{Rendered in Framebuffer}
\begin{wrapfigure}{r}{0.4\textwidth}
  \begin{center}
    \includegraphics[width=0.4\textwidth]{pasted4.pdf}
  \end{center}
  \caption{The Toucan}
\end{wrapfigure}
\begin{itemize}
\item GPU supports textures, every piece is a texture
\item Render points on the CPU and offload to the GPU to map texture on
specific place
\end{itemize}

\subsection{Determine Domination (e.g. Mark solution)}
\begin{itemize}
\item Simple approch
\item Sum all pixels of $n*n$ board and match if $sum=n*n$
\end{itemize}

\section{GPU Optimalizations}
\begin{wrapfigure}{r}{0.4\textwidth}
  \begin{center}
    \includegraphics[width=0.4\textwidth]{pasted5.pdf}
  \end{center}
  \caption{The Toucan}
\end{wrapfigure}
\begin{itemize}
\item GPU is able to process all colours at the times
Grid Framebuffer
\end{itemize}
\begin{itemize}
\item GPU has many CPU's called kernels
\item Each kernel can process it's own little block of information
\item Putting multiple possible solutions in one bloc
\end{itemize}

\section{Uitleg probleem}
\section{Theorie}
\section{Aanpak}
\section{Implementatie}
\section{Experimenten}
\section{Conclusie}
\begin{wrapfigure}{r}{0.4\textwidth}
  \begin{center}
    \includegraphics[width=0.4\textwidth]{pasted6.pdf}
  \end{center}
\caption{
Execution times (log scale) of CPU and GPU based minimum domination
implementations computing $y(Q_{n})$. As $n$ increases, the GPU's
speed advantage over the CPU become more evident.}
\end{wrapfigure}

\begin{itemize}
\item Domination texture good mapping between CPU world and GPU world
\item Flexible texture definition without any impact
\end{itemize}

\subsection{Discussion}
\begin{itemize}
\item No significant speedup, claim that $n\geq13$ GPU is \emph{'much'} faster 
\item No scaleable
\end{itemize}

\begin{thebibliography}{2}
\bibitem[DM2003]{DM2003}E. J. Cockayne, emph{Chessboard domination
problems}, \emph{Discrete Math}, 86:1320, 1990.

\bibitem[CDGPU2006]{CDGPU2006}Nathan Cournik,\emph{Chessboard Domination
on Programmable Graphics Hardware}, \emph{ACM SE'06 March
10-­12, 2006}. Melbourne, Florida, USA
\end{thebibliography}
\newpage
\end{document}
