Ignore:
Timestamp:
Aug 3, 2010, 10:58:37 PM (14 years ago)
Author:
Rick van der Zwet
Message:

Whole bunch of typo's corrected

File:
1 edited

Legend:

Unmodified
Added
Removed
  • liacs/SCA2010/nQueens/report.tex

    r144 r168  
    4242  \label{fig:patroon}
    4343\end{figure}
    44 Vanwege het het feit dat \emph{n-Queens} een algemeen geaccepteerde terminologie
    45 is, voor het plaatsen van $n$ koningen op een $n*n$ schaakbord zodanig dat de
     44Vanwege het feit dat \emph{n-Queens} een algemeen geaccepteerde terminologie
     45is voor het plaatsen van $n$ koningen op een $n*n$ schaakbord zodanig dat de
    4646koningen elkaar niet kunnen slaan, zal dit in het schrijven niet vertaald
    4747worden. Verder zal in de tekst op diverse plekken de originele Engelse bewoording
     
    5252\section{Minimale dominantie verzameling}
    5353De minimale dominantie verzameling ({\emph{Minimum domination set}}) is
    54 een opstelling waarbij zo weinig mogelijk koninginnen wordt gebruikt om elk vakje
    55 van het schaakbord door ten minste 1 koningin geslagen kan worden of dat er een
     54een opstelling waarbij met zo weinig mogelijk koninginnen elk vakje
     55van het schaakbord a) door ten minste 1 koningin geslagen kan worden of b) dat er een
    5656koningin op staat. Omdat een koningin een karakteristiek patroon kan staan (zie
    5757Figuur~\ref{fig:patroon}) kan het minimale aantal koninginnen wat nodig is ook
     
    7373data-kanalen (\emph{streams}) en heeft de vorm van een \emph{framebuffer}, welke
    7474intern als $n * m$ array gezien kan worden. Een \emph{kernel} kan toegepast
    75 worden om een (deel van de) \emph{framebuffer}.}
     75worden op een (deel van de) \emph{framebuffer}.}
    7676  \label{fig:werking}
    7777\end{figure}
     
    8181met bijvoorbeeld ingewikkelde (lees: tijdrovende) berekeningen voor schaduw,
    8282reflectie en intensiteit. Om deze grote hoeveelheid gegevens te verwerken maakt
    83 de \emph{GPU} gebruik een grote hoeveelheid parallelle processoren, welke alle
     83de \emph{GPU} gebruik van een grote hoeveelheid parallelle processoren, welke alle
    8484individueel een deel van de berekeningen op zich nemen.
    8585
    86 Recente (elektronica) ontwikkelingen zoals \emph{CUDA}\footnote{\url{http://en.wikipedia.org/wiki/CUDA}} en (meer generieke implementaties)
     86Recente (elektronica) ontwikkelingen zoals \emph{CUDA}\footnote{\url{http://en.wikipedia.org/wiki/CUDA}} en een meer generieke implementatie
    8787\emph{OpenCL}\footnote{\url{http://en.wikipedia.org/wiki/OpenCL}} hebben ertoe
    88 geleid dat de GPU ook door de geprogrammeerd kan worden om specifieke
     88geleid dat op de \emph{GPU} in plaats van enkel beeldverwerkingen te doen nu ook geprogrammeerd kan worden om specifieke
    8989berekeningen uit te voeren. Figuur~\ref{fig:werking} laat de verschillende
    9090stappen zien die uitgevoerd moeten worden om de \emph{GPU} aan te sturen. Het
     
    9595naar/van de \emph{GPU} verplaatst zal moeten worden.
    9696
    97 \section{Aanpak}
     97\section{Aanpak emph{n-Queens} probleem op de \emph{GPU}}
    9898Het zoeken van geldige minimale dominantie verzamelingen is een stevige klus,
    99 welke we (in het optimale geval) $n$ koninginnen hebben die we op een $n * n$
     99waarvoor minimaal (en dus optimale geval) $n$ koninginnen nodig zijn die we op een $n * n$
    100100schaakbord kunnen plaatsen. Dat levert $(n * n)! - ((n * n)-n)!$ mogelijkheden op.
    101101De \emph{GPU} zal gebruikt worden om oplossingen sneller te controleren en zal
     
    146146Er zijn nog twee eigenschappen van de \emph{GPU} waar dankbaar gebruik van
    147147gemaakt wordt, namelijk kleur en het verschil in grootte van het bord en de
    148 geaccepteerde invoer. Door slim te combineren ---zie figuur~\ref{fig:raster}---
    149 kan het aantal potenti"{e}le oplossingen die getest kan worden gemaximaliseerd
     148geaccepteerde invoer. Door slim te combineren ---zie figuur~\ref{fig:raster} op pagina~\pageref{fig:raster}---
     149kan het aantal potenti"{e}le oplossingen dat getest kan worden gemaximaliseerd
    150150worden.
    151151
    152 De individuele \emph{kernels} volgen het algoritme~\ref{alg:kernel}, de test of
    153 alle punten gemarkeerd zijn lijkt om het eerste gezicht een lus en test over
     152De individuele \emph{kernels} volgen het algoritme~\ref{alg:kernel}. De test of
     153alle punten gemarkeerd zijn lijkt op het eerste gezicht een lus/loop die test over
    154154alle beeldpunten, echter de \emph{GPU} heeft specifieke instructies om dit
    155 effici"{e}ntie uit te voeren.
    156 Voor het plaatsen van de stempels moet er gegaan worden voor de grafische
    157 equivalent van een \texttt{OF} operatie. Als een \texttt{INVERSE} operatie gebruikt zou
     155effici"{e}nter uit te voeren.
     156Voor het plaatsen van de stempels is er een een grafische operatie die
     157equivalent is aan een \texttt{OF} operatie. Als een \texttt{INVERSE} operatie gebruikt zou
    158158worden om de stempel te plaatsen zou een tweede overlappende stempel onterecht
    159159als niet geraakt gemarkeerd worden.
     
    175175  \includegraphics[width=0.4\textwidth]{pasted6.pdf}
    176176  \caption{
    177   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}}
     177  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}}
    178178  \label{fig:uitvoertijd}
    179179\end{figure}
    180180Door het toepassen van de \emph{GPU} in het \emph{n-Queens} probleem kunnen
    181181winsten geboekt worden zoals te zien in figuur~\ref{fig:uitvoertijd}\footnote{Gegevens direct uit \cite{CDGPU2006} overgenomen, experiment niet opnieuw uitgevoerd}.
    182 Het toepassen van \emph{GPU} dominantie textuur technieken technieken lijkt voor dit
     182Het toepassen van \emph{GPU} dominantie textuur technieken lijkt voor dit
    183183specifieke geval een goede vertaling van de traditionele \emph{CPU} wereld en
    184184de \emph{GPU} wereld. De stempels bieden tevens meer vrijheden om alternatieve
Note: See TracChangeset for help on using the changeset viewer.