Changeset 168 for liacs/SCA2010/nQueens

Timestamp:

Aug 3, 2010, 10:58:37 PM (14 years ago)

Author:

Rick van der Zwet

Message:

Whole bunch of typo's corrected

Location:

liacs/SCA2010/nQueens

Files:

• report.pdf (added)
• report.tex (modified) (7 diffs)

liacs/SCA2010/nQueens/report.tex

@@ -42 +42 @@
   \label{fig:patroon}
 \end{figure}
-Vanwege het 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
+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
 worden. Verder zal in de tekst op diverse plekken de originele Engelse bewoording
@@ -52 +52 @@
 \section{Minimale dominantie verzameling}
 De minimale dominantie verzameling ({\emph{Minimum domination set}}) is
-een opstelling waarbij zo weinig mogelijk koninginnen wordt gebruikt om elk vakje
-van het schaakbord door ten minste 1 koningin geslagen kan worden of dat er een
+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
 Figuur~\ref{fig:patroon}) kan het minimale aantal koninginnen wat nodig is ook
@@ -73 +73 @@
 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 om een (deel van de) \emph{framebuffer}.} 
+worden op een (deel van de) \emph{framebuffer}.} 
   \label{fig:werking}
 \end{figure}
@@ -81 +81 @@
 met bijvoorbeeld ingewikkelde (lees: tijdrovende) berekeningen voor schaduw,
 reflectie en intensiteit. Om deze grote hoeveelheid gegevens te verwerken maakt
-de \emph{GPU} gebruik een grote hoeveelheid parallelle processoren, welke alle
+de \emph{GPU} gebruik van een grote hoeveelheid parallelle processoren, welke alle
 individueel een deel van de berekeningen op zich nemen.
 
-Recente (elektronica) ontwikkelingen zoals \emph{CUDA}\footnote{\url{http://en.wikipedia.org/wiki/CUDA}} en (meer generieke implementaties)
+Recente (elektronica) ontwikkelingen zoals \emph{CUDA}\footnote{\url{http://en.wikipedia.org/wiki/CUDA}} en een meer generieke implementatie
 \emph{OpenCL}\footnote{\url{http://en.wikipedia.org/wiki/OpenCL}} hebben ertoe
-geleid dat de GPU ook door de geprogrammeerd kan worden om specifieke
+geleid dat op de \emph{GPU} in plaats van enkel beeldverwerkingen te doen nu ook geprogrammeerd kan worden om specifieke
 berekeningen uit te voeren. Figuur~\ref{fig:werking} laat de verschillende
 stappen zien die uitgevoerd moeten worden om de \emph{GPU} aan te sturen. Het
@@ -95 +95 @@
 naar/van de \emph{GPU} verplaatst zal moeten worden.
 
-\section{Aanpak}
+\section{Aanpak emph{n-Queens} probleem op de \emph{GPU}}
 Het zoeken van geldige minimale dominantie verzamelingen is een stevige klus,
-welke we (in het optimale geval) $n$ koninginnen hebben die we op een $n * n$
+waarvoor minimaal (en dus optimale geval) $n$ koninginnen nodig zijn die we op een $n * 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
@@ -146 +146 @@
 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}---
-kan het aantal potenti"{e}le oplossingen die getest kan worden gemaximaliseerd
+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
-alle punten gemarkeerd zijn lijkt om het eerste gezicht een lus en test over
+De individuele \emph{kernels} volgen het 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
-effici"{e}ntie uit te voeren.
-Voor het plaatsen van de stempels moet er gegaan worden voor de grafische
-equivalent van een \texttt{OF} operatie. Als een \texttt{INVERSE} operatie gebruikt zou
+effici"{e}nter uit te voeren.
+Voor het plaatsen van de stempels is er een een grafische operatie die
+equivalent is aan een \texttt{OF} operatie. Als een \texttt{INVERSE} operatie gebruikt zou
 worden om de stempel te plaatsen zou een tweede overlappende stempel onterecht
 als niet geraakt gemarkeerd worden.
@@ -175 +175 @@
   \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, de beter de \emph{GPU} gaan presteren boven de \emph{CPU}} 
+  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}} 
   \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}. 
-Het toepassen van \emph{GPU} dominantie textuur technieken technieken lijkt voor dit
+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