Changeset 143 for liacs/SCA2010/nQueens

Timestamp:

Jul 1, 2010, 8:17:44 PM (14 years ago)

Author:

Rick van der Zwet

Message:

Close to ready

File:

• liacs/SCA2010/nQueens/report.tex (modified) (5 diffs)

liacs/SCA2010/nQueens/report.tex

@@ -11 +11 @@
 \usepackage{url}
 \usepackage{amssymb,amsmath}
-\usepackage{wrapfig}
 \usepackage{lipsum}
 \usepackage{float}
@@ -17 +16 @@
 \floatstyle{ruled}
 \newfloat{algoritm}{thp}{lop}
-\floatname{algoritm}{Algoritm}
+\floatname{algoritm}{Algoritme}
 
 \title{\emph{n-Queens} minimale dominatie verzamelingen \\
@@ -53 +52 @@
 \section{Minimale dominatie verzameling}
 De minimale dominatie verzameling ({\emph{Minimum domination set}}) is
-een setup waarbij elk vakje van het schaakbord door ten minste 1 koningin
-geslagen kan worden of 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 bepaald worden dmv van
-formule~\ref{eq:ondergrens}.  
+een setup waarbij zo weinig mogelijk koninginnen wordt gembruikt om elk vakje
+van het schaakbord door ten minste 1 koningin geslagen kan worden of 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
+bepaald worden dmv 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' dominatie verzameling is dan hoeft het aantal koninginnen
+niet per-se minimaal zijn.
 
 
 \section{Grafische Verwerking Eenheid}
+\begin{figure}
+  \centering
+  \includegraphics[width=0.4\textwidth]{pasted1.png}
+  \caption{\emph{GPU} werking. De verschillende \emph{GPU} processorblokken
+worden \emph{kernels} genoemd. De data wordt getransporteerd door verschillende
+datakanalen (\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}.} 
+  \label{fig:werking}
+\end{figure}
 De Grafische Verwerking Eenheid (\emph{Graphics Processing Unit} ook bekend als
 \emph{GPU}) heeft speciale electronica om ervoor te zorgen dat deze snel de
@@ -83 +94 @@
 het hoofdgeheugen van de \emph{CPU}, maak dat de invoer en uitvoer altijd eerst
 naar/van de \emph{GPU} verplaatst zal moeten worden.
-\begin{figure}
-  \begin{center}
-    \includegraphics[width=0.4\textwidth]{pasted1.png}
-  \end{center}
-  \caption{\emph{GPU} werking. De verschillende \emph{GPU} processorblokken
-worden \emph{kernels} genoemd. De data wordt getransporteerd door verschillende
-datakanalen (\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}} \label{fig:werking}
-\end{figure}
-
-\section{Algoritme}
+
+\section{Aanpak}
 Het zoeken van geldige minimale dominatie verzamelingen is een stevige klus,
 welke we (in het optimale geval) $n$ koninginnen hebben 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 controlen en zal
-niet gebruikt worden om effientere oplossingen te vinden.
+De \emph{GPU} zal gebruikt worden om oplossingen sneller te controleren en zal
+niet gebruikt worden om effientere 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 potentieele oplossingen die aan de
+\emph{GPU} ter controle aangeboden worden respecteren de boven- en ondergrens.
 
 \begin{algoritm}
@@ -105 +110 @@
 01: klaar=nee
 02: doe
-03: ..bereken potentieel minimale dominatie verzameling 
+03: ..bereken potentieel minimale dominatie verzamelingen
 04: ..plaats in framebuffer
 05: ..als (alle pixels zijn gemarkeerd) dan
 06: ....klaar=ja 
-07: ..eindeals
 08: totdat (klaar=ja)
 \end{verbatim}
-\caption{aanpak minimale dominatie set}
+\caption{evalueren minimale dominatie set}
+\label{alg:overzicht}
 \end{algoritm}
-\subsection{Computing the piece configuration}
-\begin{itemize}
-\item Exhaustive manner
-\item Piece configuration stored on the CPU as linked links
-\item Lower bound and Upper bound is respected
-\end{itemize}
-
-\subsection{Rendered in Framebuffer}
-\begin{wrapfigure}{r}{0.4\textwidth}
-  \begin{center}
-    \includegraphics[width=0.4\textwidth]{pasted4.pdf}
-  \end{center}
-  \caption{The Toucan}
-\end{wrapfigure}
-\begin{itemize}
-\item GPU supports textures, every piece is a texture
-\item Render points on the CPU and offload to the GPU to map texture on
-specific place
-\end{itemize}
-
-\subsection{Determine Domination (e.g. Mark solution)}
-\begin{itemize}
-\item Simple approch
-\item Sum all pixels of $n*n$ board and match if $sum=n*n$
-\end{itemize}
-
-\section{GPU Optimalizations}
-\begin{wrapfigure}{r}{0.4\textwidth}
+
+\subsection{Detectie algoritme}
+\begin{figure}
+  \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}  
+  \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
+een raster (welke in traditionele beeldbewerking gebruikt wordt om texturen te
+maken). Elk schaakstuk heeft zijn eigen stempelpatroon zoals te zien in
+figuur~\ref{fig:stempels}. Hierbij moet opgemerkt worden dat de stempels
+allemaal op hun eigen manier schalen.
+
+\begin{figure}
   \begin{center}
     \includegraphics[width=0.4\textwidth]{pasted5.pdf}
   \end{center}
