source: liacs/SCA2010/nQueens/report.tex@ 169

%
% $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{lipsum}
\usepackage{float}

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

\title{\emph{n-Queens} minimale dominantie 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 feit dat \emph{n-Queens} een algemeen geaccepteerde terminologie
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 originele Engelse bewoording
staan om zo terugzoeken en refereren in het originele paper~\cite{CDGPU2006}
makkelijker te maken.


\section{Minimale dominantie verzameling}
De minimale dominantie verzameling ({\emph{Minimum domination set}}) is
een opstelling waarbij met zo weinig mogelijk koninginnen elk vakje
van het schaakbord a) door ten minste 1 koningin geslagen kan worden of b) 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}
Als het een 'gewone' dominantie verzameling is dan hoeft het aantal koninginnen
niet perse minimaal zijn.


\section{Grafische Verwerking Eenheid}
\begin{figure}
  \centering
  \includegraphics[width=0.4\textwidth]{pasted1.png}
  \caption{\emph{GPU} werking. De verschillende \emph{GPU} processor-blokken
worden \emph{kernels} genoemd. De data wordt getransporteerd door verschillende
data-kanalen (\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 op een (deel van de) \emph{framebuffer}.} 
  \label{fig:werking}
\end{figure}
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 ingewikkelde (lees: tijdrovende) berekeningen voor schaduw,
reflectie en intensiteit. Om deze grote hoeveelheid gegevens te verwerken maakt
de \emph{GPU} gebruik van een grote hoeveelheid parallelle processoren, welke alle
individueel een deel van de berekeningen op zich nemen.

Recente (elektronica) ontwikkelingen zoals \emph{CUDA}\footnote{\url{http://en.wikipedia.org/wiki/CUDA}} en een meer generieke implementatie
\emph{OpenCL}\footnote{\url{http://en.wikipedia.org/wiki/OpenCL}} hebben ertoe
geleid dat op de \emph{GPU} in plaats van enkel beeldverwerkingen te doen nu ook 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 hoofd-geheugen van de \emph{CPU}, maak dat de invoer en uitvoer altijd eerst
naar/van de \emph{GPU} verplaatst zal moeten worden.

\section{Aanpak emph{n-Queens} probleem op de \emph{GPU}}
Het zoeken van geldige minimale dominantie verzamelingen is een stevige klus,
waarvoor minimaal (en dus optimale geval) $n$ koninginnen nodig zijn 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 controleren en zal
niet gebruikt worden om effici"{e}ntie oplossingen te vinden. De kracht zit hem in
het feit dat meer oplossingen getest kunnen worden en dus potentieel betere
oplossingen tussen kunnen zitten, welke ook te zien in in
algoritme~\ref{alg:overzicht}. De genereerde potenti"{e}le oplossingen die aan de
\emph{GPU} ter controle aangeboden worden respecteren de boven- en ondergrens.

\begin{algoritm}
\begin{verbatim}
01: klaar=nee
02: doe
03: ..bereken potentieel minimale dominantie verzamelingen
04: ..plaats in framebuffer
05: ..als (alle pixels zijn gemarkeerd) dan
06: ....klaar=ja 
08: totdat (klaar=ja)
\end{verbatim}
\caption{evalueren minimale dominantie set}
\label{alg:overzicht}
\end{algoritm}

\subsection{Detectie algoritme}
\begin{figure}
  \centering
  \includegraphics[width=0.4\textwidth]{pasted4.pdf}
  \caption{Stempels van verschillende schaakstukken, de verschillende groottes zijn noodzakelijk om aan te geven hoe de stempel vergroot of verkleint moet worden}  
  \label{fig:stempels}
\end{figure}
Om snelle detectie mogelijk te maken, wordt er gebruikt gemaakt van een
eigenschap waar een \emph{GPU} in uitblinkt; het '\emph{stempelen}' van objecten in
een raster (welke in traditionele beeldbewerking gebruikt wordt om texturen te
maken). Elk schaakstuk heeft zijn eigen stempel-patroon zoals te zien in
figuur~\ref{fig:stempels}. Hierbij moet opgemerkt worden dat de stempels
allemaal op hun eigen manier schalen.

\begin{figure}
  \begin{center}
    \includegraphics[width=0.4\textwidth]{pasted5.pdf}
  \end{center}
  \caption{Door slim te coderen kunnen meerdere potenti"{e}le oplossingen tegelijk
bekeken worden. Hier wordt gebruik gemaakt van (a) het feit dat de ruimte groter
is dan het 'schaakbord' welke bekeken wordt en (b) een pixel gecodeerd is uit
vier onafhankelijke kleuren} 
  \label{fig:raster}
\end{figure}
Er zijn nog twee eigenschappen van de \emph{GPU} waar dankbaar gebruik van
gemaakt wordt, namelijk kleur en het verschil in grootte van het bord en de
geaccepteerde invoer. Door slim te combineren ---zie figuur~\ref{fig:raster} op pagina~\pageref{fig:raster}---
kan het aantal potenti"{e}le oplossingen dat getest kan worden gemaximaliseerd
worden.

De individuele \emph{kernels} volgen het algoritme~\ref{alg:kernel}. De test of
alle punten gemarkeerd zijn lijkt op het eerste gezicht een lus/loop die test over
alle beeldpunten, echter de \emph{GPU} heeft specifieke instructies om dit
effici"{e}nter uit te voeren.
Voor het plaatsen van de stempels is er een een grafische operatie die
equivalent is aan een \texttt{OF} operatie. Als een \texttt{INVERSE} operatie gebruikt zou
worden om de stempel te plaatsen zou een tweede overlappende stempel onterecht
als niet geraakt gemarkeerd worden.

\begin{algoritm}
\begin{verbatim}
01: voor elke stempels in stempel locatie
02: ..plaats stempel
03: als (alle punten gemarkeerd) dan
04: ..oplossing=ja
\end{verbatim}
\caption{evalueren minimale dominantie set door individuele kernel}
\label{alg:kernel}
\end{algoritm}

\section{Conclusie}
  \begin{figure}
  \centering
  \includegraphics[width=0.4\textwidth]{pasted6.pdf}
  \caption{
  Uitvoer tijden (logaritmische schaal) van de \emph{CPU} en \emph{GPU} gebaseerde minimale dominantie implementaties welke $y(Q_{n})$ uitrekenen. Hoe groter $n$ wordt des te beter de \emph{GPU} gaan presteren in vergelijking met de \emph{CPU}} 
  \label{fig:uitvoertijd}
\end{figure}
Door het toepassen van de \emph{GPU} in het \emph{n-Queens} probleem kunnen
winsten geboekt worden zoals te zien in figuur~\ref{fig:uitvoertijd}\footnote{Gegevens direct uit \cite{CDGPU2006} overgenomen, experiment niet opnieuw uitgevoerd}. 
Het toepassen van \emph{GPU} dominantie textuur technieken lijkt voor dit
specifieke geval een goede vertaling van de traditionele \emph{CPU} wereld en
de \emph{GPU} wereld. De stempels bieden tevens meer vrijheden om alternatieve
'schaakstukken' te onderzoeken.
\subsection{Verder werk} 
Er zal gekeken worden of de generatie van nieuwe oplossingen ook op de
\emph{GPU} gedaan kan worden om zo het probleem van de langzame context
wisselingen op te lossen.
Verder zal er gekeken worden of de codering van de borden op nog een slimmere
manier aangepakt kan worden, in plaats van de kleur in 4 basis-kleuren uit te
splitsen zouden ook de volledige 32 bits (elke kleur is 8 bit) kunnen worden om
nog meer(combinaties) van oplossingen te coderen.

\subsection{Discussie}
De claim dat de \emph{GPU} 'veel' sneller is lijkt me niet gefundeerd in de
grafieken. Beiden lijken erg dicht bij elkaar te blijven en ik zie niet waarom
dit plots veel beter zou worden bij grotere $n$ waarden.
De 'tegel-methode' van figuur~\ref{fig:raster} lijkt in theorie leuk, maar als
de $n$ groter wordt is er grote kans dat de tegels niet meer (goed) passen. Als
de $n$ groter wordt dan in mogelijke invoer is het helemaal niet meer mogelijk.



\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}