[2] | 1 | %
|
---|
| 2 | % $Id: report.tex 571 2008-04-20 17:31:04Z rick $
|
---|
| 3 | %
|
---|
| 4 |
|
---|
| 5 | \documentclass[12pt,a4paper]{article}
|
---|
| 6 |
|
---|
| 7 | \frenchspacing
|
---|
| 8 | \usepackage[english,dutch]{babel}
|
---|
| 9 | \selectlanguage{dutch}
|
---|
[142] | 10 | \usepackage[pdftex]{graphicx}
|
---|
[2] | 11 | \usepackage{url}
|
---|
| 12 | \usepackage{amssymb,amsmath}
|
---|
[142] | 13 | \usepackage{lipsum}
|
---|
| 14 | \usepackage{float}
|
---|
[2] | 15 |
|
---|
[142] | 16 | \floatstyle{ruled}
|
---|
| 17 | \newfloat{algoritm}{thp}{lop}
|
---|
[143] | 18 | \floatname{algoritm}{Algoritme}
|
---|
[142] | 19 |
|
---|
[144] | 20 | \title{\emph{n-Queens} minimale dominantie verzamelingen \\
|
---|
[178] | 21 | \large{Chessboard Domination on Programmable Graphics Hardware door Nathan Cournia}}
|
---|
[2] | 22 | \author{Rick van der Zwet\\
|
---|
[142] | 23 | \texttt{<hvdzwet@liacs.nl>}}
|
---|
[2] | 24 | \date{\today}
|
---|
| 25 |
|
---|
[142] | 26 |
|
---|
[2] | 27 | \begin{document}
|
---|
| 28 | \maketitle
|
---|
[142] | 29 | \begin{abstract}
|
---|
[178] | 30 | Dit schrijven zal het paper van Nathan Cournia \emph{Chessboard Domination on
|
---|
| 31 | Programmable Graphics Hardware}~\cite{CDGPU2006} ---en in het bijzonder de
|
---|
| 32 | gepresenteerde $n$-Queens oplossing--- vrij samenvatten in het Nederlands en zal
|
---|
[142] | 33 | de mening van de ondergetekende op het geheel geven.
|
---|
| 34 | \end{abstract}
|
---|
[2] | 35 |
|
---|
| 36 | \section{Inleiding}
|
---|
[142] | 37 | \begin{figure}
|
---|
| 38 | \begin{center}
|
---|
| 39 | \includegraphics[width=0.5\textwidth]{pasted1.pdf}
|
---|
| 40 | \end{center}
|
---|
[178] | 41 | \caption{Links: koningin kan dit patroon slaan. Rechts: ongeldige \emph{n-Queens} oplossing, omdat de koninginnen rechtsonder elkaar kunnen slaan.}
|
---|
[142] | 42 | \label{fig:patroon}
|
---|
| 43 | \end{figure}
|
---|
[168] | 44 | Vanwege het feit dat \emph{n-Queens} een algemeen geaccepteerde terminologie
|
---|
[178] | 45 | is voor het plaatsen van $n$ koninginnen op een $n*n$ schaakbord zodanig dat de
|
---|
| 46 | koninginnen elkaar niet kunnen slaan, zal dit in het schrijven niet vertaald
|
---|
[144] | 47 | worden. Verder zal in de tekst op diverse plekken de originele Engelse bewoording
|
---|
[178] | 48 | staan om zo terugzoeken in en refereren naar het originele paper~\cite{CDGPU2006}
|
---|
[142] | 49 | makkelijker te maken.
|
---|
| 50 |
|
---|
| 51 |
|
---|
[144] | 52 | \section{Minimale dominantie verzameling}
|
---|
| 53 | De minimale dominantie verzameling ({\emph{Minimum domination set}}) is
|
---|
[168] | 54 | een opstelling waarbij met zo weinig mogelijk koninginnen elk vakje
|
---|
[178] | 55 | van het schaakbord a) door ten minste 1 koningin direct bereikt kan worden of b) bezet is
|
---|
| 56 | door een koningin. Omdat een koningin een \emph{karakteristiek patroon} kan slaan (zie
|
---|
[143] | 57 | Figuur~\ref{fig:patroon}) kan het minimale aantal koninginnen wat nodig is ook
|
---|
[178] | 58 | bepaald worden door middel van Formule~\ref{eq:ondergrens}:
|
---|
[142] | 59 | \begin{equation}
|
---|
| 60 | y(Q_{n})\geq\frac{n-1}{2}, n\geq1
|
---|
| 61 | \label{eq:ondergrens}
|
---|
| 62 | \end{equation}
|
---|
[178] | 63 | Waarbij in Formule~\ref{eq:ondergrens} $n$ het de grootte van het bord is ($n
|
---|
| 64 | \times n$). De knopen van $Q_{n}$ zijn genomen van een $n \times n$ bord met
|
---|
| 65 | $n^{2}$ als de knopen. Als knoop $a$ door middel van het \emph{karakteristiek
|
---|
| 66 | patroon} van een koningin vanuit $b$ bereikt kan worden, wordt er een tak
|
---|
| 67 | tussen deze knopen gevormd. Dit geheel (de knopen en takken) is $Q_{n}$. $y(G)$
|
---|
| 68 | is de minimum of a domination set of $G$. $y(Q_{n})$ is dan het minimalel
|
---|
| 69 | aantal koninginnen die men kan plaatsen en zodaning de minimale dominantie
|
---|
| 70 | verzameling te bereiken. Als het een ``gewone'' dominantie verzameling is dan
|
---|
| 71 | hoeft het aantal koninginnen niet perse minimaal zijn.
|
---|
[142] | 72 |
|
---|
| 73 |
|
---|
[178] | 74 | \section{Grafische Verwerkings Eenheid}
|
---|
[143] | 75 | \begin{figure}
|
---|
| 76 | \centering
|
---|
| 77 | \includegraphics[width=0.4\textwidth]{pasted1.png}
|
---|
[144] | 78 | \caption{\emph{GPU} werking. De verschillende \emph{GPU} processor-blokken
|
---|
[143] | 79 | worden \emph{kernels} genoemd. De data wordt getransporteerd door verschillende
|
---|
[144] | 80 | data-kanalen (\emph{streams}) en heeft de vorm van een \emph{framebuffer}, welke
|
---|
[143] | 81 | intern als $n * m$ array gezien kan worden. Een \emph{kernel} kan toegepast
|
---|
[178] | 82 | worden op een (deel van de) \emph{framebuffer}. Illustratie uit \cite{WPCUDA}.}
|
---|
[143] | 83 | \label{fig:werking}
|
---|
| 84 | \end{figure}
|
---|
[178] | 85 | De Grafische Verwerkings Eenheid (\emph{Graphics Processing Unit}, ook bekend als
|
---|
[142] | 86 | \emph{GPU}) heeft speciale electronica om ervoor te zorgen dat deze snel de
|
---|
| 87 | \emph{RGB} waardes van alle beeldpunten kan berekenen in complexe beeldsystemen
|
---|
[144] | 88 | met bijvoorbeeld ingewikkelde (lees: tijdrovende) berekeningen voor schaduw,
|
---|
| 89 | reflectie en intensiteit. Om deze grote hoeveelheid gegevens te verwerken maakt
|
---|
[168] | 90 | de \emph{GPU} gebruik van een grote hoeveelheid parallelle processoren, welke alle
|
---|
[142] | 91 | individueel een deel van de berekeningen op zich nemen.
|
---|
| 92 |
|
---|
[168] | 93 | Recente (elektronica) ontwikkelingen zoals \emph{CUDA}\footnote{\url{http://en.wikipedia.org/wiki/CUDA}} en een meer generieke implementatie
|
---|
[142] | 94 | \emph{OpenCL}\footnote{\url{http://en.wikipedia.org/wiki/OpenCL}} hebben ertoe
|
---|
[168] | 95 | geleid dat op de \emph{GPU} in plaats van enkel beeldverwerkingen te doen nu ook geprogrammeerd kan worden om specifieke
|
---|
[142] | 96 | berekeningen uit te voeren. Figuur~\ref{fig:werking} laat de verschillende
|
---|
| 97 | stappen zien die uitgevoerd moeten worden om de \emph{GPU} aan te sturen. Het
|
---|
| 98 | is belangrijk om te beseffen dat de \emph{GPU} een heel simpele processor is en
|
---|
[178] | 99 | (dus) zeer kleine buffers en instructieset heeft. Verder is het ook cruciaal
|
---|
[142] | 100 | te weten dat de \emph{GPU} \textit{niet} direct gebruik gebruik kan maken van
|
---|
[178] | 101 | het hoofd-geheugen van de \emph{CPU}, maar dat de invoer en uitvoer altijd eerst
|
---|
[142] | 102 | naar/van de \emph{GPU} verplaatst zal moeten worden.
|
---|
| 103 |
|
---|
[178] | 104 | \section{Aanpak $n$-Queens probleem op de \emph{GPU}}
|
---|
[144] | 105 | Het zoeken van geldige minimale dominantie verzamelingen is een stevige klus,
|
---|
[178] | 106 | waarvoor minimaal (in het optimale geval) $n$ koninginnen nodig zijn die we op een $n \times n$
|
---|
[142] | 107 | schaakbord kunnen plaatsen. Dat levert $(n * n)! - ((n * n)-n)!$ mogelijkheden op.
|
---|
[143] | 108 | De \emph{GPU} zal gebruikt worden om oplossingen sneller te controleren en zal
|
---|
[178] | 109 | niet gebruikt worden om effici"{e}nte oplossingen te vinden. De kracht zit hem in
|
---|
| 110 | het feit dat meer oplossingen getest kunnen worden en er dus potentieel betere
|
---|
| 111 | oplossingen tussen kunnen zitten, wat ook te zien is in
|
---|
| 112 | Algoritme~\ref{alg:overzicht}. De genereerde potenti"{e}le oplossingen die aan de
|
---|
| 113 | \emph{GPU} ter controle aangeboden worden respecteren eventuele bekende boven-
|
---|
| 114 | en ondergrenzen zoals Formule~\ref{eq:ondergrens}. \footnote{Zie voor meer
|
---|
| 115 | bekende boven- en ondergrenzen onder andere de papers genoemd in \cite[CDGPU2006]{sectie 2, pagina 62}.}
|
---|
[142] | 116 |
|
---|
[178] | 117 |
|
---|
[142] | 118 | \begin{algoritm}
|
---|
| 119 | \begin{verbatim}
|
---|
| 120 | 01: klaar=nee
|
---|
| 121 | 02: doe
|
---|
[144] | 122 | 03: ..bereken potentieel minimale dominantie verzamelingen
|
---|
[142] | 123 | 04: ..plaats in framebuffer
|
---|
| 124 | 05: ..als (alle pixels zijn gemarkeerd) dan
|
---|
| 125 | 06: ....klaar=ja
|
---|
| 126 | 08: totdat (klaar=ja)
|
---|
| 127 | \end{verbatim}
|
---|
[144] | 128 | \caption{evalueren minimale dominantie set}
|
---|
[143] | 129 | \label{alg:overzicht}
|
---|
[142] | 130 | \end{algoritm}
|
---|
| 131 |
|
---|
[143] | 132 | \subsection{Detectie algoritme}
|
---|
| 133 | \begin{figure}
|
---|
| 134 | \centering
|
---|
| 135 | \includegraphics[width=0.4\textwidth]{pasted4.pdf}
|
---|
[178] | 136 | \caption{Stempels van verschillende schaakstukken, de verschillende groottes zijn noodzakelijk om aan te geven hoe het stempel vergroot of verkleind moet worden.}
|
---|
[143] | 137 | \label{fig:stempels}
|
---|
| 138 | \end{figure}
|
---|
| 139 | Om snelle detectie mogelijk te maken, wordt er gebruikt gemaakt van een
|
---|
[178] | 140 | eigenschap waar een \emph{GPU} in uitblinkt: het ``\emph{stempelen}'' van objecten in
|
---|
[143] | 141 | een raster (welke in traditionele beeldbewerking gebruikt wordt om texturen te
|
---|
[144] | 142 | maken). Elk schaakstuk heeft zijn eigen stempel-patroon zoals te zien in
|
---|
[143] | 143 | figuur~\ref{fig:stempels}. Hierbij moet opgemerkt worden dat de stempels
|
---|
| 144 | allemaal op hun eigen manier schalen.
|
---|
[142] | 145 |
|
---|
[143] | 146 | \begin{figure}
|
---|
[142] | 147 | \begin{center}
|
---|
| 148 | \includegraphics[width=0.4\textwidth]{pasted5.pdf}
|
---|
| 149 | \end{center}
|
---|
[144] | 150 | \caption{Door slim te coderen kunnen meerdere potenti"{e}le oplossingen tegelijk
|
---|
[143] | 151 | bekeken worden. Hier wordt gebruik gemaakt van (a) het feit dat de ruimte groter
|
---|
[178] | 152 | is dan het ``schaakbord'' dat bekeken wordt en (b) een pixel gecodeerd is uit
|
---|
| 153 | vier onafhankelijke kleuren.}
|
---|
[143] | 154 | \label{fig:raster}
|
---|
| 155 | \end{figure}
|
---|
| 156 | Er zijn nog twee eigenschappen van de \emph{GPU} waar dankbaar gebruik van
|
---|
| 157 | gemaakt wordt, namelijk kleur en het verschil in grootte van het bord en de
|
---|
[178] | 158 | geaccepteerde invoer. Door slim te combineren ---zie Figuur~\ref{fig:raster} op pagina~\pageref{fig:raster}---
|
---|
[168] | 159 | kan het aantal potenti"{e}le oplossingen dat getest kan worden gemaximaliseerd
|
---|
[143] | 160 | worden.
|
---|
[142] | 161 |
|
---|
[178] | 162 | De individuele \emph{kernels} volgen Algoritme~\ref{alg:kernel}. De test of
|
---|
[168] | 163 | alle punten gemarkeerd zijn lijkt op het eerste gezicht een lus/loop die test over
|
---|
[143] | 164 | alle beeldpunten, echter de \emph{GPU} heeft specifieke instructies om dit
|
---|
[168] | 165 | effici"{e}nter uit te voeren.
|
---|
| 166 | Voor het plaatsen van de stempels is er een een grafische operatie die
|
---|
| 167 | equivalent is aan een \texttt{OF} operatie. Als een \texttt{INVERSE} operatie gebruikt zou
|
---|
[143] | 168 | worden om de stempel te plaatsen zou een tweede overlappende stempel onterecht
|
---|
| 169 | als niet geraakt gemarkeerd worden.
|
---|
| 170 |
|
---|
| 171 | \begin{algoritm}
|
---|
| 172 | \begin{verbatim}
|
---|
[178] | 173 | 01: voor alle stempels in stempel locatie
|
---|
[143] | 174 | 02: ..plaats stempel
|
---|
| 175 | 03: als (alle punten gemarkeerd) dan
|
---|
| 176 | 04: ..oplossing=ja
|
---|
| 177 | \end{verbatim}
|
---|
[144] | 178 | \caption{evalueren minimale dominantie set door individuele kernel}
|
---|
[143] | 179 | \label{alg:kernel}
|
---|
| 180 | \end{algoritm}
|
---|
| 181 |
|
---|
[2] | 182 | \section{Conclusie}
|
---|
[143] | 183 | \begin{figure}
|
---|
| 184 | \centering
|
---|
| 185 | \includegraphics[width=0.4\textwidth]{pasted6.pdf}
|
---|
| 186 | \caption{
|
---|
[178] | 187 | 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}.}
|
---|
[143] | 188 | \label{fig:uitvoertijd}
|
---|
| 189 | \end{figure}
|
---|
[178] | 190 | Door het toepassen van de \emph{GPU} op het \emph{n-Queens} probleem kunnen
|
---|
| 191 | winsten geboekt worden zoals te zien is in Figuur~\ref{fig:uitvoertijd}\footnote{Gegevens direct uit \cite{CDGPU2006} overgenomen, experiment niet opnieuw uitgevoerd}.
|
---|
[168] | 192 | Het toepassen van \emph{GPU} dominantie textuur technieken lijkt voor dit
|
---|
[178] | 193 | specifieke geval een goede vertaling van de traditionele \emph{CPU} wereld naar
|
---|
| 194 | een implementatie in de \emph{GPU} wereld. De stempels bieden tevens meer
|
---|
| 195 | vrijheden om alternatieve ``schaakstukken'' te onderzoeken.
|
---|
[143] | 196 | \subsection{Verder werk}
|
---|
| 197 | Er zal gekeken worden of de generatie van nieuwe oplossingen ook op de
|
---|
[178] | 198 | \emph{GPU} gedaan kan worden om zo het probleem van de langzame
|
---|
| 199 | contextwisselingen op te lossen. Verder zal er gekeken worden of de codering
|
---|
| 200 | van de borden op nog een slimmere
|
---|
| 201 | manier aangepakt kan worden: in plaats van de kleur in 4 basis-kleuren uit te
|
---|
| 202 | splitsen zouden ook de volledige 32 bits (elke kleur heeft 8 bits) kunnen worden om
|
---|
| 203 | nog meer (combinaties) van oplossingen te coderen.
|
---|
[142] | 204 |
|
---|
[143] | 205 | \subsection{Discussie}
|
---|
[178] | 206 | De claim dat de \emph{GPU} ``veel'' sneller is lijkt niet gefundeerd in de
|
---|
| 207 | grafieken. Beide lijken erg dicht bij elkaar te blijven en ik zie niet waarom
|
---|
[143] | 208 | dit plots veel beter zou worden bij grotere $n$ waarden.
|
---|
[178] | 209 | De ``tegel-methode'' van Figuur~\ref{fig:raster} lijkt in theorie leuk, maar als
|
---|
| 210 | $n$ groter wordt is er grote kans dat de tegels niet meer (goed) passen. Als
|
---|
| 211 | $n$ groter wordt dan in mogelijke invoer ---de maximale grootte van een bord
|
---|
| 212 | 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
|
---|
| 213 | mogelijk.
|
---|
[142] | 214 |
|
---|
| 215 |
|
---|
[143] | 216 |
|
---|
[178] | 217 | \begin{thebibliography}{3}
|
---|
[142] | 218 | \bibitem[DM2003]{DM2003}E. J. Cockayne, emph{Chessboard domination
|
---|
| 219 | problems}, \emph{Discrete Math}, 86:1320, 1990.
|
---|
| 220 |
|
---|
| 221 | \bibitem[CDGPU2006]{CDGPU2006}Nathan Cournik,\emph{Chessboard Domination
|
---|
| 222 | on Programmable Graphics Hardware}, \emph{ACM SE'06 March
|
---|
| 223 | 10-Â12, 2006}. Melbourne, Florida, USA
|
---|
[178] | 224 |
|
---|
| 225 | \bibitem[WPCUDA]{WPCUDA}Wikipedia, CUDA, \url{http://en.wikipedia.org/wiki/CUDA}
|
---|
| 226 | (as of Sept. 7, 2010, 12:03 GMT).
|
---|
| 227 |
|
---|
[2] | 228 | \end{thebibliography}
|
---|
| 229 | \newpage
|
---|
| 230 | \end{document}
|
---|