Changeset 144 for liacs/SCA2010/nQueens
- Timestamp:
- Jul 1, 2010, 8:23:16 PM (14 years ago)
- File:
-
- 1 edited
-
liacs/SCA2010/nQueens/report.tex (modified) (15 diffs)
Legend:
- Unmodified
- Added
- Removed
-
liacs/SCA2010/nQueens/report.tex
r143 r144 18 18 \floatname{algoritm}{Algoritme} 19 19 20 \title{\emph{n-Queens} minimale domina tie verzamelingen \\20 \title{\emph{n-Queens} minimale dominantie verzamelingen \\ 21 21 \large{Chessboard Domination on Programmable Graphics Hardware door Nathan Cournik}} 22 22 \author{Rick van der Zwet\\ … … 42 42 \label{fig:patroon} 43 43 \end{figure} 44 Vanwege het het feit dat \emph{n-Queens} een algemeen geaccepteerde termi ologie44 Vanwege het het feit dat \emph{n-Queens} een algemeen geaccepteerde terminologie 45 45 is, voor het plaatsen van $n$ koningen op een $n*n$ schaakbord zodanig dat de 46 46 koningen elkaar niet kunnen slaan, zal dit in het schrijven niet vertaald 47 worden. Verder zal in de tekst op diverse plekken de or ginele engelse bewoordinging48 staan om zo terugzoeken en refereren in het or ginele paper~\cite{CDGPU2006}47 worden. Verder zal in de tekst op diverse plekken de originele Engelse bewoording 48 staan om zo terugzoeken en refereren in het originele paper~\cite{CDGPU2006} 49 49 makkelijker te maken. 50 50 51 51 52 \section{Minimale domina tie verzameling}53 De minimale domina tie verzameling ({\emph{Minimum domination set}}) is54 een setup waarbij zo weinig mogelijk koninginnen wordt gembruikt om elk vakje52 \section{Minimale dominantie verzameling} 53 De minimale dominantie verzameling ({\emph{Minimum domination set}}) is 54 een opstelling waarbij zo weinig mogelijk koninginnen wordt gebruikt om elk vakje 55 55 van het schaakbord door ten minste 1 koningin geslagen kan worden of dat er een 56 56 koningin op staat. Omdat een koningin een karakteristiek patroon kan staan (zie … … 61 61 \label{eq:ondergrens} 62 62 \end{equation} 63 Als het een 'gewone' domina tie verzameling is dan hoeft het aantal koninginnen64 niet per -se minimaal zijn.63 Als het een 'gewone' dominantie verzameling is dan hoeft het aantal koninginnen 64 niet perse minimaal zijn. 65 65 66 66 … … 69 69 \centering 70 70 \includegraphics[width=0.4\textwidth]{pasted1.png} 71 \caption{\emph{GPU} werking. De verschillende \emph{GPU} processor blokken71 \caption{\emph{GPU} werking. De verschillende \emph{GPU} processor-blokken 72 72 worden \emph{kernels} genoemd. De data wordt getransporteerd door verschillende 73 data kanalen (\emph{streams}) en heeft de vorm van een \emph{framebuffer}, welke73 data-kanalen (\emph{streams}) en heeft de vorm van een \emph{framebuffer}, welke 74 74 intern als $n * m$ array gezien kan worden. Een \emph{kernel} kan toegepast 75 75 worden om een (deel van de) \emph{framebuffer}.} … … 79 79 \emph{GPU}) heeft speciale electronica om ervoor te zorgen dat deze snel de 80 80 \emph{RGB} waardes van alle beeldpunten kan berekenen in complexe beeldsystemen 81 met bijvoorbeeld ingewikke nde (lees: tijdrovende) berekeningen voor schaduw,82 refle xtie en intensiteit. Om deze grote hoeveelheid gegevens te verwerken maakt83 de \emph{GPU} gebruik een grote hoeveelheid par ralelle processoren, welke alle81 met bijvoorbeeld ingewikkelde (lees: tijdrovende) berekeningen voor schaduw, 82 reflectie en intensiteit. Om deze grote hoeveelheid gegevens te verwerken maakt 83 de \emph{GPU} gebruik een grote hoeveelheid parallelle processoren, welke alle 84 84 individueel een deel van de berekeningen op zich nemen. 85 85 86 Recente (ele ctronica) onwikkelingen zoals \emph{CUDA}\footnote{\url{http://en.wikipedia.org/wiki/CUDA}} en (meer generieke implementaties)86 Recente (elektronica) ontwikkelingen zoals \emph{CUDA}\footnote{\url{http://en.wikipedia.org/wiki/CUDA}} en (meer generieke implementaties) 87 87 \emph{OpenCL}\footnote{\url{http://en.wikipedia.org/wiki/OpenCL}} hebben ertoe 88 88 geleid dat de GPU ook door de geprogrammeerd kan worden om specifieke … … 92 92 (dus) zeer kleine buffers en instructie set heeft. Verder is het ook cruciaal 93 93 te weten dat de \emph{GPU} \textit{niet} direct gebruik gebruik kan maken van 94 het hoofd geheugen van de \emph{CPU}, maak dat de invoer en uitvoer altijd eerst94 het hoofd-geheugen van de \emph{CPU}, maak dat de invoer en uitvoer altijd eerst 95 95 naar/van de \emph{GPU} verplaatst zal moeten worden. 96 96 97 97 \section{Aanpak} 98 Het zoeken van geldige minimale domina tie verzamelingen is een stevige klus,98 Het zoeken van geldige minimale dominantie verzamelingen is een stevige klus, 99 99 welke we (in het optimale geval) $n$ koninginnen hebben die we op een $n * n$ 100 100 schaakbord kunnen plaatsen. Dat levert $(n * n)! - ((n * n)-n)!$ mogelijkheden op. 101 101 De \emph{GPU} zal gebruikt worden om oplossingen sneller te controleren en zal 102 niet gebruikt worden om effi entere oplossingen te vinden. De kracht zit hem in102 niet gebruikt worden om effici"{e}ntie oplossingen te vinden. De kracht zit hem in 103 103 het feit dat meer oplossingen getest kunnen worden en dus potentieel betere 104 104 oplossingen tussen kunnen zitten, welke ook te zien in in 105 algoritme~\ref{alg:overzicht}. De genereerde potenti eele oplossingen die aan de105 algoritme~\ref{alg:overzicht}. De genereerde potenti"{e}le oplossingen die aan de 106 106 \emph{GPU} ter controle aangeboden worden respecteren de boven- en ondergrens. 107 107 … … 110 110 01: klaar=nee 111 111 02: doe 112 03: ..bereken potentieel minimale domina tie verzamelingen112 03: ..bereken potentieel minimale dominantie verzamelingen 113 113 04: ..plaats in framebuffer 114 114 05: ..als (alle pixels zijn gemarkeerd) dan … … 116 116 08: totdat (klaar=ja) 117 117 \end{verbatim} 118 \caption{evalueren minimale domina tie set}118 \caption{evalueren minimale dominantie set} 119 119 \label{alg:overzicht} 120 120 \end{algoritm} … … 130 130 eigenschap waar een \emph{GPU} in uitblinkt; het '\emph{stempelen}' van objecten in 131 131 een raster (welke in traditionele beeldbewerking gebruikt wordt om texturen te 132 maken). Elk schaakstuk heeft zijn eigen stempel patroon zoals te zien in132 maken). Elk schaakstuk heeft zijn eigen stempel-patroon zoals te zien in 133 133 figuur~\ref{fig:stempels}. Hierbij moet opgemerkt worden dat de stempels 134 134 allemaal op hun eigen manier schalen. … … 138 138 \includegraphics[width=0.4\textwidth]{pasted5.pdf} 139 139 \end{center} 140 \caption{Door slim te coderen kunnen meerdere potenti ele oplossingen tegelijk140 \caption{Door slim te coderen kunnen meerdere potenti"{e}le oplossingen tegelijk 141 141 bekeken worden. Hier wordt gebruik gemaakt van (a) het feit dat de ruimte groter 142 142 is dan het 'schaakbord' welke bekeken wordt en (b) een pixel gecodeerd is uit 143 vier onafhankel e kleuren}143 vier onafhankelijke kleuren} 144 144 \label{fig:raster} 145 145 \end{figure} … … 147 147 gemaakt wordt, namelijk kleur en het verschil in grootte van het bord en de 148 148 geaccepteerde invoer. Door slim te combineren ---zie figuur~\ref{fig:raster}--- 149 kan het aantal potenti ele oplossingen die getest kan worden gemaximaliseerd149 kan het aantal potenti"{e}le oplossingen die getest kan worden gemaximaliseerd 150 150 worden. 151 151 152 De individu le \emph{kernels} volgen het algoritme~\ref{alg:kernel}, de test of152 De individuele \emph{kernels} volgen het algoritme~\ref{alg:kernel}, de test of 153 153 alle punten gemarkeerd zijn lijkt om het eerste gezicht een lus en test over 154 154 alle beeldpunten, echter de \emph{GPU} heeft specifieke instructies om dit 155 effi enteruit te voeren.155 effici"{e}ntie uit te voeren. 156 156 Voor het plaatsen van de stempels moet er gegaan worden voor de grafische 157 157 equivalent van een \texttt{OF} operatie. Als een \texttt{INVERSE} operatie gebruikt zou … … 166 166 04: ..oplossing=ja 167 167 \end{verbatim} 168 \caption{evalueren minimale domina tie set door individuele kernel}168 \caption{evalueren minimale dominantie set door individuele kernel} 169 169 \label{alg:kernel} 170 170 \end{algoritm} … … 175 175 \includegraphics[width=0.4\textwidth]{pasted6.pdf} 176 176 \caption{ 177 Uitvoer tijden (logaritmische schaal) van de \emph{CPU} en \emph{GPU} gebaseerde minimale domina tie 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, de beter de \emph{GPU} gaan presteren boven de \emph{CPU}} 178 178 \label{fig:uitvoertijd} 179 179 \end{figure} 180 Door het toepassen van de \emph{GPU} in het \emph{n-Queens} prob eem kunnen181 winsten 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} domina tie textuur technieken technieken lijkt voor dit180 Door het toepassen van de \emph{GPU} in het \emph{n-Queens} probleem kunnen 181 winsten 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 183 183 specifieke geval een goede vertaling van de traditionele \emph{CPU} wereld en 184 184 de \emph{GPU} wereld. De stempels bieden tevens meer vrijheden om alternatieve … … 186 186 \subsection{Verder werk} 187 187 Er zal gekeken worden of de generatie van nieuwe oplossingen ook op de 188 \emph{GPU} gedaan kan worden om zo het prob eem van de langzame context188 \emph{GPU} gedaan kan worden om zo het probleem van de langzame context 189 189 wisselingen op te lossen. 190 190 Verder zal er gekeken worden of de codering van de borden op nog een slimmere 191 manier aangepakt kan worden, in plaats van de kleur in 4 basis kleuren uit te191 manier aangepakt kan worden, in plaats van de kleur in 4 basis-kleuren uit te 192 192 splitsen zouden ook de volledige 32 bits (elke kleur is 8 bit) kunnen worden om 193 193 nog meer(combinaties) van oplossingen te coderen. … … 197 197 grafieken. Beiden lijken erg dicht bij elkaar te blijven en ik zie niet waarom 198 198 dit plots veel beter zou worden bij grotere $n$ waarden. 199 De 'tegel methode' van figuur~\ref{fig:raster} lijkt in theorie leuk, maar als199 De 'tegel-methode' van figuur~\ref{fig:raster} lijkt in theorie leuk, maar als 200 200 de $n$ groter wordt is er grote kans dat de tegels niet meer (goed) passen. Als 201 201 de $n$ groter wordt dan in mogelijke invoer is het helemaal niet meer mogelijk.
Note:
See TracChangeset
for help on using the changeset viewer.
