Changeset 179 for liacs/SCA2010/nQueens
- Timestamp:
- Sep 8, 2010, 5:46:49 PM (14 years ago)
- Location:
- liacs/SCA2010/nQueens
- Files:
-
- 3 edited
-
latex.mk (modified) (1 diff)
-
report.pdf (modified) ( previous)
-
report.tex (modified) (11 diffs)
Legend:
- Unmodified
- Added
- Removed
-
liacs/SCA2010/nQueens/latex.mk
r142 r179 61 61 .tex.pdf: 62 62 pdflatex -halt-on-error $? 63 pdflatex -halt-on-error $? 63 64 64 65 .tex.dvi: -
liacs/SCA2010/nQueens/report.tex
r178 r179 18 18 \floatname{algoritm}{Algoritme} 19 19 20 \title{\emph{n-Queens} minimale domin antie verzamelingen \\20 \title{\emph{n-Queens} minimale dominerende verzamelingen \\ 21 21 \large{Chessboard Domination on Programmable Graphics Hardware door Nathan Cournia}} 22 22 \author{Rick van der Zwet\\ … … 43 43 \end{figure} 44 44 Vanwege het feit dat \emph{n-Queens} een algemeen geaccepteerde terminologie 45 is voor het plaatsen van $n$ koninginnen op een $n *n$ schaakbord zodanig dat de45 is voor het plaatsen van $n$ koninginnen op een $n \times n$ schaakbord zodanig dat de 46 46 koninginnen elkaar niet kunnen slaan, zal dit in het schrijven niet vertaald 47 47 worden. Verder zal in de tekst op diverse plekken de originele Engelse bewoording … … 50 50 51 51 52 \section{Minimale dominantie verzameling} 53 De minimale dominantie verzameling ({\emph{Minimum domination set}}) is 54 een opstelling waarbij met zo weinig mogelijk koninginnen elk vakje 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 55 56 van het schaakbord a) door ten minste 1 koningin direct bereikt kan worden of b) bezet is 56 57 door een koningin. Omdat een koningin een \emph{karakteristiek patroon} kan slaan (zie 57 Figuur~\ref{fig:patroon}) kan het minimale aantal koninginnen wat nodig is ook58 bepaald worden door middel van Formule~\ref{eq:ondergrens} :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}.}: 59 60 \begin{equation} 60 61 y(Q_{n})\geq\frac{n-1}{2}, n\geq1 61 62 \label{eq:ondergrens} 62 63 \end{equation} 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. 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. 72 71 73 72 … … 79 78 worden \emph{kernels} genoemd. De data wordt getransporteerd door verschillende 80 79 data-kanalen (\emph{streams}) en heeft de vorm van een \emph{framebuffer}, welke 81 intern als $n *m$ array gezien kan worden. Een \emph{kernel} kan toegepast80 intern als $n \times m$ array gezien kan worden. Een \emph{kernel} kan toegepast 82 81 worden op een (deel van de) \emph{framebuffer}. Illustratie uit \cite{WPCUDA}.} 83 82 \label{fig:werking} … … 103 102 104 103 \section{Aanpak $n$-Queens probleem op de \emph{GPU}} 105 Het zoeken van geldige minimale domin antie verzamelingen is een stevige klus,104 Het zoeken van geldige minimale dominerende verzamelingen is een stevige klus, 106 105 waarvoor minimaal (in het optimale geval) $n$ koninginnen nodig zijn die we op een $n \times n$ 107 106 schaakbord kunnen plaatsen. Dat levert $(n * n)! - ((n * n)-n)!$ mogelijkheden op. … … 112 111 Algoritme~\ref{alg:overzicht}. De genereerde potenti"{e}le oplossingen die aan de 113 112 \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}.} 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 116 117 117 118 … … 120 121 01: klaar=nee 121 122 02: doe 122 03: ..bereken potentieel minimale domin antie verzamelingen123 03: ..bereken potentieel minimale dominerende verzamelingen 123 124 04: ..plaats in framebuffer 124 125 05: ..als (alle pixels zijn gemarkeerd) dan … … 126 127 08: totdat (klaar=ja) 127 128 \end{verbatim} 128 \caption{evalueren minimale domin antie set}129 \caption{evalueren minimale dominerende set} 129 130 \label{alg:overzicht} 130 131 \end{algoritm} 131 132 132 133 \subsection{Detectie algoritme} 133 \begin{figure} 134 \begin{figure}[h] 134 135 \centering 135 136 \includegraphics[width=0.4\textwidth]{pasted4.pdf} … … 176 177 04: ..oplossing=ja 177 178 \end{verbatim} 178 \caption{evalueren minimale domin antie set door individuele kernel}179 \caption{evalueren minimale dominerende set door individuele kernel} 179 180 \label{alg:kernel} 180 181 \end{algoritm} … … 185 186 \includegraphics[width=0.4\textwidth]{pasted6.pdf} 186 187 \caption{ 187 Uitvoertijden (logaritmische schaal) van de \emph{CPU} en \emph{GPU} gebaseerde minimale domin antie implementaties welke $y(Q_{n})$ uitrekenen. Hoe groter $n$ wordt des te beter de \emph{GPU} gaat presteren in vergelijking met de \emph{CPU}.}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}.} 188 189 \label{fig:uitvoertijd} 189 190 \end{figure} 190 191 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 }.192 Het toepassen van \emph{GPU} domin antie textuur technieken lijkt voor dit192 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 193 194 specifieke geval een goede vertaling van de traditionele \emph{CPU} wereld naar 194 195 een implementatie in de \emph{GPU} wereld. De stempels bieden tevens meer … … 216 217 217 218 \begin{thebibliography}{3} 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 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 224 225 225 \bibitem[WPCUDA]{WPCUDA}Wikipedia, CUDA, \url{http://en.wikipedia.org/wiki/CUDA}
Note:
See TracChangeset
for help on using the changeset viewer.
