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}
|
---|
10 | \usepackage[pdftex]{graphicx}
|
---|
11 | \usepackage{url}
|
---|
12 | \usepackage{amssymb,amsmath}
|
---|
13 | \usepackage{lipsum}
|
---|
14 | \usepackage{float}
|
---|
15 |
|
---|
16 | \floatstyle{ruled}
|
---|
17 | \newfloat{algoritm}{thp}{lop}
|
---|
18 | \floatname{algoritm}{Algoritme}
|
---|
19 |
|
---|
20 | \title{\emph{n-Queens} minimale dominerende verzamelingen \\
|
---|
21 | \large{Chessboard Domination on Programmable Graphics Hardware door Nathan Cournia}}
|
---|
22 | \author{Rick van der Zwet\\
|
---|
23 | \texttt{<hvdzwet@liacs.nl>}}
|
---|
24 | \date{\today}
|
---|
25 |
|
---|
26 |
|
---|
27 | \begin{document}
|
---|
28 | \maketitle
|
---|
29 | \begin{abstract}
|
---|
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
|
---|
33 | de mening van de ondergetekende op het geheel geven.
|
---|
34 | \end{abstract}
|
---|
35 |
|
---|
36 | \section{Inleiding}
|
---|
37 | \begin{figure}
|
---|
38 | \begin{center}
|
---|
39 | \includegraphics[width=0.5\textwidth]{pasted1.pdf}
|
---|
40 | \end{center}
|
---|
41 | \caption{Links: koningin kan dit patroon slaan. Rechts: ongeldige \emph{n-Queens} oplossing, omdat de koninginnen rechtsonder elkaar kunnen slaan.}
|
---|
42 | \label{fig:patroon}
|
---|
43 | \end{figure}
|
---|
44 | Vanwege het feit dat \emph{n-Queens} een algemeen geaccepteerde terminologie
|
---|
45 | is voor het plaatsen van $n$ koninginnen op een $n \times n$ schaakbord zodanig dat de
|
---|
46 | koninginnen elkaar niet kunnen slaan, zal dit in het schrijven niet vertaald
|
---|
47 | worden. Verder zal in de tekst op diverse plekken de originele Engelse bewoording
|
---|
48 | staan om zo terugzoeken in en refereren naar het originele paper~\cite{CDGPU2006}
|
---|
49 | makkelijker te maken.
|
---|
50 |
|
---|
51 |
|
---|
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
|
---|
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
|
---|
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}.}:
|
---|
60 | \begin{equation}
|
---|
61 | y(Q_{n})\geq\frac{n-1}{2}, n\geq1
|
---|
62 | \label{eq:ondergrens}
|
---|
63 | \end{equation}
|
---|
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.
|
---|
71 |
|
---|
72 |
|
---|
73 | \section{Grafische Verwerkings Eenheid}
|
---|
74 | \begin{figure}
|
---|
75 | \centering
|
---|
76 | \includegraphics[width=0.4\textwidth]{pasted1.png}
|
---|
77 | \caption{\emph{GPU} werking. De verschillende \emph{GPU} processor-blokken
|
---|
78 | worden \emph{kernels} genoemd. De data wordt getransporteerd door verschillende
|
---|
79 | data-kanalen (\emph{streams}) en heeft de vorm van een \emph{framebuffer}, welke
|
---|
80 | intern als $n \times m$ array gezien kan worden. Een \emph{kernel} kan toegepast
|
---|
81 | worden op een (deel van de) \emph{framebuffer}. Illustratie uit \cite{WPCUDA}.}
|
---|
82 | \label{fig:werking}
|
---|
83 | \end{figure}
|
---|
84 | De Grafische Verwerkings Eenheid (\emph{Graphics Processing Unit}, ook bekend als
|
---|
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
|
---|
87 | met bijvoorbeeld ingewikkelde (lees: tijdrovende) berekeningen voor schaduw,
|
---|
88 | reflectie en intensiteit. Om deze grote hoeveelheid gegevens te verwerken maakt
|
---|
89 | de \emph{GPU} gebruik van een grote hoeveelheid parallelle processoren, welke alle
|
---|
90 | individueel een deel van de berekeningen op zich nemen.
|
---|
91 |
|
---|
92 | Recente (elektronica) ontwikkelingen zoals \emph{CUDA}\footnote{\url{http://en.wikipedia.org/wiki/CUDA}} en een meer generieke implementatie
|
---|
93 | \emph{OpenCL}\footnote{\url{http://en.wikipedia.org/wiki/OpenCL}} hebben ertoe
|
---|
94 | geleid dat op de \emph{GPU} in plaats van enkel beeldverwerkingen te doen nu ook geprogrammeerd kan worden om specifieke
|
---|
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
|
---|
98 | (dus) zeer kleine buffers en instructieset heeft. Verder is het ook cruciaal
|
---|
99 | te weten dat de \emph{GPU} \textit{niet} direct gebruik gebruik kan maken van
|
---|
100 | het hoofd-geheugen van de \emph{CPU}, maar dat de invoer en uitvoer altijd eerst
|
---|
101 | naar/van de \emph{GPU} verplaatst zal moeten worden.
|
---|
102 |
|
---|
103 | \section{Aanpak $n$-Queens probleem op de \emph{GPU}}
|
---|
104 | Het zoeken van geldige minimale dominerende verzamelingen is een stevige klus,
|
---|
105 | waarvoor minimaal (in het optimale geval) $n$ koninginnen nodig zijn die we op een $n \times n$
|
---|
106 | schaakbord kunnen plaatsen. Dat levert $(n * n)! - ((n * n)-n)!$ mogelijkheden op.
|
---|
107 | De \emph{GPU} zal gebruikt worden om oplossingen sneller te controleren en zal
|
---|
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-
|
---|
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
|
---|
117 |
|
---|
118 |
|
---|
119 | \begin{algoritm}
|
---|
120 | \begin{verbatim}
|
---|
121 | 01: klaar=nee
|
---|
122 | 02: doe
|
---|
123 | 03: ..bereken potentieel minimale dominerende verzamelingen
|
---|
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}
|
---|
129 | \caption{evalueren minimale dominerende set}
|
---|
130 | \label{alg:overzicht}
|
---|
131 | \end{algoritm}
|
---|
132 |
|
---|
133 | \subsection{Detectie algoritme}
|
---|
134 | \begin{figure}[h]
|
---|
135 | \centering
|
---|
136 | \includegraphics[width=0.4\textwidth]{pasted4.pdf}
|
---|
137 | \caption{Stempels van verschillende schaakstukken, de verschillende groottes zijn noodzakelijk om aan te geven hoe het stempel vergroot of verkleind moet worden.}
|
---|
138 | \label{fig:stempels}
|
---|
139 | \end{figure}
|
---|
140 | Om snelle detectie mogelijk te maken, wordt er gebruikt gemaakt van een
|
---|
141 | eigenschap waar een \emph{GPU} in uitblinkt: het ``\emph{stempelen}'' van objecten in
|
---|
142 | een raster (welke in traditionele beeldbewerking gebruikt wordt om texturen te
|
---|
143 | maken). Elk schaakstuk heeft zijn eigen stempel-patroon zoals te zien in
|
---|
144 | figuur~\ref{fig:stempels}. Hierbij moet opgemerkt worden dat de stempels
|
---|
145 | allemaal op hun eigen manier schalen.
|
---|
146 |
|
---|
147 | \begin{figure}
|
---|
148 | \begin{center}
|
---|
149 | \includegraphics[width=0.4\textwidth]{pasted5.pdf}
|
---|
150 | \end{center}
|
---|
151 | \caption{Door slim te coderen kunnen meerdere potenti"{e}le oplossingen tegelijk
|
---|
152 | bekeken worden. Hier wordt gebruik gemaakt van (a) het feit dat de ruimte groter
|
---|
153 | is dan het ``schaakbord'' dat bekeken wordt en (b) een pixel gecodeerd is uit
|
---|
154 | vier onafhankelijke kleuren.}
|
---|
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
|
---|
159 | geaccepteerde invoer. Door slim te combineren ---zie Figuur~\ref{fig:raster} op pagina~\pageref{fig:raster}---
|
---|
160 | kan het aantal potenti"{e}le oplossingen dat getest kan worden gemaximaliseerd
|
---|
161 | worden.
|
---|
162 |
|
---|
163 | De individuele \emph{kernels} volgen Algoritme~\ref{alg:kernel}. De test of
|
---|
164 | alle punten gemarkeerd zijn lijkt op het eerste gezicht een lus/loop die test over
|
---|
165 | alle beeldpunten, echter de \emph{GPU} heeft specifieke instructies om dit
|
---|
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
|
---|
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}
|
---|
174 | 01: voor alle stempels in stempel locatie
|
---|
175 | 02: ..plaats stempel
|
---|
176 | 03: als (alle punten gemarkeerd) dan
|
---|
177 | 04: ..oplossing=ja
|
---|
178 | \end{verbatim}
|
---|
179 | \caption{evalueren minimale dominerende set door individuele kernel}
|
---|
180 | \label{alg:kernel}
|
---|
181 | \end{algoritm}
|
---|
182 |
|
---|
183 | \section{Conclusie}
|
---|
184 | \begin{figure}
|
---|
185 | \centering
|
---|
186 | \includegraphics[width=0.4\textwidth]{pasted6.pdf}
|
---|
187 | \caption{
|
---|
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}.}
|
---|
189 | \label{fig:uitvoertijd}
|
---|
190 | \end{figure}
|
---|
191 | Door het toepassen van de \emph{GPU} op het \emph{n-Queens} probleem kunnen
|
---|
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
|
---|
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.
|
---|
197 | \subsection{Verder werk}
|
---|
198 | Er zal gekeken worden of de generatie van nieuwe oplossingen ook op de
|
---|
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.
|
---|
205 |
|
---|
206 | \subsection{Discussie}
|
---|
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
|
---|
209 | dit plots veel beter zou worden bij grotere $n$ waarden.
|
---|
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.
|
---|
215 |
|
---|
216 |
|
---|
217 |
|
---|
218 | \begin{thebibliography}{3}
|
---|
219 | \bibitem[DM2003]{DM2003}E. J. Cockayne, \emph{Chessboard domination
|
---|
220 | problems}, \emph{Discrete Math}, 86:13--20, 1990.
|
---|
221 |
|
---|
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.
|
---|
224 |
|
---|
225 | \bibitem[WPCUDA]{WPCUDA}Wikipedia, CUDA, \url{http://en.wikipedia.org/wiki/CUDA}
|
---|
226 | (as of Sept. 7, 2010, 12:03 GMT).
|
---|
227 |
|
---|
228 | \end{thebibliography}
|
---|
229 | \newpage
|
---|
230 | \end{document}
|
---|