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