#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 . \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 \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