% % $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 Cournia}} \author{Rick van der Zwet\\ \texttt{}} \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*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 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 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 wat nodig is ook bepaald worden door middel van Formule~\ref{eq:ondergrens}: \begin{equation} y(Q_{n})\geq\frac{n-1}{2}, n\geq1 \label{eq:ondergrens} \end{equation} Waarbij in Formule~\ref{eq:ondergrens} $n$ het de grootte van het bord is ($n \times n$). De knopen van $Q_{n}$ zijn genomen van een $n \times n$ bord met $n^{2}$ als de 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}$. $y(G)$ is de minimum of a domination set of $G$. $y(Q_{n})$ is dan het minimalel aantal koninginnen die men kan plaatsen en zodaning de minimale dominantie verzameling te bereiken. Als het een ``gewone'' dominantie verzameling is dan hoeft het aantal koninginnen niet perse minimaal zijn. \section{Grafische Verwerkings 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}. Illustratie uit \cite{WPCUDA}.} \label{fig:werking} \end{figure} De Grafische Verwerkings 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 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 dominantie 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 zoals Formule~\ref{eq:ondergrens}. \footnote{Zie voor meer bekende boven- en ondergrenzen onder andere de papers genoemd in \cite[CDGPU2006]{sectie 2, pagina 62}.} \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 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 dominantie 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 dominantie 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} dominantie 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 contextwisselingen 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 iin 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: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 \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}