source: liacs/SCA2010/presentation1/presentation-paper-rvdzwet.tex

%% LyX 1.6.5 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[english]{beamer}
\usepackage{mathptmx}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{amssymb}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\DeclareRobustCommand*{\lyxarrow}{%
\@ifstar
{\leavevmode\,$\triangleleft$\,\allowbreak}
{\leavevmode\,$\triangleright$\,\allowbreak}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 % this default might be overridden by plain title style
 \newcommand\makebeamertitle{\frame{\maketitle}}%
 \AtBeginDocument{
   \let\origtableofcontents=\tableofcontents
   \def\tableofcontents{\@ifnextchar[{\origtableofcontents}{\gobbletableofcontents}}
   \def\gobbletableofcontents#1{\origtableofcontents}
 }
 \makeatletter
 \long\def\lyxframe#1{\@lyxframe#1\@lyxframestop}%
 \def\@lyxframe{\@ifnextchar<{\@@lyxframe}{\@@lyxframe<*>}}%
 \def\@@lyxframe<#1>{\@ifnextchar[{\@@@lyxframe<#1>}{\@@@lyxframe<#1>[]}}
 \def\@@@lyxframe<#1>[{\@ifnextchar<{\@@@@@lyxframe<#1>[}{\@@@@lyxframe<#1>[<*>][}}
 \def\@@@@@lyxframe<#1>[#2]{\@ifnextchar[{\@@@@lyxframe<#1>[#2]}{\@@@@lyxframe<#1>[#2][]}}
 \long\def\@@@@lyxframe<#1>[#2][#3]#4\@lyxframestop#5\lyxframeend{%
   \frame<#1>[#2][#3]{\frametitle{#4}#5}}
 \makeatother
 \def\lyxframeend{} % In case there is a superfluous frame end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usetheme{Warsaw}
% or ...

\setbeamercovered{transparent}
% or whatever (possibly just delete it)

\makeatother

\usepackage{babel}

\begin{document}





\title[Chessboard Domination on GPU]{Chessboard Domination on Programmable Graphics Hardware {[}CDGPU2006{]}}


\subtitle{{}``First algorithm to determine the minimum domination number of
a chessboard graph using the GPU''}


\author[Rick van der Zwet <hvdzwet@liacs.nl>]{Rick van der Zwet }


\institute{LIACS - Leiden University}


\date[SCA2010]{Seminar Combinatorial Algorithms, 2010}

\makebeamertitle


\pgfdeclareimage[height=0.5cm]{institution-logo}{institution-logo-filename.jpg}

\logo{\pgfuseimage{institution-logo}}





%\beamerdefaultoverlayspecification{<+->}


\lyxframeend{}\lyxframe{Outline}

\tableofcontents{}




\lyxframeend{}\section{Minimum domination set}


\lyxframeend{}\subsection[Domination set]{Domination set}


\lyxframeend{}\lyxframe{Domination set}


\framesubtitle{Capture them all }
\begin{itemize}
\item Use the least amount of items to cover a whole board
\item Item based characteristics made whole set
\end{itemize}

\lyxframeend{}\lyxframe{Queen lower bound}
\begin{itemize}
\item $y(Q_{n})\geq\frac{n-1}{2}$, $n\geq1$\cite{DM2003}
\item Every square either contains a queen, or can be reached by a queen
(e.g. least amount of pieces required)
\end{itemize}
\begin{figure}
\includegraphics[scale=0.50]{pasted1.pdf}
\end{figure}


\lyxframeend{}\subsection{GPU Inner Workings}


\lyxframeend{}\lyxframe{Board Layout}
\begin{itemize}
\item \emph{streams:} pipelines available on the GPU - a collection of records
requiring similar computation.
\item \emph{kernel:} function that is applied to each element of a stream.
\end{itemize}
In the GPU streaming model, textures, geometry, and the framebuffer
are seen as streams while vertex and fragment programs are seen as
kernels.


\lyxframeend{}\lyxframe{Outlined Figure}

\begin{figure}
\includegraphics[scale=0.75]{pasted1.png}
\end{figure}


\lyxframeend{}\section{Algoritm}


\lyxframeend{}\lyxframe{Basic Algoritm}

\texttt{01: finished=false}

\texttt{02: do}

\texttt{03: ..computes a piece configuration which may be a minimally
dominating set }

\texttt{04: ..Rendered in the framebuffer }

\texttt{05: ..if (All pixels are marked) }

\texttt{06: ....finished=true }

\texttt{07: ..fi }

\texttt{08: while (finished=false)}


\lyxframeend{}\subsection{Computing the piece configuration}


\lyxframeend{}\lyxframe{Method}
\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}

\lyxframeend{}\subsection{Rendered in Framebuffer}
\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}
\begin{figure}
\includegraphics[scale=0.50]{pasted4.pdf}
\end{figure}



\lyxframeend{}\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}

\lyxframeend{}\section{GPU Optimalizations}


\lyxframeend{}\lyxframe{Colour Channels}
\begin{figure}
\includegraphics[scale=0.50]{pasted5.pdf}
\end{figure}
\begin{itemize}
\item GPU is able to process all colours at the times
\end{itemize}

\lyxframeend{}\lyxframe{Grid Framebuffer}
\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}

\lyxframeend{}\section{Results}


\lyxframeend{}\subsection{Main Results}


\lyxframeend{}\lyxframe{Conclusions and Future Work}

%
\begin{figure}


\caption{\protect\includegraphics[scale=0.60]{pasted6}}


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{figure}



\lyxframeend{}\lyxframe{Conclusions and Future Work {[}2{]}}
\begin{itemize}
\item Domination texture good mapping between CPU world and GPU world
\item Flexible texture definition without any impact
\end{itemize}

\lyxframeend{}\subsection{Discussion}


\lyxframeend{}\lyxframe{Discussion}
\begin{itemize}
\item No significant speedup, claim that $n\geq13$ GPU is \emph{'much'
}faster
\item No scaleable
\end{itemize}

\lyxframeend{}\section*{Summary}


\lyxframeend{}\lyxframe{Summary}
\begin{itemize}
\item First GPU algoritm for solving minimum domination described at the
time
\item Using texture mapping to build bridges between the CPU world and GPU
world
\end{itemize}


\vskip0pt plus.5fill
\begin{itemize}
\item Outlook

\begin{itemize}
\item Make it scale so its decision algoritms is much smarter
\item Build a framework to allow easy and proper testing for various combinations
\end{itemize}
\end{itemize}

\lyxframeend{}

\appendix

\lyxframeend{}\section*{Appendix}


\lyxframeend{}\subsection{For Further Reading}

\beamertemplatebookbibitems
\begin{thebibliography}{2}
\bibitem{DM2003}E. J. Cockayne\newblock\emph{Chessboard domination
problems}\newblock \emph{Discrete Math}., 86:1320, 1990.

\bibitem{CDGPU2006}Nathan Courni\newblock\emph{Chessboard Domination
on Programmable Graphics Hardware}\newblock \emph{ACM SE'06 March
10-ￜ12, 2006}. Melbourne, Florida, USA\beamertemplatearticlebibitems
\end{thebibliography}

\end{document}