source: liacs/SCA2010/presentation1/presentation-paper-rvdzwet.lyx@ 240

Last change on this file since 240 was 124, checked in by Rick van der Zwet, 14 years ago

Presentation about GPU nQueens paper
  • Property svn:executable set to *
File size: 16.0 KB
RevLine 
[124]1#LyX 1.6.5 created this file. For more info see http://www.lyx.org/
2\lyxformat 345
3\begin_document
4\begin_header
5\textclass beamer
6\begin_preamble
7\usetheme{Warsaw}
8% or ...
9
10\setbeamercovered{transparent}
11% or whatever (possibly just delete it)
12\end_preamble
13\use_default_options false
14\language english
15\inputencoding auto
16\font_roman times
17\font_sans default
18\font_typewriter default
19\font_default_family default
20\font_sc false
21\font_osf false
22\font_sf_scale 100
23\font_tt_scale 100
24
25\graphics default
26\paperfontsize default
27\spacing single
28\use_hyperref false
29\papersize default
30\use_geometry false
31\use_amsmath 2
32\use_esint 0
33\cite_engine basic
34\use_bibtopic false
35\paperorientation portrait
36\secnumdepth 2
37\tocdepth 2
38\paragraph_separation indent
39\defskip medskip
40\quotes_language english
41\papercolumns 1
42\papersides 1
43\paperpagestyle default
44\tracking_changes false
45\output_changes false
46\author ""
47\author ""
48\end_header
49
50\begin_body
51
52\begin_layout Standard
53\begin_inset Note Note
54status open
55
56\begin_layout Plain Layout
57This file is a solution template for:
58\end_layout
59
60\begin_layout Itemize
61Talk at a conference/colloquium.
62
63\end_layout
64
65\begin_layout Itemize
66Talk length is about 20min.
67
68\end_layout
69
70\begin_layout Itemize
71Style is ornate.
72\end_layout
73
74\end_inset
75
76
77\end_layout
78
79\begin_layout Standard
80\begin_inset Note Note
81status collapsed
82
83\begin_layout Plain Layout
84Copyright 2004 by Till Tan tau <tantau@users.sourceforge.net>.
85
86\end_layout
87
88\begin_layout Plain Layout
89In principle, this file can be redistributed and/or modified under the terms
90 of the GNU Public License, version 2.
91 However, this file is supposed to be a template to be modified for your
92 own needs.
93 For this reason, if you use this file as a template and not specifically
94 distribute it as part of a another package/program, the author grants the
95 extra permission to freely copy and modify this file as you see fit and
96 even to delete this copyright notice.
97
98\end_layout
99
100\end_inset
101
102
103\end_layout
104
105\begin_layout Title
106Chessboard Domination on Programmable Graphics Hardware [CDGPU2006]
107\begin_inset OptArg
108status open
109
110\begin_layout Plain Layout
111Chessboard Domination on GPU
112\begin_inset Note Note
113status collapsed
114
115\begin_layout Plain Layout
116optional, use only with long paper titles
117\end_layout
118
119\end_inset
120
121
122\end_layout
123
124\end_inset
125
126
127\end_layout
128
129\begin_layout Subtitle
130\begin_inset Quotes eld
131\end_inset
132
133First algorithm to determine the minimum domination number of a chessboard
134 graph using the GPU
135\begin_inset Quotes erd
136\end_inset
137
138
139\end_layout
140
141\begin_layout Author
142Rick van der Zwet
143\begin_inset Note Note
144status collapsed
145
146\begin_layout Itemize
147Give the names in the same order as the appear in the paper.
148
149\end_layout
150
151\begin_layout Itemize
152Use the
153\begin_inset Quotes eld
154\end_inset
155
156Institute mark
157\begin_inset Quotes erd
158\end_inset
159
160 inset (
161\family sans
162Insert\SpecialChar \menuseparator
163Custom Insets\SpecialChar \menuseparator
164InstituteMark
165\family default
166) only if the authors have different affiliations.
167\end_layout
168
169\end_inset
170
171
172\begin_inset OptArg
173status open
174
175\begin_layout Plain Layout
176Rick van der Zwet <hvdzwet@liacs.nl>
177\begin_inset Note Note
178status collapsed
179
180\begin_layout Plain Layout
181- optional, use only with lots of authors
182\end_layout
183
184\begin_layout Plain Layout
185- if there are really lots of authors, use
186\begin_inset Quotes eld
187\end_inset
188
189Author ET al.
190\begin_inset Quotes erd
191\end_inset
192
193
194\end_layout
195
196\end_inset
197
198
199\end_layout
200
201\end_inset
202
203
204\end_layout
205
206\begin_layout Institute
207LIACS - Leiden University
208\end_layout
209
210\begin_layout Date
211Seminar Combinatorial Algorithms, 2010
212\begin_inset Note Note
213status collapsed
214
215\begin_layout Itemize
216Either use conference name or its abbreviation.
217
218\end_layout
219
220\begin_layout Itemize
221Not really informative to the audience, more for people (including yourself)
222 who are reading the slides online
223\end_layout
224
225\end_inset
226
227
228\begin_inset OptArg
229status open
230
231\begin_layout Plain Layout
232SCA2010
233\begin_inset Note Note
234status collapsed
235
236\begin_layout Plain Layout
237optional, should be abbreviation of conference name
238\end_layout
239
240\end_inset
241
242
243\end_layout
244
245\end_inset
246
247
248\end_layout
249
250\begin_layout Standard
251\begin_inset Note Note
252status open
253
254\begin_layout Plain Layout
255If you have a file called "institution-logo-filename.xxx", where xxx is a
256 graphic format that can be processed by latex or pdflatex, resp., then you
257 can add a logo by uncommenting the following:
258\end_layout
259
260\end_inset
261
262
263\end_layout
264
265\begin_layout Standard
266\begin_inset ERT
267status open
268
269\begin_layout Plain Layout
270
271
272\backslash
273pgfdeclareimage[height=0.5cm]{institution-logo}{institution-logo-filename}
274\end_layout
275
276\begin_layout Plain Layout
277
278\end_layout
279
280\begin_layout Plain Layout
281
282
283\backslash
284logo{
285\backslash
286pgfuseimage{institution-logo}}
287\end_layout
288
289\end_inset
290
291
292\end_layout
293
294\begin_layout Standard
295\begin_inset Note Note
296status open
297
298\begin_layout Plain Layout
299The following causes the table of contents to be shown at the beginning
300 of every subsection.
301 Delete this, if you do not want it.
302\end_layout
303
304\end_inset
305
306
307\end_layout
308
309\begin_layout Standard
310\begin_inset Note Note
311status open
312
313\begin_layout Plain Layout
314If you wish to uncover everything in a step-wise fashion, uncomment the
315 following command:
316\end_layout
317
318\end_inset
319
320
321\end_layout
322
323\begin_layout Standard
324\begin_inset ERT
325status open
326
327\begin_layout Plain Layout
328
329%
330\backslash
331beamerdefaultoverlayspecification{<+->}
332\end_layout
333
334\end_inset
335
336
337\end_layout
338
339\begin_layout BeginFrame
340Outline
341\end_layout
342
343\begin_layout Standard
344\begin_inset CommandInset toc
345LatexCommand tableofcontents
346
347\end_inset
348
349
350\end_layout
351
352\begin_layout Standard
353\begin_inset Note Note
354status open
355
356\begin_layout Plain Layout
357Structuring a talk is a difficult task and the following structure may not
358 be suitable.
359 Here are some rules that apply for this solution:
360\end_layout
361
362\begin_layout Itemize
363Exactly two or three sections (other than the summary).
364
365\end_layout
366
367\begin_layout Itemize
368At *most* three subsections per section.
369
370\end_layout
371
372\begin_layout Itemize
373Talk about 30s to 2min per frame.
374 So there should be between about 15 and 30 frames, all told.
375\end_layout
376
377\begin_layout Itemize
378A conference audience is likely to know very little of what you are going
379 to talk about.
380 So *simplify*!
381\end_layout
382
383\begin_layout Itemize
384In a 20min talk, getting the main ideas across is hard enough.
385 Leave out details, even if it means being less precise than you think necessary.
386
387\end_layout
388
389\begin_layout Itemize
390If you omit details that are vital to the proof/implementation, just say
391 so once.
392 Everybody will be happy with that.
393
394\end_layout
395
396\end_inset
397
398
399\end_layout
400
401\begin_layout Section
402Minimum domination set
403\end_layout
404
405\begin_layout Subsection
406Domination set
407\begin_inset OptArg
408status open
409
410\begin_layout Plain Layout
411Domination set
412\end_layout
413
414\end_inset
415
416
417\end_layout
418
419\begin_layout BeginFrame
420Domination set
421\end_layout
422
423\begin_layout FrameSubtitle
424Capture them all
425\begin_inset Note Note
426status open
427
428\begin_layout Plain Layout
429A title should summarize the slide in an understandable fashion for anyone
430 how does not follow everything on the slide itself.
431
432\end_layout
433
434\end_inset
435
436
437\end_layout
438
439\begin_layout Itemize
440Use the least amount of items to cover a whole board
441\end_layout
442
443\begin_layout Itemize
444Item based characteristics made whole set
445\end_layout
446
447\begin_layout BeginFrame
448Queen lower bound
449\end_layout
450
451\begin_layout Itemize
452\begin_inset Formula $y(Q_{n})\geq\frac{n-1}{2}$
453\end_inset
454
455,
456\begin_inset Formula $n\geq1$
457\end_inset
458
459
460\begin_inset CommandInset citation
461LatexCommand cite
462key "DM2003"
463
464\end_inset
465
466
467\end_layout
468
469\begin_layout Itemize
470Every square either contains a queen, or can be reached by a queen (e.g.
471 least amount of pieces required)
472\end_layout
473
474\begin_layout Itemize
475\begin_inset Graphics
476 filename pasted1.emf
477 scale 99
478
479\end_inset
480
481
482\end_layout
483
484\begin_layout Subsection
485GPU Inner Workings
486\end_layout
487
488\begin_layout BeginFrame
489Board Layout
490\end_layout
491
492\begin_layout Itemize
493
494\emph on
495streams:
496\emph default
497 pipelines available on the GPU - a collection of records requiring similar
498 computation.
499\end_layout
500
501\begin_layout Itemize
502
503\emph on
504kernel:
505\emph default
506 function that is applied to each element of a stream.
507\end_layout
508
509\begin_layout Standard
510In the GPU streaming model, textures, geometry, and the framebuffer are
511 seen as streams while vertex and fragment programs are seen as kernels.
512\end_layout
513
514\begin_layout BeginFrame
515Outlined Figure
516\end_layout
517
518\begin_layout Standard
519\begin_inset Graphics
520 filename C:/Documents and Settings/rvdzwet/Desktop/liacs/SCA2010/presentation1/pasted1.png
521 scale 99
522
523\end_inset
524
525
526\end_layout
527
528\begin_layout Section
529Algoritm
530\end_layout
531
532\begin_layout BeginFrame
533Basic Algoritm
534\end_layout
535
536\begin_layout Standard
537
538\family typewriter
53901: finished=false
540\end_layout
541
542\begin_layout Standard
543
544\family typewriter
54502: do
546\end_layout
547
548\begin_layout Standard
549
550\family typewriter
55103: ..computes a piece configuration which may be a minimally dominating set
552
553\end_layout
554
555\begin_layout Standard
556
557\family typewriter
55804: ..Rendered in the framebuffer
559\end_layout
560
561\begin_layout Standard
562
563\family typewriter
56405: ..if (All pixels are marked)
565\end_layout
566
567\begin_layout Standard
568
569\family typewriter
57006: ....finished=true
571\end_layout
572
573\begin_layout Standard
574
575\family typewriter
57607: ..fi
577\end_layout
578
579\begin_layout Standard
580
581\family typewriter
58208: while (finished=false)
583\end_layout
584
585\begin_layout Subsection
586Computing the piece configuration
587\end_layout
588
589\begin_layout BeginFrame
590Method
591\end_layout
592
593\begin_layout Itemize
594Exhaustive manner
595\end_layout
596
597\begin_layout Itemize
598Piece configuration stored on the CPU as linked links
599\end_layout
600
601\begin_layout Itemize
602Lower bound and Upper bound is respected
603\end_layout
604
605\begin_layout Subsection
606Rendered in Framebuffer
607\end_layout
608
609\begin_layout Itemize
610GPU supports textures, every piece is a texture
611\end_layout
612
613\begin_layout Itemize
614Render points on the CPU and offload to the GPU to map texture on specific
615 place
616\end_layout
617
618\begin_layout Standard
619\begin_inset Graphics
620 filename C:/Documents and Settings/rvdzwet/Desktop/liacs/SCA2010/presentation1/pasted4.emf
621 scale 99
622
623\end_inset
624
625
626\end_layout
627
628\begin_layout Subsection
629Determine Domination (e.g.
630 Mark solution)
631\end_layout
632
633\begin_layout Itemize
634Simple approch
635\end_layout
636
637\begin_layout Itemize
638Sum all pixels of
639\begin_inset Formula $n*n$
640\end_inset
641
642 board and match if
643\begin_inset Formula $sum=n*n$
644\end_inset
645
646
647\end_layout
648
649\begin_layout Section
650GPU Optimalizations
651\end_layout
652
653\begin_layout BeginFrame
654Colour Channels
655\end_layout
656
657\begin_layout Standard
658\begin_inset Graphics
659 filename C:/Documents and Settings/rvdzwet/Desktop/liacs/SCA2010/presentation1/pasted5.emf
660 scale 99
661
662\end_inset
663
664
665\end_layout
666
667\begin_layout Itemize
668GPU is able to process all colours at the times
669\end_layout
670
671\begin_layout BeginFrame
672Grid Framebuffer
673\end_layout
674
675\begin_layout Itemize
676GPU has many CPU's called kernels
677\end_layout
678
679\begin_layout Itemize
680Each kernel can process it's own little block of information
681\end_layout
682
683\begin_layout Itemize
684Putting multiple possible solutions in one bloc
685\end_layout
686
687\begin_layout Section
688Results
689\end_layout
690
691\begin_layout Subsection
692Main Results
693\end_layout
694
695\begin_layout BeginFrame
696Conclusions and Future Work
697\end_layout
698
699\begin_layout Standard
700\begin_inset Float figure
701wide false
702sideways false
703status open
704
705\begin_layout Plain Layout
706
707\end_layout
708
709\begin_layout Plain Layout
710\begin_inset Caption
711
712\begin_layout Plain Layout
713\begin_inset Graphics
714 filename pasted6.emf
715 scale 99
716
717\end_inset
718
719
720\end_layout
721
722\end_inset
723
724
725\end_layout
726
727\begin_layout Plain Layout
728Execution times (log scale) of CPU and GPU based minimum domination implementati
729ons computing
730\begin_inset Formula $y(Q_{n})$
731\end_inset
732
733.
734 As
735\begin_inset Formula $n$
736\end_inset
737
738 increases, the GPU's speed advantage over the CPU become more evident.
739\end_layout
740
741\end_inset
742
743
744\end_layout
745
746\begin_layout BeginFrame
747Conclusions and Future Work [2]
748\end_layout
749
750\begin_layout Itemize
751Domination texture good mapping between CPU world and GPU world
752\end_layout
753
754\begin_layout Itemize
755Flexible texture definition without any impact
756\end_layout
757
758\begin_layout Subsection
759Discussion
760\end_layout
761
762\begin_layout BeginFrame
763Discussion
764\end_layout
765
766\begin_layout Itemize
767No significant speedup, claim that
768\begin_inset Formula $n\geq13$
769\end_inset
770
771 GPU is
772\emph on
773'much'
774\emph default
775faster
776\end_layout
777
778\begin_layout Itemize
779No scaleable
780\end_layout
781
782\begin_layout Section*
783Summary
784\end_layout
785
786\begin_layout BeginFrame
787Summary
788\end_layout
789
790\begin_layout Itemize
791First GPU algoritm for solving minimum domination described at the time
792\end_layout
793
794\begin_layout Itemize
795Using texture mapping to build bridges between the CPU world and GPU world
796\end_layout
797
798\begin_layout Standard
799\begin_inset Note Note
800status open
801
802\begin_layout Plain Layout
803An outlook is always optional.
804\end_layout
805
806\end_inset
807
808
809\end_layout
810
811\begin_layout Standard
812\begin_inset ERT
813status collapsed
814
815\begin_layout Plain Layout
816
817
818\backslash
819vskip0pt plus.5fill
820\end_layout
821
822\end_inset
823
824
825\end_layout
826
827\begin_layout Itemize
828Outlook
829\end_layout
830
831\begin_deeper
832\begin_layout Itemize
833Make it scale so its decision algoritms is much smarter
834\end_layout
835
836\begin_layout Itemize
837Build a framework to allow easy and proper testing for various combinations
838\end_layout
839
840\end_deeper
841\begin_layout EndFrame
842
843\end_layout
844
845\begin_layout Section*
846\start_of_appendix
847\begin_inset Note Note
848status open
849
850\begin_layout Plain Layout
851All of the following is optional and typically not needed.
852\end_layout
853
854\end_inset
855
856Appendix
857\end_layout
858
859\begin_layout Subsection*
860For Further Reading
861\end_layout
862
863\begin_layout BeginFrame
864For Further Reading
865\end_layout
866
867\begin_layout Standard
868\begin_inset ERT
869status collapsed
870
871\begin_layout Plain Layout
872
873
874\backslash
875beamertemplatebookbibitems
876\end_layout
877
878\end_inset
879
880
881\begin_inset Note Note
882status open
883
884\begin_layout Plain Layout
885Start with overview books.
886\end_layout
887
888\end_inset
889
890
891\end_layout
892
893\begin_layout Bibliography
894\begin_inset CommandInset bibitem
895LatexCommand bibitem
896key "DM2003"
897
898\end_inset
899
900E.
901 J.
902 Cockayne
903\begin_inset ERT
904status collapsed
905
906\begin_layout Plain Layout
907
908
909\backslash
910newblock
911\end_layout
912
913\end_inset
914
915
916\emph on
917Chessboard domination problems
918\emph default
919
920\begin_inset ERT
921status collapsed
922
923\begin_layout Plain Layout
924
925
926\backslash
927newblock
928\end_layout
929
930\end_inset
931
932
933\emph on
934Discrete Math
935\emph default
936., 86:1320, 1990.
937\end_layout
938
939\begin_layout Bibliography
940\begin_inset CommandInset bibitem
941LatexCommand bibitem
942key "CDGPU2006"
943
944\end_inset
945
946Nathan Courni
947\begin_inset ERT
948status collapsed
949
950\begin_layout Plain Layout
951
952
953\backslash
954newblock
955\end_layout
956
957\end_inset
958
959
960\emph on
961Chessboard Domination on Programmable Graphics Hardware
962\emph default
963
964\begin_inset ERT
965status collapsed
966
967\begin_layout Plain Layout
968
969
970\backslash
971newblock
972\end_layout
973
974\end_inset
975
976
977\emph on
978ACM SE'06 March 10-­12, 2006
979\emph default
980.
981 Melbourne, Florida, USA
982\begin_inset ERT
983status open
984
985\begin_layout Plain Layout
986
987
988\backslash
989beamertemplatearticlebibitems
990\end_layout
991
992\end_inset
993
994
995\begin_inset Note Note
996status open
997
998\begin_layout Plain Layout
999Followed by interesting articles.
1000 Keep the list short.
1001
1002\end_layout
1003
1004\end_inset
1005
1006
1007\end_layout
1008
1009\end_body
1010\end_document
Note: See TracBrowser for help on using the repository browser.