Difference between revisions of "HPC - Algorithms and Applications - Winter 13"

From Sccswiki
Jump to navigation Jump to search
m
 
(47 intermediate revisions by 2 users not shown)
Line 2: Line 2:
 
| term = Winter 13/14
 
| term = Winter 13/14
 
| lecturer = [[Michael Bader|Prof. Dr. Michael Bader]]
 
| lecturer = [[Michael Bader|Prof. Dr. Michael Bader]]
| timeplace = Lecture: Monday, 14.15-15.45, MI 02.07.023 (starts Oct 21); Tutorial: Wednesday, 10-12, MI 02.07.023 (starts Oct 23)
+
| timeplace = Lecture: Monday, 14.00-15.30, MI 02.07.023 (starts Oct 21);<br> Tutorial: Wednesday, 10-12, MI 02.07.023 (starts Oct 23, roughly bi-weekly)
 
| credits = 3 SWS (2V + 1Ü) / 4 ECTS
 
| credits = 3 SWS (2V + 1Ü) / 4 ECTS
 
| audience = Elective topic in Informatics Bachelor/Master: students in mathematics or in any science or engineering discipline are welcome!
 
| audience = Elective topic in Informatics Bachelor/Master: students in mathematics or in any science or engineering discipline are welcome!
| tutorials = [[Sebastian Rettenberger, M.Sc.]]
+
| tutorials = [[Oliver Meister]]
| exam = written or oral exam at end of semester <!-- Monday, Feb 4, 2013; 14-16 in room MI 02.07.023 (time and room of the lecture) - Review: Wednesday, March 27th/March 6th; 10am to 12am in LRZ Room E.2.040 -->
+
| exam = written exam, Wednesday, Feb 5, 2014; 10-12 in room MI 02.07.023 (time and room of the tutorial)<br>a repeat exam (oral) will be offered on April 2 and 3
 
| tumonline = https://campus.tum.de/tumonline/lv.detail?clvnr=950111465 (lecture)<br>https://campus.tum.de/tumonline/wbStpModHB.detailPage?&pKnotenNr=705979 (module description)
 
| tumonline = https://campus.tum.de/tumonline/lv.detail?clvnr=950111465 (lecture)<br>https://campus.tum.de/tumonline/wbStpModHB.detailPage?&pKnotenNr=705979 (module description)
 
}}
 
}}
 +
 +
= Annonuncements =
 +
* From Nov 18, the lecture on Monday will start at 14.00 (instead of 14.15)
  
 
= Content =
 
= Content =
Line 24: Line 27:
  
 
Slides and exercise sheets/solutions will be made available during the lecture.  
 
Slides and exercise sheets/solutions will be made available during the lecture.  
See the [[HPC - Algorithms and Applications - Winter 12|lecture from winter term 2012/13]] until then.
+
 
 +
Lecture slides will be published here after the lessons:
 +
See also the [[HPC - Algorithms and Applications - Winter 12|lecture from winter term 2012/13]].
 +
* Oct 21: [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/intro.pdf Intro]
 +
* Oct 21, Oct 28, Nov 4: [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/fundamentals.pdf Fundamentals - Parallel Architectures, Models, and Languages]
 +
** read the related paper: [http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-134.html Roofline: An Insightful Visual Performance Model for Floating-Point Programs and Multicore Architectures] (technical report by Williams et al.)
 +
** MPI examples: Cannon's Algorithm [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/mpi_cannon.c mpi_cannon.c] (unsafe send/receive), [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/mpi_cannon_sr.c mpi_cannon_sr.c] (using MPI_Sendrecv), [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/mpi_cannon_nbl.c mpi_cannon_nbl.c] (non-blocking communication)
 +
* Oct 28, Nov 4, Nov 11: Dwarf No. 1 - [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/denseLA.pdf Dense Linear Algebra];
 +
