Changeset 178 for liacs/SCA2010/nQueens

Timestamp:

Sep 7, 2010, 12:56:06 PM (14 years ago)

Author:

Rick van der Zwet

Message:

Corrected whole bunch of useful changes

Location:

liacs/SCA2010/nQueens

Files:

• report.pdf (modified) ( previous)
• report.tex (modified) (11 diffs)

liacs/SCA2010/nQueens/report.tex

@@ -19 +19 @@
 
 \title{\emph{n-Queens} minimale dominantie verzamelingen \\
-\large{Chessboard Domination on Programmable Graphics Hardware door Nathan Cournik}}
+\large{Chessboard Domination on Programmable Graphics Hardware door Nathan Cournia}}
 \author{Rick van der Zwet\\
   \texttt{<hvdzwet@liacs.nl>}}
@@ -28 +28 @@
 \maketitle
 \begin{abstract}
-Dit schrijven zal het paper van Nathan Cournik \emph{Chessboard Domination on
-Programmable Graphics Hardware}~\cite{CDGPU2006} ---en in het speciaal de
-gepresenteerde n-Queens oplossing--- vrij samenvatten in het nederlands en zal
+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}
@@ -39 +39 @@
     \includegraphics[width=0.5\textwidth]{pasted1.pdf}
   \end{center}
-  \caption{Links; koningin kan dit patroon slaan. Rechts; ongeldige \emph{n-Queens} oplossing, opdat de koninginnen rechtsonder elkaar kunnen slaan}
+  \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$ koningen op een $n*n$ schaakbord zodanig dat de
-koningen elkaar niet kunnen slaan, zal dit in het schrijven niet vertaald
+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 en refereren in het originele paper~\cite{CDGPU2006}
+staan om zo terugzoeken in en refereren naar het originele paper~\cite{CDGPU2006}
 makkelijker te maken.
 
@@ -53 +53 @@
 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 geslagen kan worden of b) dat er een
-koningin op staat. Omdat een koningin een karakteristiek patroon kan staan (zie
+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 dmv van formule~\ref{eq:ondergrens}.  
+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}
-Als het een 'gewone' dominantie verzameling is dan hoeft het aantal koninginnen
-niet perse minimaal zijn.
-
-
-\section{Grafische Verwerking Eenheid}
+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
@@ -73 +80 @@
 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}.} 
+worden op een (deel van de) \emph{framebuffer}. Illustratie uit \cite{WPCUDA}.}
   \label{fig:werking}
 \end{figure}
-De Grafische Verwerking Eenheid (\emph{Graphics Processing Unit} ook bekend als
+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
@@ -90 +97 @@
 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 instructie set heeft. Verder is het ook cruciaal
+(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}, maak dat de invoer en uitvoer altijd eerst
+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 emph{n-Queens} probleem op de \emph{GPU}}
+\section{Aanpak $n$-Queens probleem op de \emph{GPU}}
 Het zoeken van geldige minimale dominantie verzamelingen is een stevige klus,
-waarvoor minimaal (en dus optimale geval) $n$ koninginnen nodig zijn die we op een $n * n$
+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}ntie oplossingen te vinden. De kracht zit hem in
-het feit dat meer oplossingen getest kunnen worden en dus potentieel betere
-oplossingen tussen kunnen zitten, welke ook te zien in in
-algoritme~\ref{alg:overzicht}. De genereerde potenti"{e}le oplossingen die aan de
-\emph{GPU} ter controle aangeboden worden respecteren de boven- en ondergrens.
+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}
@@ -124 +134 @@
   \centering
   \includegraphics[width=0.4\textwidth]{pasted4.pdf}
-  \caption{Stempels van verschillende schaakstukken, de verschillende groottes zijn noodzakelijk om aan te geven hoe de stempel vergroot of verkleint moet worden}  
+  \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
+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
@@ -140 +150 @@
   \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' welke bekeken wordt en (b) een pixel gecodeerd is uit
-vier onafhankelijke kleuren} 
+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}---
+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 het algoritme~\ref{alg:kernel}. De test of
+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
@@ -161 +171 @@
 \begin{algoritm}
 \begin{verbatim}
-01: voor elke stempels in stempel locatie
+01: voor alle stempels in stempel locatie
 02: ..plaats stempel
 03: als (alle punten gemarkeerd) dan
@@ -175 +185 @@
   \includegraphics[width=0.4\textwidth]{pasted6.pdf}
   \caption{
-  Uitvoer tijden (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} gaan presteren in vergelijking met de \emph{CPU}} 
+  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} in het \emph{n-Queens} probleem kunnen
-winsten geboekt worden zoals te zien in figuur~\ref{fig:uitvoertijd}\footnote{Gegevens direct uit \cite{CDGPU2006} overgenomen, experiment niet opnieuw uitgevoerd}. 
+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 en
-de \emph{GPU} wereld. De stempels bieden tevens meer vrijheden om alternatieve
-'schaakstukken' te onderzoeken.
+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 context
-wisselingen 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 is 8 bit) kunnen worden om
-nog meer(combinaties) van oplossingen te coderen.
+\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 me niet gefundeerd in de
-grafieken. Beiden lijken erg dicht bij elkaar te blijven en ik zie niet waarom
+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
-de $n$ groter wordt is er grote kans dat de tegels niet meer (goed) passen. Als
-de $n$ groter wordt dan in mogelijke invoer is het helemaal niet meer mogelijk.
-
-
-
-\begin{thebibliography}{2}
+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.
@@ -210 +222 @@
 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