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

%
% $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 dominerende verzamelingen \\
\large{Chessboard Domination on Programmable Graphics Hardware door Nathan Cournia}}
\author{Rick van der Zwet\\
  \texttt{<hvdzwet@liacs.nl>}}
\date{\today}


\begin{document}
\maketitle
\begin{abstract}
Dit schrijven zal het paper van Nathan Cournia \emph{Chessboard Domination on
Programmable Graphics Hardware}~\cite{CDGPU2006} ---en in het bijzonder 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, omdat 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$ koninginnen op een $n \times n$ schaakbord zodanig dat de
koninginnen 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 in en refereren naar het originele paper~\cite{CDGPU2006}
makkelijker te maken.


\section{Minimale dominerende verzameling}
Een dominerende set is een verzameling koninginnen, die tezamen alle velden
bereiken. Een minimale dominerende 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 direct bereikt kan worden of b) bezet is 
door een koningin. Omdat een koningin een \emph{karakteristiek patroon} kan slaan (zie
Figuur~\ref{fig:patroon}) kan het minimale aantal koninginnen dat nodig is
bepaald worden door middel van Formule~\ref{eq:ondergrens}\footnote{Bewezen in \cite{DM2003}.}:  
\begin{equation}
y(Q_{n})\geq\frac{n-1}{2}, n\geq1
\label{eq:ondergrens}
\end{equation}
Hierbij is $n$ de hoogte van het bord. De knopen van $Q_{n}$
zijn genomen van een $n \times n$ bord met $n^{2}$ knopen. Als knoop $a$
door middel van het \emph{karakteristiek patroon} van een koningin vanuit $b$
bereikt kan worden, wordt er een tak tussen deze knopen gevormd. Dit geheel (de
knopen en takken) is $Q_{n}$. De $y(Q_{n})$ is dan het minimale aantal
koninginnen dat men kan plaatsen om zo een minimale dominerende verzameling
te bereiken. 


\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 \times m$ array gezien kan worden. Een \emph{kernel} kan toegepast
worden op een (deel van de) \emph{framebuffer}. Illustratie uit \cite{WPCUDA}.}
  \label{fig:werking}
\end{figure}
De Grafische Verwerking Eenheid (\emph{Graphics Processing Unit}, ook bekend als
\emph{GPU}) heeft speciale elektronica om ervoor te zorgen dat deze snel de
\emph{RGB} waardes van alle beeldpunten kan berekenen in complexe beeld-systemen
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 beeld verwerkingen 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 instructieset 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}, maar dat de invoer en uitvoer altijd eerst
naar/van de \emph{GPU} verplaatst zal moeten worden.

\section{Aanpak $n$-Queens probleem op de \emph{GPU}}
Het zoeken van geldige minimale dominerende verzamelingen is een stevige klus,
waarvoor minimaal (in het optimale geval) $n$ koninginnen nodig zijn die we op een $n \times 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}nte oplossingen te vinden. De kracht zit hem in
het feit dat meer oplossingen getest kunnen worden en er dus potentieel betere
oplossingen tussen kunnen zitten, wat ook te zien is in
Algoritme~\ref{alg:overzicht}. De genereerde potenti"{e}le oplossingen die aan de
\emph{GPU} ter controle aangeboden worden respecteren eventuele bekende boven-
en ondergrenzen \footnote{Zie voor meer bekende boven- en ondergrenzen onder
andere de papers genoemd in \cite{CDGPU2006}[sectie 2, pagina 62].} zoals
Formule~\ref{eq:ondergrens}.
\newpage


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

\subsection{Detectie algoritme}
\begin{figure}[h]
  \centering
  \includegraphics[width=0.4\textwidth]{pasted4.pdf}
  \caption{Stempels van verschillende schaakstukken, de verschillende groottes zijn noodzakelijk om aan te geven hoe het stempel vergroot of verkleind 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'' dat 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 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 alle stempels in stempel locatie
02: ..plaats stempel
03: als (alle punten gemarkeerd) dan
04: ..oplossing=ja
\end{verbatim}
\caption{evalueren minimale dominerende set door individuele kernel}
\label{alg:kernel}
\end{algoritm}

\section{Conclusie}
  \begin{figure}
  \centering
  \includegraphics[width=0.4\textwidth]{pasted6.pdf}
  \caption{
  Uitvoertijden (logaritmische schaal) van de \emph{CPU} en \emph{GPU} gebaseerde minimale dominerende implementaties welke $y(Q_{n})$ uitrekenen. Hoe groter $n$ wordt des te beter de \emph{GPU} gaat presteren in vergelijking met de \emph{CPU}.} 
  \label{fig:uitvoertijd}
\end{figure}
Door het toepassen van de \emph{GPU} op het \emph{n-Queens} probleem kunnen
winsten geboekt worden zoals te zien is in Figuur~\ref{fig:uitvoertijd}\footnote{Gegevens direct uit \cite{CDGPU2006} overgenomen, experiment niet opnieuw uitgevoerd.}. 
Het toepassen van \emph{GPU} dominerende textuur technieken lijkt voor dit
specifieke geval een goede vertaling van de traditionele \emph{CPU} wereld naar
een implementatie in 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 heeft 8 bits) kunnen worden om
nog meer (combinaties) van oplossingen te coderen.

\subsection{Discussie}
De claim dat de \emph{GPU} ``veel'' sneller is lijkt niet gefundeerd in de
grafieken. Beide 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
 $n$ groter wordt is er grote kans dat de tegels niet meer (goed) passen. Als
 $n$ groter wordt dan in mogelijke invoer ---de maximale grootte van een bord
die in in het geheugen van de de \emph{GPU} past is gelimiteerd aan de hoeveelheid geheugen in de \emph{GPU} en op welke manier dit geheugen ingedeeld is--- is het helemaal niet meer
mogelijk.



\begin{thebibliography}{3}
\bibitem[DM2003]{DM2003}E. J. Cockayne, \emph{Chessboard domination
problems}, \emph{Discrete Math}, 86:13--20, 1990.

\bibitem[CDGPU2006]{CDGPU2006}Nathan Cournia,\emph{Chessboard Domination
on Programmable Graphics Hardware}, \emph{Proceedings of the 44th annual Southeast Regional Conferencee}, pp. 62--67, 2006.

\bibitem[WPCUDA]{WPCUDA}Wikipedia, CUDA, \url{http://en.wikipedia.org/wiki/CUDA}
(as of Sept. 7, 2010, 12:03 GMT).

\end{thebibliography}
\newpage
\end{document}