Changeset 179


Ignore:
Timestamp:
Sep 8, 2010, 5:46:49 PM (14 years ago)
Author:
Rick van der Zwet
Message:

Corrected versions (lots of typo's and sentences not clear).

Thanks to Walter Kosters for the corrections!.

Location:
liacs/SCA2010/nQueens
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • liacs/SCA2010/nQueens/latex.mk

    r142 r179  
    6161.tex.pdf:
    6262        pdflatex -halt-on-error $?
     63        pdflatex -halt-on-error $?
    6364
    6465.tex.dvi:

  • liacs/SCA2010/nQueens/report.tex

    r178 r179  
    1818\floatname{algoritm}{Algoritme}
    1919
    20 \title{\emph{n-Queens} minimale dominantie verzamelingen \\
     20\title{\emph{n-Queens} minimale dominerende verzamelingen \\
    2121\large{Chessboard Domination on Programmable Graphics Hardware door Nathan Cournia}}
    2222\author{Rick van der Zwet\\
    … …  
    4343\end{figure}
    4444Vanwege 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 de
     45is voor het plaatsen van $n$ koninginnen op een $n \times n$ schaakbord zodanig dat de
    4646koninginnen elkaar niet kunnen slaan, zal dit in het schrijven niet vertaald
    4747worden. Verder zal in de tekst op diverse plekken de originele Engelse bewoording
    … …  
    5050
    5151
    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}
     53Een dominerende set is een verzameling koninginnen, die tesamen alle velden
     54bereiken. Een minimale dominerende verzameling ({\emph{Minimum domination
     55set}}) is een opstelling waarbij met zo weinig mogelijk koninginnen elk vakje
    5556van het schaakbord a) door ten minste 1 koningin direct bereikt kan worden of b) bezet is
    5657door 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 ook
    58 bepaald worden door middel van Formule~\ref{eq:ondergrens}: 
     58Figuur~\ref{fig:patroon}) kan het minimale aantal koninginnen dat nodig is
     59bepaald worden door middel van Formule~\ref{eq:ondergrens}\footnote{Bewezen in \cite{DM2003}.}: 
    5960\begin{equation}
    6061y(Q_{n})\geq\frac{n-1}{2}, n\geq1
    6162\label{eq:ondergrens}
    6263\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.
     64Hierbij is $n$ de hoogte van het bord. De knopen van $Q_{n}$
     65zijn genomen van een $n \times n$ bord met $n^{2}$ knopen. Als knoop $a$
     66door middel van het \emph{karakteristiek patroon} van een koningin vanuit $b$
     67bereikt kan worden, wordt er een tak tussen deze knopen gevormd. Dit geheel (de
     68knopen en takken) is $Q_{n}$. De $y(Q_{n})$ is dan het minimale aantal
     69koninginnen dat men kan plaatsen om zo een minimale dominerende verzameling
     70te bereiken.
    7271
    7372
    … …  
    7978worden \emph{kernels} genoemd. De data wordt getransporteerd door verschillende
    8079data-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 toegepast
     80intern als $n \times m$ array gezien kan worden. Een \emph{kernel} kan toegepast
    8281worden op een (deel van de) \emph{framebuffer}. Illustratie uit \cite{WPCUDA}.}
    8382  \label{fig:werking}
    … …  
    103102
    104103\section{Aanpak $n$-Queens probleem op de \emph{GPU}}
    105 Het zoeken van geldige minimale dominantie verzamelingen is een stevige klus,
     104Het zoeken van geldige minimale dominerende verzamelingen is een stevige klus,
    106105waarvoor minimaal (in het optimale geval) $n$ koninginnen nodig zijn die we op een $n \times n$
    107106schaakbord kunnen plaatsen. Dat levert $(n * n)! - ((n * n)-n)!$ mogelijkheden op.
    … …  
    112111Algoritme~\ref{alg:overzicht}. De genereerde potenti"{e}le oplossingen die aan de
    113112\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}.}
     113en ondergrenzen \footnote{Zie voor meer bekende boven- en ondergrenzen onder
     114andere de papers genoemd in \cite{CDGPU2006}[sectie 2, pagina 62].} zoals
     115Formule~\ref{eq:ondergrens}.
     116\newpage
    116117
    117118
    … …  
    12012101: klaar=nee
    12112202: doe
    122 03: ..bereken potentieel minimale dominantie verzamelingen
     12303: ..bereken potentieel minimale dominerende verzamelingen
    12312404: ..plaats in framebuffer
    12412505: ..als (alle pixels zijn gemarkeerd) dan
    … …  
    12612708: totdat (klaar=ja)
    127128\end{verbatim}
    128 \caption{evalueren minimale dominantie set}
     129\caption{evalueren minimale dominerende set}
    129130\label{alg:overzicht}
    130131\end{algoritm}
    131132
    132133\subsection{Detectie algoritme}
    133 \begin{figure}
     134\begin{figure}[h]
    134135  \centering
    135136  \includegraphics[width=0.4\textwidth]{pasted4.pdf}
    … …  
    17617704: ..oplossing=ja
    177178\end{verbatim}
    178 \caption{evalueren minimale dominantie set door individuele kernel}
     179\caption{evalueren minimale dominerende set door individuele kernel}
    179180\label{alg:kernel}
    180181\end{algoritm}
    … …  
    185186  \includegraphics[width=0.4\textwidth]{pasted6.pdf}
    186187  \caption{
    187   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}.}
     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}.}
    188189  \label{fig:uitvoertijd}
    189190\end{figure}
    190191Door 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} dominantie textuur technieken lijkt voor dit
     192winsten geboekt worden zoals te zien is in Figuur~\ref{fig:uitvoertijd}\footnote{Gegevens direct uit \cite{CDGPU2006} overgenomen, experiment niet opnieuw uitgevoerd.}.
     193Het toepassen van \emph{GPU} dominerende textuur technieken lijkt voor dit
    193194specifieke geval een goede vertaling van de traditionele \emph{CPU} wereld naar
    194195een implementatie in de  \emph{GPU} wereld. De stempels bieden tevens meer
    … …  
    216217
    217218\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
     220problems}, \emph{Discrete Math}, 86:13--20, 1990.
     221
     222\bibitem[CDGPU2006]{CDGPU2006}Nathan Cournia,\emph{Chessboard Domination
     223on Programmable Graphics Hardware}, \emph{Proceedings of the 44th annual Southeast Regional Conferencee}, pp. 62--67, 2006.
    224224
    225225\bibitem[WPCUDA]{WPCUDA}Wikipedia, CUDA, \url{http://en.wikipedia.org/wiki/CUDA}
Note: See TracChangeset for help on using the changeset viewer.