-  \caption{The Toucan}
-\end{wrapfigure}
-\begin{itemize}
-\item GPU is able to process all colours at the times
-Grid Framebuffer
-\end{itemize}
-\begin{itemize}
-\item GPU has many CPU's called kernels
-\item Each kernel can process it's own little block of information
-\item Putting multiple possible solutions in one bloc
-\end{itemize}
-
-\section{Uitleg probleem}
-\section{Theorie}
-\section{Aanpak}
-\section{Implementatie}
-\section{Experimenten}
+  \caption{Door slim te coderen kunnen meerdere potentiele 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 onafhankele 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}---
+kan het aantal potentiele oplossingen die getest kan worden gemaximaliseerd
+worden.
+
+De individule \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
+alle beeldpunten, echter de \emph{GPU} heeft specifieke instructies om dit
+effienter 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
+worden om de stempel te plaatsen zou een tweede overlappende stempel onterecht
+als niet geraakt gemarkeerd worden.
+
+\begin{algoritm}
+\begin{verbatim}
+01: voor elke stempels in stempel locatie
+02: ..plaats stempel
+03: als (alle punten gemarkeerd) dan
+04: ..oplossing=ja
+\end{verbatim}
+\caption{evalueren minimale dominatie set door individuele kernel}
+\label{alg:kernel}
+\end{algoritm}
+
 \section{Conclusie}
-\begin{wrapfigure}{r}{0.4\textwidth}
-  \begin{center}
-    \includegraphics[width=0.4\textwidth]{pasted6.pdf}
-  \end{center}
-\caption{
-Execution times (log scale) of CPU and GPU based minimum domination
-implementations computing $y(Q_{n})$. As $n$ increases, the GPU's
-speed advantage over the CPU become more evident.}
-\end{wrapfigure}
-
-\begin{itemize}
-\item Domination texture good mapping between CPU world and GPU world
-\item Flexible texture definition without any impact
-\end{itemize}
-
-\subsection{Discussion}
-\begin{itemize}
-\item No significant speedup, claim that $n\geq13$ GPU is \emph{'much'} faster 
-\item No scaleable
-\end{itemize}
+  \begin{figure}
+  \centering
+  \includegraphics[width=0.4\textwidth]{pasted6.pdf}
+  \caption{
+  Uitvoer tijden (logaritmische schaal) van de \emph{CPU} en \emph{GPU} gebaseerde minimale dominatie implementaties welke $y(Q_{n})$ uitrekenen. Hoe groter $n$ wordt, de beter de \emph{GPU} gaan presteren boven de \emph{CPU}} 
+  \label{fig:uitvoertijd}
+\end{figure}
+Door het toepassen van de \emph{GPU} in het \emph{n-Queens} probeem 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} dominatie textuur technieken 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.
+\subsection{Verder werk} 
+Er zal gekeken worden of de generatie van nieuwe oplossingen ook op de
+\emph{GPU} gedaan kan worden om zo het probeem 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 basiskleuren uit te
+splitsen zouden ook de volledige 32 bits (elke kleur is 8 bit) 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
+dit plots veel beter zou worden bij grotere $n$ waarden.
+De 'tegelmethode' 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}