** read the related paper: [http://epubs.siam.org/sirev/resource/1/siread/v46/i1/p3_s1 article by Elmroth et al.] in [http://epubs.siam.org/sirev/ SIAM Review]
 +
** chapter [http://netlib.org/scalapack/slug/node74.html In-core dense matrices] of the [http://netlib.org/scalapack/slug/scalapack_slug.html ScaLAPACK User's Guide]
 +
* Nov 18: Dwarf no. 2 - [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/sparseLA.pdf Sparse Linear Algebra]: Application example (page rank) and data structures
 +
* Nov 25, Dec 2: Parallel Sparse Matrix-Vector Multiplication
 +
** [http://www.staff.science.uu.nl/~bisse101/Education/PA/pa.html lecture material] accompanying the book by R. Bisseling (see esp. the slides [http://www.staff.science.uu.nl/~bisse101/Book/PSC/psc4_3.pdf psc4_3.pdf], [http://www.staff.science.uu.nl/~bisse101/Book/PSC/psc4_4.pdf psc4_4.pdf], [http://www.staff.science.uu.nl/~bisse101/Book/PSC/psc4_5.pdf psc4_5.pdf], and [http://www.staff.science.uu.nl/~bisse101/Book/PSC/psc4_6.pdf psc4_6.pdf])
 +
* Dec 9, Dec 16: Dwarf No. 5 - [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/structured.pdf Structured Grids]
 +
** articles by M. Frigo and V. Strumpen:<br> [http://www.fftw.org/~athena/papers/ics05.pdf Cache oblivious stencil operations] (preprint);<br> [http://link.springer.com/article/10.1007%2Fs11227-007-0111-y The memory behavior of cache oblivious stencil operations] (preprint can be found via Google)
 +
** [http://epubs.siam.org/doi/abs/10.1137/070693199 article by K. Datta et al.]  in [http://epubs.siam.org/sirev/ SIAM Review] ([http://www.cs.berkeley.edu/~kdatta/pubs/sirev09_stencil.pdf preprint])
 +
* Dec 16, Dec 18: [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/sfc.pdf Structured Grids and Space-filling Curves] (will not be part of the exam) <!--, [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS12/solving_swe.pdf Solving the Shallow Water Equations]-->
 +
<!--
 +
** Maple worksheets: [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS12/hilbert_adap.mw hilbert_adap.mw] (also as [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS12/hilbert_adap.pdf PDF]);
 +
-->
 +
* Jan 13: Dwarf No. 6 - [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/unstructured.pdf Unstructured Grids and Partitioning]
 +
** additional material: [http://epubs.siam.org/sisc/resource/1/sjoce3/v20/i1/p359_s1 article by Karypis and Kumar: A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs]
 +
<!--
 +
* Dec 17: [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS12/sfc.pdf Partitioning and Space-filling Curves revisited]
 +
** Maple worksheets: [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS12/hilbert-arith-part.mw hilbert-arith-part.mw] (also as [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS12/hilbert-arith-part.pdf PDF]); [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS12/reftree_hilbert_vertexlab.mw reftree_hilbert_vertexlab.mw] (also as [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS12/reftree_hilbert_vertexlab.pdf PDF]);
 +
** related article by Mitchell: [http://www.sciencedirect.com/science/article/pii/S0743731506002309 journal article], [http://math.nist.gov/~WMitchell/papers/reftree.pdf preprint], [http://math.nist.gov/phaml/reftree.html webpage by W. Mitchell on reftree method]
 +
-->
 +
* Jan 20, Jan 27: Dwarf no. 4: [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/moldyn.pdf N-body methods] and [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/moldyn_impl.pdf implementation]
 +
** Maple worksheet: [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/twobody.mw twobody.mw] (also as [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/twobody.pdf PDF])
 +
** [http://epubs.siam.org/doi/abs/10.1137/0913055 article on Fast Multipole methods by C.R. Anderson]
 +
** [http://www.nature.com/nature/journal/v324/n6096/abs/324446a0.html article by Barnes &amp; Hut in Nature] (both articles can be accessed via TUM ebib-access)
 +
* Feb 3: "all questions answered" (exam preparation)
 +
 
 +
= Tutorials =
 +
Roughly every second week a two hour tutorial will take place (details at page top; days and time will be announced in TUMonline and in the lectures). The assignments and their solutions will be gradually posted here.
 +
 
 +
{| class="wikitable"
 +
|-
 +
| '''Date''' || '''Slides''' || '''Worksheet''' || '''Source''' || '''Source (solution)'''
 +
|-
 +
| Oct 23rd || [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/uebung/organization.pdf Organizational remarks] || - || - || -
 +
|-
 +
| Nov 6th || [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/uebung/cuda.pdf Introduction to CUDA] || [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/uebung/worksheet1.pdf Worksheet 1] || [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/uebung/Exercise1.zip Exercise 1] || [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/uebung/Solution1.zip Solution 1]
 +
|-
 +
| Nov 13th || [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/uebung/cuda_2.pdf Further details on Dense LA in CUDA] || [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/uebung/worksheet2.pdf Worksheet 2] || [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/uebung/Exercise2.zip Exercise 2] || [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/uebung/Solution2.zip Solution 2]
 +
|-
 +
| Nov 27th || [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/uebung/sparse_la_01.pdf Sparse LA in CUDA] || [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/uebung/worksheet3.pdf Worksheet 3] || [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/uebung/Exercise3.zip Exercise 3] || [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/uebung/Solution3.zip Solution 3]
 +
|-
 +
| Dec 11th || [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/uebung/sparse_la_02.pdf Solving the heat equation with CUDA] || [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/uebung/worksheet4.pdf Worksheet 4] || [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/uebung/Exercise4.zip Exercise 4] || [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/uebung/Solution4.zip Solution 4]
 +
|-
 +
| Jan 8th || [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/uebung/swe_01.pdf The Shallow Water Equations and CUDA] || [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/uebung/worksheet5.pdf Worksheet 5] || [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/uebung/Exercise5.zip Exercise 5] || [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/uebung/Solution5.zip Solution 5]
 +
|-
 +
| Jan 22nd || [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/uebung/swe_02.pdf Further topics on SWE and CUDA] || [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/uebung/worksheet6.pdf Worksheet 6] || - || -
 +
|}
 +
 
 +
= Exam =
 +
* '''Repeat Exam:''' will be scheduled as '''oral exam on April 2/3'''; the same rules as for the written exam will apply (esp. no helping material, questions on the tutorials)
 +
<!--
 +
* '''Exam review:''' you may view your corrected and graded exam on '''Thursday, Feb 13, 15.30''' (office of Prof. Bader, Leibniz Supercomputing Centre, room E.2.044)
 +
* written exam on Feb 5, 2014, from 10.15 (room MI 02.07.023)
 +
** please be in (front of) the lecture room in time (at 10.00); the exam will start on 10.15, at the latest, and there will be announcements before the start!
 +
-->
 +
* '''no helping material of any kind''' will be allowed for the exam
 +
* please make sure that you register for the exam in TUMonline
 +
* the exam will extend over all topics discussed in the lectures and tutorials:
 +
** approx. 30% of the questions will deal with questions related to the tutorials; basic knowledge about GPU programming with CUDA is thus necessary
 +
* The following topics will be excluded as topics of the exam:
 +
** module on [http://www5.in.tum.de/lehre/vorlesungen/hpc/WS13/sfc.pdf Structured Grids and Space-filling Curves]
 +
 
 +
<!--** the part on tree methods (Barnes-Hut and Fast Multipole algorithms) for N-body problems are excluded from the exam-->
  
 
= Literature and Online Material =
 
= Literature and Online Material =
Line 30: Line 102:
 
* R.H. Bisseling: [http://ukcatalogue.oup.com/product/9780198529392.do Parallel Scientific Computing - A structured approach using BSP and MPI], Oxford University Press, 2004.  
 
* R.H. Bisseling: [http://ukcatalogue.oup.com/product/9780198529392.do Parallel Scientific Computing - A structured approach using BSP and MPI], Oxford University Press, 2004.  
 
** [http://www.staff.science.uu.nl/~bisse101/Education/PA/pa.html Course notes on Rob Bisseling's lecture on Parallel Algorithms] (based on the text book)
 
** [http://www.staff.science.uu.nl/~bisse101/Education/PA/pa.html Course notes on Rob Bisseling's lecture on Parallel Algorithms] (based on the text book)
 +
* V. Eijkhout: [http://pages.tacc.utexas.edu/~eijkhout/istc/istc.html Introduction to High-Performance Scientific Computing] (textbook, available as PDF on the website)
 
* T.G. Mattson, B.A. Sanders, B.L. Massingill: [http://www.pearsonhighered.com/educator/product/Patterns-for-Parallel-Programming/9780321228116.page Patterns for Parallel Programming], Addison-Wesley, 2005
 
* T.G. Mattson, B.A. Sanders, B.L. Massingill: [http://www.pearsonhighered.com/educator/product/Patterns-for-Parallel-Programming/9780321228116.page Patterns for Parallel Programming], Addison-Wesley, 2005
 +
* G. Hager, G. Wellein: [http://www.crcpress.com/product/isbn/9781439811924 Introduction to High Performance Computing for Scientists and Engineers], Chapman & Hall/CRC Computational Science, 2010
 +
 +
== Books on CUDA ==
 
* D.B. Kirk, W.W. Hwu: [http://www.elsevierdirect.com/v2/companion.jsp?ISBN=9780123814722 Programming Massively Parallel Processors - A Hands-on Approach], Morgan-Kaufman, 2010
 
* D.B. Kirk, W.W. Hwu: [http://www.elsevierdirect.com/v2/companion.jsp?ISBN=9780123814722 Programming Massively Parallel Processors - A Hands-on Approach], Morgan-Kaufman, 2010
 
* J. Sanders, E. Kandrot: CUDA by Example, Addison-Wesley, 2011
 
* J. Sanders, E. Kandrot: CUDA by Example, Addison-Wesley, 2011

Latest revision as of 14:04, 27 October 2014

Term
Winter 13/14
Lecturer
Prof. Dr. Michael Bader
Time and Place
Lecture: Monday, 14.00-15.30, MI 02.07.023 (starts Oct 21);
Tutorial: Wednesday, 10-12, MI 02.07.023 (starts Oct 23, roughly bi-weekly)
Audience
Elective topic in Informatics Bachelor/Master: students in mathematics or in any science or engineering discipline are welcome!
Tutorials
Oliver Meister
Exam
written exam, Wednesday, Feb 5, 2014; 10-12 in room MI 02.07.023 (time and room of the tutorial)
a repeat exam (oral) will be offered on April 2 and 3
Semesterwochenstunden / ECTS Credits
3 SWS (2V + 1Ü) / 4 ECTS
TUMonline
https://campus.tum.de/tumonline/lv.detail?clvnr=950111465 (lecture)
https://campus.tum.de/tumonline/wbStpModHB.detailPage?&pKnotenNr=705979 (module description)



Annonuncements

  • From Nov 18, the lecture on Monday will start at 14.00 (instead of 14.15)

Content

The lecture will have a focus on parallel algorithms and implementation techniques in the field of numerical simulation and high performance computing, such as:

  • linear algebra problems on dense and sparse matrices
  • simulation on structured and unstructured meshes
  • particle-based simulations (with long-range and short-range interactions)
  • spectral methods (parallel FFT and related algorithms)
  • Monte Carlo and statistical methods

(a.k.a. the seven dwarfs of HPC).

The accompanying tutorials will include practical assignments, and will concentrate on the programming of GPU and accelerator platforms.

Lecture Material

Slides and exercise sheets/solutions will be made available during the lecture.

Lecture slides will be published here after the lessons: See also the lecture from winter term 2012/13.

Tutorials

Roughly every second week a two hour tutorial will take place (details at page top; days and time will be announced in TUMonline and in the lectures). The assignments and their solutions will be gradually posted here.

Date Slides Worksheet Source Source (solution)
Oct 23rd Organizational remarks - - -
Nov 6th Introduction to CUDA Worksheet 1 Exercise 1 Solution 1
Nov 13th Further details on Dense LA in CUDA Worksheet 2 Exercise 2 Solution 2
Nov 27th Sparse LA in CUDA Worksheet 3 Exercise 3 Solution 3
Dec 11th Solving the heat equation with CUDA Worksheet 4 Exercise 4 Solution 4
Jan 8th The Shallow Water Equations and CUDA Worksheet 5 Exercise 5 Solution 5
Jan 22nd Further topics on SWE and CUDA Worksheet 6 - -

Exam

  • Repeat Exam: will be scheduled as oral exam on April 2/3; the same rules as for the written exam will apply (esp. no helping material, questions on the tutorials)
  • no helping material of any kind will be allowed for the exam
  • please make sure that you register for the exam in TUMonline
  • the exam will extend over all topics discussed in the lectures and tutorials:
    • approx. 30% of the questions will deal with questions related to the tutorials; basic knowledge about GPU programming with CUDA is thus necessary
  • The following topics will be excluded as topics of the exam:


Literature and Online Material

Books on CUDA

Prerequisites

Helpful, but not strictly required is knowledge in:

  • basics of numerical methods (e.g.: lecture IN0019 Numerical Programming or similar)
  • basics of parallel programming (lecture Parallel Programming, HPC - Programming Paradigms and Scalability, or similar)

Most important is a certain interest in problems from scientific computing and numerical simulation!