Changeset 142 for liacs/SCA2010/nQueens

Timestamp:

Jul 1, 2010, 2:59:37 PM (14 years ago)

Author:

Rick van der Zwet

Message:

Not ready yet, but going on the road...

Location:

liacs/SCA2010/nQueens

Files:

• latex.mk (modified) (1 diff)
• pasted1.eps (added)
• pasted1.pdf (added)
• pasted1.png (added)
• pasted4.pdf (added)
• pasted5.pdf (added)
• pasted6.pdf (added)
• report.tex (modified) (2 diffs)

liacs/SCA2010/nQueens/latex.mk

@@ -56 +56 @@
         $(ASPELL) -l en -p ~/aspell-en.dic $(ASPELL_ARGS) $<
 
-.dvi.pdf:
-        $(DVIPDF) $? $@
+#.dvi.pdf:
+#       $(DVIPDF) $? $@
+
+.tex.pdf:
+        pdflatex -halt-on-error $?
 
 .tex.dvi:

liacs/SCA2010/nQueens/report.tex

@@ -8 +8 @@
 \usepackage[english,dutch]{babel}
 \selectlanguage{dutch}
-\usepackage{graphicx}
+\usepackage[pdftex]{graphicx}
 \usepackage{url}
-\usepackage{multicol}
-\usepackage{fancybox}
 \usepackage{amssymb,amsmath}
+\usepackage{wrapfig}
+\usepackage{lipsum}
+\usepackage{float}
 
-\author{Rick van der Zwet, Universiteit Leiden}
-\title{XXX \\
-\large{XXX}}
+\floatstyle{ruled}
+\newfloat{algoritm}{thp}{lop}
+\floatname{algoritm}{Algoritm}
+
+\title{\emph{n-Queens} minimale dominatie verzamelingen \\
+\large{Chessboard Domination on Programmable Graphics Hardware door Nathan Cournik}}
 \author{Rick van der Zwet\\
-  \texttt{<hvdzwet@liacs.nl>}\\
-  \\
-  LIACS\\
-  Leiden University\\
-  Niels Bohrweg 1\\
-  2333 CA Leiden\\
-  The Netherlands}
+  \texttt{<hvdzwet@liacs.nl>}}
 \date{\today}
 
+
 \begin{document}
-
 \maketitle
+\begin{abstract}
+Dit schrijven zal het paper van Nathan Cournik \emph{Chessboard Domination on
+Programmable Graphics Hardware}~\cite{CDGPU2006} ---en in het speciaal de
+gepresenteerde n-Queens oplossing--- vrij samenvatten in het nederlands en zal
+de mening van de ondergetekende op het geheel geven.
+\end{abstract}
 
 \section{Inleiding}
+\begin{figure}
+  \begin{center}
+    \includegraphics[width=0.5\textwidth]{pasted1.pdf}
+  \end{center}
+  \caption{Links; koningin kan dit patroon slaan. Rechts; ongeldige \emph{n-Queens} oplossing, opdat de koninginnen rechtsonder elkaar kunnen slaan}
+  \label{fig:patroon}
+\end{figure}
+Vanwege het het feit dat \emph{n-Queens} een algemeen geaccepteerde termiologie
+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 orginele engelse bewoordinging
+staan om zo terugzoeken en refereren in het orginele paper~\cite{CDGPU2006}
+makkelijker te maken.
+
+
+\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}.  
+\begin{equation}
+y(Q_{n})\geq\frac{n-1}{2}, n\geq1
+\label{eq:ondergrens}
+\end{equation}
+
+
+\section{Grafische Verwerking Eenheid}
+De Grafische Verwerking Eenheid (\emph{Graphics Processing Unit} ook bekend als
+\emph{GPU}) heeft speciale electronica om ervoor te zorgen dat deze snel de
+\emph{RGB} waardes van alle beeldpunten kan berekenen in complexe beeldsystemen
+met bijvoorbeeld ingewikkende (lees: tijdrovende) berekeningen voor schaduw,
+reflextie en intensiteit. Om deze grote hoeveelheid gegevens te verwerken maakt
+de \emph{GPU} gebruik een grote hoeveelheid parralelle processoren, welke alle
+individueel een deel van de berekeningen op zich nemen.
+
+Recente (electronica) onwikkelingen zoals \emph{CUDA}\footnote{\url{http://en.wikipedia.org/wiki/CUDA}} en (meer generieke implementaties)
+\emph{OpenCL}\footnote{\url{http://en.wikipedia.org/wiki/OpenCL}} hebben ertoe
+geleid dat de GPU ook door de 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
+is belangrijk om te beseffen dat de \emph{GPU} een heel simpele processor is en
+(dus) zeer kleine buffers en instructie set heeft. Verder is het ook cruciaal
+te weten dat de \emph{GPU} \textit{niet} direct gebruik gebruik kan maken van
+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}
+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.
+
+\begin{algoritm}
+\begin{verbatim}
+01: klaar=nee
+02: doe
+03: ..bereken potentieel minimale dominatie verzameling 
+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}
+\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}
+  \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}
@@ -38 +163 @@
 \section{Experimenten}
 \section{Conclusie}
-\begin{thebibliography}{10}
+\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{thebibliography}{2}
+\bibitem[DM2003]{DM2003}E. J. Cockayne, emph{Chessboard domination
+problems}, \emph{Discrete Math}, 86:1320, 1990.
+
+\bibitem[CDGPU2006]{CDGPU2006}Nathan Cournik,\emph{Chessboard Domination
+on Programmable Graphics Hardware}, \emph{ACM SE'06 March
+10-­12, 2006}. Melbourne, Florida, USA
 \end{thebibliography}
 \newpage
-% \advance\textwidth by 8cm
-% \advance\oddsidemargin by -3cm
-% \advance\evensidemargin by -3cm
-% \advance\topmargin by -2cm
-% \advance\textheight by 4cm
-% \advance\footskip by -4cm
-% \marginparwidth 0cm
-% \twocolumn
-% \section*{Appendix}
-% De NN code en pre-parse.pl code  zagen er als volgt uit:
-% \newline
-% \tiny
-% %preformatted with `source-highlight -n -f latex bridge.cc`
-% \input{nn.c}
-% \input{data/pre-parse.pl}
-% \onecolumn
-
 \end{document}