Index: liacs/SCA2010/presentation1/presentation-paper-rvdzwet.aux
===================================================================
--- liacs/SCA2010/presentation1/presentation-paper-rvdzwet.aux	(revision 124)
+++ liacs/SCA2010/presentation1/presentation-paper-rvdzwet.aux	(revision 124)
@@ -0,0 +1,98 @@
+\relax 
+\ifx\hyper@anchor\@undefined
+\global \let \oldcontentsline\contentsline
+\gdef \contentsline#1#2#3#4{\oldcontentsline{#1}{#2}{#3}}
+\global \let \oldnewlabel\newlabel
+\gdef \newlabel#1#2{\newlabelxx{#1}#2}
+\gdef \newlabelxx#1#2#3#4#5#6{\oldnewlabel{#1}{{#2}{#3}}}
+\AtEndDocument{\let \contentsline\oldcontentsline
+\let \newlabel\oldnewlabel}
+\else
+\global \let \hyper@last\relax 
+\fi
+
+\@writefile{toc}{\beamer@endinputifotherversion {3.07pt}}
+\@writefile{nav}{\beamer@endinputifotherversion {3.07pt}}
+\select@language{english}
+\@writefile{toc}{\select@language{english}}
+\@writefile{lof}{\select@language{english}}
+\@writefile{lot}{\select@language{english}}
+\@writefile{nav}{\headcommand {\slideentry {0}{0}{1}{1/1}{}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {1}{1}}}
+\@writefile{nav}{\headcommand {\slideentry {0}{0}{2}{2/2}{}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {2}{2}}}
+\@writefile{toc}{\beamer@sectionintoc {1}{Minimum domination set}{3}{0}{1}}
+\@writefile{nav}{\headcommand {\sectionentry {1}{Minimum domination set}{3}{Minimum domination set}{0}}}
+\@writefile{nav}{\headcommand {\beamer@sectionpages {1}{2}}}
+\@writefile{nav}{\headcommand {\beamer@subsectionpages {1}{2}}}
+\@writefile{toc}{\beamer@subsectionintoc {1}{1}{Domination set}{3}{0}{1}}
+\@writefile{nav}{\headcommand {\beamer@subsectionentry {0}{1}{1}{3}{Domination set}}\headcommand {\beamer@subsectionpages {3}{2}}}
+\@writefile{nav}{\headcommand {\slideentry {1}{1}{1}{3/3}{Domination set}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {3}{3}}}
+\citation{DM2003}
+\@writefile{nav}{\headcommand {\slideentry {1}{1}{2}{4/4}{Domination set}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {4}{4}}}
+\@writefile{toc}{\beamer@subsectionintoc {1}{2}{GPU Inner Workings}{5}{0}{1}}
+\@writefile{nav}{\headcommand {\beamer@subsectionentry {0}{1}{2}{5}{GPU Inner Workings}}\headcommand {\beamer@subsectionpages {3}{4}}}
+\@writefile{nav}{\headcommand {\slideentry {1}{2}{1}{5/5}{GPU Inner Workings}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {5}{5}}}
+\@writefile{nav}{\headcommand {\slideentry {1}{2}{2}{6/6}{GPU Inner Workings}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {6}{6}}}
+\@writefile{toc}{\beamer@sectionintoc {2}{Algoritm}{7}{0}{2}}
+\@writefile{nav}{\headcommand {\sectionentry {2}{Algoritm}{7}{Algoritm}{0}}}
+\@writefile{nav}{\headcommand {\beamer@sectionpages {3}{6}}}
+\@writefile{nav}{\headcommand {\beamer@subsectionpages {5}{6}}}
+\@writefile{nav}{\headcommand {\slideentry {2}{0}{3}{7/7}{}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {7}{7}}}
+\@writefile{toc}{\beamer@subsectionintoc {2}{1}{Computing the piece configuration}{8}{0}{2}}
+\@writefile{nav}{\headcommand {\beamer@subsectionentry {0}{2}{1}{8}{Computing the piece configuration}}\headcommand {\beamer@subsectionpages {7}{7}}}
+\@writefile{nav}{\headcommand {\slideentry {2}{1}{1}{8/8}{Computing the piece configuration}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {8}{8}}}
+\@writefile{toc}{\beamer@subsectionintoc {2}{2}{Rendered in Framebuffer}{9}{0}{2}}
+\@writefile{nav}{\headcommand {\beamer@subsectionentry {0}{2}{2}{9}{Rendered in Framebuffer}}\headcommand {\beamer@subsectionpages {8}{8}}}
+\@writefile{toc}{\beamer@subsectionintoc {2}{3}{Determine Domination (e.g. Mark solution)}{9}{0}{2}}
+\@writefile{nav}{\headcommand {\beamer@subsectionentry {0}{2}{3}{9}{Determine Domination (e.g. Mark solution)}}\headcommand {\beamer@subsectionpages {9}{8}}}
+\@writefile{toc}{\beamer@sectionintoc {3}{GPU Optimalizations}{9}{0}{3}}
+\@writefile{nav}{\headcommand {\sectionentry {3}{GPU Optimalizations}{9}{GPU Optimalizations}{0}}}
+\@writefile{nav}{\headcommand {\beamer@sectionpages {7}{8}}}
+\@writefile{nav}{\headcommand {\beamer@subsectionpages {9}{8}}}
+\@writefile{nav}{\headcommand {\slideentry {3}{0}{1}{9/9}{}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {9}{9}}}
+\@writefile{nav}{\headcommand {\slideentry {3}{0}{2}{11/11}{}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {11}{11}}}
+\@writefile{toc}{\beamer@sectionintoc {4}{Results}{12}{0}{4}}
+\@writefile{nav}{\headcommand {\sectionentry {4}{Results}{12}{Results}{0}}}
+\@writefile{nav}{\headcommand {\beamer@sectionpages {9}{11}}}
+\@writefile{nav}{\headcommand {\beamer@subsectionpages {9}{11}}}
+\@writefile{toc}{\beamer@subsectionintoc {4}{1}{Main Results}{12}{0}{4}}
+\@writefile{nav}{\headcommand {\beamer@subsectionentry {0}{4}{1}{12}{Main Results}}\headcommand {\beamer@subsectionpages {12}{11}}}
+\@writefile{nav}{\headcommand {\slideentry {4}{1}{1}{12/12}{Main Results}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {12}{12}}}
+\@writefile{nav}{\headcommand {\slideentry {4}{1}{2}{13/13}{Main Results}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {13}{13}}}
+\@writefile{toc}{\beamer@subsectionintoc {4}{2}{Discussion}{14}{0}{4}}
+\@writefile{nav}{\headcommand {\beamer@subsectionentry {0}{4}{2}{14}{Discussion}}\headcommand {\beamer@subsectionpages {12}{13}}}
+\@writefile{nav}{\headcommand {\slideentry {4}{2}{1}{14/14}{Discussion}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {14}{14}}}
+\@writefile{nav}{\headcommand {\sectionentry {5}{Summary}{15}{Summary}{0}}}
+\@writefile{nav}{\headcommand {\beamer@sectionpages {12}{14}}}
+\@writefile{nav}{\headcommand {\beamer@subsectionpages {14}{14}}}
+\@writefile{nav}{\headcommand {\slideentry {5}{0}{2}{15/15}{}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {15}{15}}}
+\bibcite{DM2003}{\hyperlink {beamerbibDM2003}{1}}
+\bibcite{CDGPU2006}{\hyperlink {beamerbibCDGPU2006}{2}}
+\@writefile{nav}{\headcommand {\partentry {Appendix}{1}}}
+\@writefile{nav}{\headcommand {\beamer@partpages {1}{15}}}
+\@writefile{nav}{\headcommand {\beamer@sectionpages {15}{15}}}
+\@writefile{nav}{\headcommand {\beamer@subsectionpages {15}{15}}}
+\@writefile{nav}{\headcommand {\beamer@appendixpages {16}}}
+\@writefile{nav}{\headcommand {\sectionentry {6}{Appendix}{16}{Appendix}{1}}}
+\@writefile{nav}{\headcommand {\beamer@sectionpages {16}{15}}}
+\@writefile{nav}{\headcommand {\beamer@subsectionpages {16}{15}}}
+\@writefile{toc}{\beamer@subsectionintoc {6}{1}{For Further Reading}{16}{1}{4}}
+\@writefile{nav}{\headcommand {\beamer@subsectionentry {1}{6}{1}{16}{For Further Reading}}\headcommand {\beamer@subsectionpages {16}{15}}}
+\@writefile{nav}{\headcommand {\beamer@partpages {16}{16}}}
+\@writefile{nav}{\headcommand {\beamer@subsectionpages {16}{16}}}
+\@writefile{nav}{\headcommand {\beamer@sectionpages {16}{16}}}
+\@writefile{nav}{\headcommand {\beamer@documentpages {16}}}
+\@writefile{nav}{\headcommand {\def \inserttotalframenumber {14}}}
Index: liacs/SCA2010/presentation1/presentation-paper-rvdzwet.blg
===================================================================
--- liacs/SCA2010/presentation1/presentation-paper-rvdzwet.blg	(revision 124)
+++ liacs/SCA2010/presentation1/presentation-paper-rvdzwet.blg	(revision 124)
@@ -0,0 +1,4 @@
+This is BibTeX, Version 0.99cThe top-level auxiliary file: presentation-paper-rvdzwet.aux
+I found no \bibdata command---while reading file presentation-paper-rvdzwet.aux
+I found no \bibstyle command---while reading file presentation-paper-rvdzwet.aux
+(There were 2 error messages)
Index: liacs/SCA2010/presentation1/presentation-paper-rvdzwet.lyx
===================================================================
--- liacs/SCA2010/presentation1/presentation-paper-rvdzwet.lyx	(revision 124)
+++ liacs/SCA2010/presentation1/presentation-paper-rvdzwet.lyx	(revision 124)
@@ -0,0 +1,1010 @@
+#LyX 1.6.5 created this file. For more info see http://www.lyx.org/
+\lyxformat 345
+\begin_document
+\begin_header
+\textclass beamer
+\begin_preamble
+\usetheme{Warsaw}
+% or ...
+
+\setbeamercovered{transparent}
+% or whatever (possibly just delete it)
+\end_preamble
+\use_default_options false
+\language english
+\inputencoding auto
+\font_roman times
+\font_sans default
+\font_typewriter default
+\font_default_family default
+\font_sc false
+\font_osf false
+\font_sf_scale 100
+\font_tt_scale 100
+
+\graphics default
+\paperfontsize default
+\spacing single
+\use_hyperref false
+\papersize default
+\use_geometry false
+\use_amsmath 2
+\use_esint 0
+\cite_engine basic
+\use_bibtopic false
+\paperorientation portrait
+\secnumdepth 2
+\tocdepth 2
+\paragraph_separation indent
+\defskip medskip
+\quotes_language english
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+\tracking_changes false
+\output_changes false
+\author "" 
+\author "" 
+\end_header
+
+\begin_body
+
+\begin_layout Standard
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+This file is a solution template for:
+\end_layout
+
+\begin_layout Itemize
+Talk at a conference/colloquium.
+ 
+\end_layout
+
+\begin_layout Itemize
+Talk length is about 20min.
+ 
+\end_layout
+
+\begin_layout Itemize
+Style is ornate.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Note Note
+status collapsed
+
+\begin_layout Plain Layout
+Copyright 2004 by Till Tan tau <tantau@users.sourceforge.net>.
+ 
+\end_layout
+
+\begin_layout Plain Layout
+In principle, this file can be redistributed and/or modified under the terms
+ of the GNU Public License, version 2.
+ However, this file is supposed to be a template to be modified for your
+ own needs.
+ For this reason, if you use this file as a template and not specifically
+ distribute it as part of a another package/program, the author grants the
+ extra permission to freely copy and modify this file as you see fit and
+ even to delete this copyright notice.
+ 
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Title
+Chessboard Domination on Programmable Graphics Hardware [CDGPU2006]
+\begin_inset OptArg
+status open
+
+\begin_layout Plain Layout
+Chessboard Domination on GPU
+\begin_inset Note Note
+status collapsed
+
+\begin_layout Plain Layout
+optional, use only with long paper titles
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Subtitle
+\begin_inset Quotes eld
+\end_inset
+
+First algorithm to determine the minimum domination number of a chessboard
+ graph using the GPU
+\begin_inset Quotes erd
+\end_inset
+
+
+\end_layout
+
+\begin_layout Author
+Rick van der Zwet 
+\begin_inset Note Note
+status collapsed
+
+\begin_layout Itemize
+Give the names in the same order as the appear in the paper.
+ 
+\end_layout
+
+\begin_layout Itemize
+Use the 
+\begin_inset Quotes eld
+\end_inset
+
+Institute mark
+\begin_inset Quotes erd
+\end_inset
+
+ inset (
+\family sans
+Insert\SpecialChar \menuseparator
+Custom Insets\SpecialChar \menuseparator
+InstituteMark
+\family default
+) only if the authors have different affiliations.
+\end_layout
+
+\end_inset
+
+
+\begin_inset OptArg
+status open
+
+\begin_layout Plain Layout
+Rick van der Zwet <hvdzwet@liacs.nl>
+\begin_inset Note Note
+status collapsed
+
+\begin_layout Plain Layout
+- optional, use only with lots of authors
+\end_layout
+
+\begin_layout Plain Layout
+- if there are really lots of authors, use 
+\begin_inset Quotes eld
+\end_inset
+
+Author ET al.
+\begin_inset Quotes erd
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Institute
+LIACS - Leiden University
+\end_layout
+
+\begin_layout Date
+Seminar Combinatorial Algorithms, 2010
+\begin_inset Note Note
+status collapsed
+
+\begin_layout Itemize
+Either use conference name or its abbreviation.
+ 
+\end_layout
+
+\begin_layout Itemize
+Not really informative to the audience, more for people (including yourself)
+ who are reading the slides online
+\end_layout
+
+\end_inset
+
+
+\begin_inset OptArg
+status open
+
+\begin_layout Plain Layout
+SCA2010
+\begin_inset Note Note
+status collapsed
+
+\begin_layout Plain Layout
+optional, should be abbreviation of conference name
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+If you have a file called "institution-logo-filename.xxx", where xxx is a
+ graphic format that can be processed by latex or pdflatex, resp., then you
+ can add a logo by uncommenting the following:
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+pgfdeclareimage[height=0.5cm]{institution-logo}{institution-logo-filename}
+\end_layout
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+logo{
+\backslash
+pgfuseimage{institution-logo}}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+The following causes the table of contents to be shown at the beginning
+ of every subsection.
+ Delete this, if you do not want it.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+If you wish to uncover everything in a step-wise fashion, uncomment the
+ following command:
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+%
+\backslash
+beamerdefaultoverlayspecification{<+->}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout BeginFrame
+Outline
+\end_layout
+
+\begin_layout Standard
+\begin_inset CommandInset toc
+LatexCommand tableofcontents
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+Structuring a talk is a difficult task and the following structure may not
+ be suitable.
+ Here are some rules that apply for this solution: 
+\end_layout
+
+\begin_layout Itemize
+Exactly two or three sections (other than the summary).
+ 
+\end_layout
+
+\begin_layout Itemize
+At *most* three subsections per section.
+ 
+\end_layout
+
+\begin_layout Itemize
+Talk about 30s to 2min per frame.
+ So there should be between about 15 and 30 frames, all told.
+\end_layout
+
+\begin_layout Itemize
+A conference audience is likely to know very little of what you are going
+ to talk about.
+ So *simplify*! 
+\end_layout
+
+\begin_layout Itemize
+In a 20min talk, getting the main ideas across is hard enough.
+ Leave out details, even if it means being less precise than you think necessary.
+ 
+\end_layout
+
+\begin_layout Itemize
+If you omit details that are vital to the proof/implementation, just say
+ so once.
+ Everybody will be happy with that.
+ 
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Section
+Minimum domination set
+\end_layout
+
+\begin_layout Subsection
+Domination set
+\begin_inset OptArg
+status open
+
+\begin_layout Plain Layout
+Domination set
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout BeginFrame
+Domination set
+\end_layout
+
+\begin_layout FrameSubtitle
+Capture them all 
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+A title should summarize the slide in an understandable fashion for anyone
+ how does not follow everything on the slide itself.
+ 
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Itemize
+Use the least amount of items to cover a whole board
+\end_layout
+
+\begin_layout Itemize
+Item based characteristics made whole set
+\end_layout
+
+\begin_layout BeginFrame
+Queen lower bound
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $y(Q_{n})\geq\frac{n-1}{2}$
+\end_inset
+
+, 
+\begin_inset Formula $n\geq1$
+\end_inset
+
+
+\begin_inset CommandInset citation
+LatexCommand cite
+key "DM2003"
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Itemize
+Every square either contains a queen, or can be reached by a queen (e.g.
+ least amount of pieces required)
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Graphics
+	filename pasted1.emf
+	scale 99
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Subsection
+GPU Inner Workings
+\end_layout
+
+\begin_layout BeginFrame
+Board Layout
+\end_layout
+
+\begin_layout Itemize
+
+\emph on
+streams:
+\emph default
+ pipelines available on the GPU - a collection of records requiring similar
+ computation.
+\end_layout
+
+\begin_layout Itemize
+
+\emph on
+kernel:
+\emph default
+ function that is applied to each element of a stream.
+\end_layout
+
+\begin_layout Standard
+In the GPU streaming model, textures, geometry, and the framebuffer are
+ seen as streams while vertex and fragment programs are seen as kernels.
+\end_layout
+
+\begin_layout BeginFrame
+Outlined Figure
+\end_layout
+
+\begin_layout Standard
+\begin_inset Graphics
+	filename C:/Documents and Settings/rvdzwet/Desktop/liacs/SCA2010/presentation1/pasted1.png
+	scale 99
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Section
+Algoritm
+\end_layout
+
+\begin_layout BeginFrame
+Basic Algoritm
+\end_layout
+
+\begin_layout Standard
+
+\family typewriter
+01: finished=false
+\end_layout
+
+\begin_layout Standard
+
+\family typewriter
+02: do
+\end_layout
+
+\begin_layout Standard
+
+\family typewriter
+03: ..computes a piece configuration which may be a minimally dominating set
+ 
+\end_layout
+
+\begin_layout Standard
+
+\family typewriter
+04: ..Rendered in the framebuffer 
+\end_layout
+
+\begin_layout Standard
+
+\family typewriter
+05: ..if (All pixels are marked) 
+\end_layout
+
+\begin_layout Standard
+
+\family typewriter
+06: ....finished=true 
+\end_layout
+
+\begin_layout Standard
+
+\family typewriter
+07: ..fi 
+\end_layout
+
+\begin_layout Standard
+
+\family typewriter
+08: while (finished=false)
+\end_layout
+
+\begin_layout Subsection
+Computing the piece configuration
+\end_layout
+
+\begin_layout BeginFrame
+Method
+\end_layout
+
+\begin_layout Itemize
+Exhaustive manner
+\end_layout
+
+\begin_layout Itemize
+Piece configuration stored on the CPU as linked links
+\end_layout
+
+\begin_layout Itemize
+Lower bound and Upper bound is respected
+\end_layout
+
+\begin_layout Subsection
+Rendered in Framebuffer
+\end_layout
+
+\begin_layout Itemize
+GPU supports textures, every piece is a texture
+\end_layout
+
+\begin_layout Itemize
+Render points on the CPU and offload to the GPU to map texture on specific
+ place
+\end_layout
+
+\begin_layout Standard
+\begin_inset Graphics
+	filename C:/Documents and Settings/rvdzwet/Desktop/liacs/SCA2010/presentation1/pasted4.emf
+	scale 99
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Subsection
+Determine Domination (e.g.
+ Mark solution)
+\end_layout
+
+\begin_layout Itemize
+Simple approch
+\end_layout
+
+\begin_layout Itemize
+Sum all pixels of 
+\begin_inset Formula $n*n$
+\end_inset
+
+ board and match if 
+\begin_inset Formula $sum=n*n$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Section
+GPU Optimalizations
+\end_layout
+
+\begin_layout BeginFrame
+Colour Channels
+\end_layout
+
+\begin_layout Standard
+\begin_inset Graphics
+	filename C:/Documents and Settings/rvdzwet/Desktop/liacs/SCA2010/presentation1/pasted5.emf
+	scale 99
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Itemize
+GPU is able to process all colours at the times
+\end_layout
+
+\begin_layout BeginFrame
+Grid Framebuffer
+\end_layout
+
+\begin_layout Itemize
+GPU has many CPU's called kernels
+\end_layout
+
+\begin_layout Itemize
+Each kernel can process it's own little block of information
+\end_layout
+
+\begin_layout Itemize
+Putting multiple possible solutions in one bloc
+\end_layout
+
+\begin_layout Section
+Results
+\end_layout
+
+\begin_layout Subsection
+Main Results
+\end_layout
+
+\begin_layout BeginFrame
+Conclusions and Future Work
+\end_layout
+
+\begin_layout Standard
+\begin_inset Float figure
+wide false
+sideways false
+status open
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\begin_layout Plain Layout
+\begin_inset Caption
+
+\begin_layout Plain Layout
+\begin_inset Graphics
+	filename pasted6.emf
+	scale 99
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+Execution times (log scale) of CPU and GPU based minimum domination implementati
+ons computing 
+\begin_inset Formula $y(Q_{n})$
+\end_inset
+
+.
+ As 
+\begin_inset Formula $n$
+\end_inset
+
+ increases, the GPU's speed advantage over the CPU become more evident.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout BeginFrame
+Conclusions and Future Work [2]
+\end_layout
+
+\begin_layout Itemize
+Domination texture good mapping between CPU world and GPU world
+\end_layout
+
+\begin_layout Itemize
+Flexible texture definition without any impact
+\end_layout
+
+\begin_layout Subsection
+Discussion
+\end_layout
+
+\begin_layout BeginFrame
+Discussion
+\end_layout
+
+\begin_layout Itemize
+No significant speedup, claim that 
+\begin_inset Formula $n\geq13$
+\end_inset
+
+ GPU is 
+\emph on
+'much' 
+\emph default
+faster
+\end_layout
+
+\begin_layout Itemize
+No scaleable
+\end_layout
+
+\begin_layout Section*
+Summary
+\end_layout
+
+\begin_layout BeginFrame
+Summary
+\end_layout
+
+\begin_layout Itemize
+First GPU algoritm for solving minimum domination described at the time
+\end_layout
+
+\begin_layout Itemize
+Using texture mapping to build bridges between the CPU world and GPU world
+\end_layout
+
+\begin_layout Standard
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+An outlook is always optional.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status collapsed
+
+\begin_layout Plain Layout
+
+
+\backslash
+vskip0pt plus.5fill
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Itemize
+Outlook
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+Make it scale so its decision algoritms is much smarter
+\end_layout
+
+\begin_layout Itemize
+Build a framework to allow easy and proper testing for various combinations
+\end_layout
+
+\end_deeper
+\begin_layout EndFrame
+
+\end_layout
+
+\begin_layout Section*
+\start_of_appendix
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+All of the following is optional and typically not needed.
+\end_layout
+
+\end_inset
+
+Appendix
+\end_layout
+
+\begin_layout Subsection*
+For Further Reading
+\end_layout
+
+\begin_layout BeginFrame
+For Further Reading
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status collapsed
+
+\begin_layout Plain Layout
+
+
+\backslash
+beamertemplatebookbibitems
+\end_layout
+
+\end_inset
+
+
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+Start with overview books.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Bibliography
+\begin_inset CommandInset bibitem
+LatexCommand bibitem
+key "DM2003"
+
+\end_inset
+
+E.
+ J.
+ Cockayne
+\begin_inset ERT
+status collapsed
+
+\begin_layout Plain Layout
+
+
+\backslash
+newblock
+\end_layout
+
+\end_inset
+
+
+\emph on
+Chessboard domination problems
+\emph default
+
+\begin_inset ERT
+status collapsed
+
+\begin_layout Plain Layout
+
+
+\backslash
+newblock
+\end_layout
+
+\end_inset
+
+ 
+\emph on
+Discrete Math
+\emph default
+., 86:1320, 1990.
+\end_layout
+
+\begin_layout Bibliography
+\begin_inset CommandInset bibitem
+LatexCommand bibitem
+key "CDGPU2006"
+
+\end_inset
+
+Nathan Courni
+\begin_inset ERT
+status collapsed
+
+\begin_layout Plain Layout
+
+
+\backslash
+newblock
+\end_layout
+
+\end_inset
+
+
+\emph on
+Chessboard Domination on Programmable Graphics Hardware
+\emph default
+
+\begin_inset ERT
+status collapsed
+
+\begin_layout Plain Layout
+
+
+\backslash
+newblock
+\end_layout
+
+\end_inset
+
+ 
+\emph on
+ACM SE'06 March 10-Â­12, 2006
+\emph default
+.
+ Melbourne, Florida, USA
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+beamertemplatearticlebibitems
+\end_layout
+
+\end_inset
+
+
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+Followed by interesting articles.
+ Keep the list short.
+ 
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_body
+\end_document
Index: liacs/SCA2010/presentation1/presentation-paper-rvdzwet.nav
===================================================================
--- liacs/SCA2010/presentation1/presentation-paper-rvdzwet.nav	(revision 124)
+++ liacs/SCA2010/presentation1/presentation-paper-rvdzwet.nav	(revision 124)
@@ -0,0 +1,65 @@
+\beamer@endinputifotherversion {3.07pt}
+\headcommand {\slideentry {0}{0}{1}{1/1}{}{0}}
+\headcommand {\beamer@framepages {1}{1}}
+\headcommand {\slideentry {0}{0}{2}{2/2}{}{0}}
+\headcommand {\beamer@framepages {2}{2}}
+\headcommand {\sectionentry {1}{Minimum domination set}{3}{Minimum domination set}{0}}
+\headcommand {\beamer@sectionpages {1}{2}}
+\headcommand {\beamer@subsectionpages {1}{2}}
+\headcommand {\beamer@subsectionentry {0}{1}{1}{3}{Domination set}}\headcommand {\beamer@subsectionpages {3}{2}}
+\headcommand {\slideentry {1}{1}{1}{3/3}{Domination set}{0}}
+\headcommand {\beamer@framepages {3}{3}}
+\headcommand {\slideentry {1}{1}{2}{4/4}{Domination set}{0}}
+\headcommand {\beamer@framepages {4}{4}}
+\headcommand {\beamer@subsectionentry {0}{1}{2}{5}{GPU Inner Workings}}\headcommand {\beamer@subsectionpages {3}{4}}
+\headcommand {\slideentry {1}{2}{1}{5/5}{GPU Inner Workings}{0}}
+\headcommand {\beamer@framepages {5}{5}}
+\headcommand {\slideentry {1}{2}{2}{6/6}{GPU Inner Workings}{0}}
+\headcommand {\beamer@framepages {6}{6}}
+\headcommand {\sectionentry {2}{Algoritm}{7}{Algoritm}{0}}
+\headcommand {\beamer@sectionpages {3}{6}}
+\headcommand {\beamer@subsectionpages {5}{6}}
+\headcommand {\slideentry {2}{0}{3}{7/7}{}{0}}
+\headcommand {\beamer@framepages {7}{7}}
+\headcommand {\beamer@subsectionentry {0}{2}{1}{8}{Computing the piece configuration}}\headcommand {\beamer@subsectionpages {7}{7}}
+\headcommand {\slideentry {2}{1}{1}{8/8}{Computing the piece configuration}{0}}
+\headcommand {\beamer@framepages {8}{8}}
+\headcommand {\beamer@subsectionentry {0}{2}{2}{9}{Rendered in Framebuffer}}\headcommand {\beamer@subsectionpages {8}{8}}
+\headcommand {\beamer@subsectionentry {0}{2}{3}{9}{Determine Domination (e.g. Mark solution)}}\headcommand {\beamer@subsectionpages {9}{8}}
+\headcommand {\sectionentry {3}{GPU Optimalizations}{9}{GPU Optimalizations}{0}}
+\headcommand {\beamer@sectionpages {7}{8}}
+\headcommand {\beamer@subsectionpages {9}{8}}
+\headcommand {\slideentry {3}{0}{1}{9/9}{}{0}}
+\headcommand {\beamer@framepages {9}{9}}
+\headcommand {\slideentry {3}{0}{2}{11/11}{}{0}}
+\headcommand {\beamer@framepages {11}{11}}
+\headcommand {\sectionentry {4}{Results}{12}{Results}{0}}
+\headcommand {\beamer@sectionpages {9}{11}}
+\headcommand {\beamer@subsectionpages {9}{11}}
+\headcommand {\beamer@subsectionentry {0}{4}{1}{12}{Main Results}}\headcommand {\beamer@subsectionpages {12}{11}}
+\headcommand {\slideentry {4}{1}{1}{12/12}{Main Results}{0}}
+\headcommand {\beamer@framepages {12}{12}}
+\headcommand {\slideentry {4}{1}{2}{13/13}{Main Results}{0}}
+\headcommand {\beamer@framepages {13}{13}}
+\headcommand {\beamer@subsectionentry {0}{4}{2}{14}{Discussion}}\headcommand {\beamer@subsectionpages {12}{13}}
+\headcommand {\slideentry {4}{2}{1}{14/14}{Discussion}{0}}
+\headcommand {\beamer@framepages {14}{14}}
+\headcommand {\sectionentry {5}{Summary}{15}{Summary}{0}}
+\headcommand {\beamer@sectionpages {12}{14}}
+\headcommand {\beamer@subsectionpages {14}{14}}
+\headcommand {\slideentry {5}{0}{2}{15/15}{}{0}}
+\headcommand {\beamer@framepages {15}{15}}
+\headcommand {\partentry {Appendix}{1}}
+\headcommand {\beamer@partpages {1}{15}}
+\headcommand {\beamer@sectionpages {15}{15}}
+\headcommand {\beamer@subsectionpages {15}{15}}
+\headcommand {\beamer@appendixpages {16}}
+\headcommand {\sectionentry {6}{Appendix}{16}{Appendix}{1}}
+\headcommand {\beamer@sectionpages {16}{15}}
+\headcommand {\beamer@subsectionpages {16}{15}}
+\headcommand {\beamer@subsectionentry {1}{6}{1}{16}{For Further Reading}}\headcommand {\beamer@subsectionpages {16}{15}}
+\headcommand {\beamer@partpages {16}{16}}
+\headcommand {\beamer@subsectionpages {16}{16}}
+\headcommand {\beamer@sectionpages {16}{16}}
+\headcommand {\beamer@documentpages {16}}
+\headcommand {\def \inserttotalframenumber {14}}
Index: liacs/SCA2010/presentation1/presentation-paper-rvdzwet.out
===================================================================
--- liacs/SCA2010/presentation1/presentation-paper-rvdzwet.out	(revision 124)
+++ liacs/SCA2010/presentation1/presentation-paper-rvdzwet.out	(revision 124)
@@ -0,0 +1,15 @@
+\BOOKMARK [2][]{Outline0.1}{Minimum domination set}{}
+\BOOKMARK [3][]{Outline0.1.1.3}{Domination set}{Outline0.1}
+\BOOKMARK [3][]{Outline0.1.2.5}{GPU Inner Workings}{Outline0.1}
+\BOOKMARK [2][]{Outline0.2}{Algoritm}{}
+\BOOKMARK [3][]{Outline0.2.1.8}{Computing the piece configuration}{Outline0.2}
+\BOOKMARK [3][]{Outline0.2.2.9}{Rendered in Framebuffer}{Outline0.2}
+\BOOKMARK [3][]{Outline0.2.3.9}{Determine Domination \(e.g. Mark solution\)}{Outline0.2}
+\BOOKMARK [2][]{Outline0.3}{GPU Optimalizations}{}
+\BOOKMARK [2][]{Outline0.4}{Results}{}
+\BOOKMARK [3][]{Outline0.4.1.12}{Main Results}{Outline0.4}
+\BOOKMARK [3][]{Outline0.4.2.14}{Discussion}{Outline0.4}
+\BOOKMARK [2][]{Outline0.5}{Summary}{}
+\BOOKMARK [1][]{Outline1}{Appendix}{}
+\BOOKMARK [2][]{Outline1.6}{Appendix}{Outline1}
+\BOOKMARK [3][]{Outline1.6.1.16}{For Further Reading}{Outline1.6}
Index: liacs/SCA2010/presentation1/presentation-paper-rvdzwet.tex
===================================================================
--- liacs/SCA2010/presentation1/presentation-paper-rvdzwet.tex	(revision 124)
+++ liacs/SCA2010/presentation1/presentation-paper-rvdzwet.tex	(revision 124)
@@ -0,0 +1,286 @@
+%% 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}
Index: liacs/SCA2010/presentation1/presentation-paper-rvdzwet.toc
===================================================================
--- liacs/SCA2010/presentation1/presentation-paper-rvdzwet.toc	(revision 124)
+++ liacs/SCA2010/presentation1/presentation-paper-rvdzwet.toc	(revision 124)
@@ -0,0 +1,14 @@
+\beamer@endinputifotherversion {3.07pt}
+\select@language {english}
+\beamer@sectionintoc {1}{Minimum domination set}{3}{0}{1}
+\beamer@subsectionintoc {1}{1}{Domination set}{3}{0}{1}
+\beamer@subsectionintoc {1}{2}{GPU Inner Workings}{5}{0}{1}
+\beamer@sectionintoc {2}{Algoritm}{7}{0}{2}
+\beamer@subsectionintoc {2}{1}{Computing the piece configuration}{8}{0}{2}
+\beamer@subsectionintoc {2}{2}{Rendered in Framebuffer}{9}{0}{2}
+\beamer@subsectionintoc {2}{3}{Determine Domination (e.g. Mark solution)}{9}{0}{2}
+\beamer@sectionintoc {3}{GPU Optimalizations}{9}{0}{3}
+\beamer@sectionintoc {4}{Results}{12}{0}{4}
+\beamer@subsectionintoc {4}{1}{Main Results}{12}{0}{4}
+\beamer@subsectionintoc {4}{2}{Discussion}{14}{0}{4}
+\beamer@subsectionintoc {6}{1}{For Further Reading}{16}{1}{4}
