Difference between revisions of "Algorithms of Scientific Computing II - Winter 11"
(33 intermediate revisions by 3 users not shown) | |||
Line 2: | Line 2: | ||
| term = Winter 11/12 | | term = Winter 11/12 | ||
| lecturer = [[Michael Bader|Prof. Dr. Michael Bader]] | | lecturer = [[Michael Bader|Prof. Dr. Michael Bader]] | ||
− | | timeplace = Lecture: Wednesday, 10: | + | | timeplace = Lecture: Wednesday, 10:30 - 12:00 Uhr, room MI 02.07.023, started Oct 26 |
− | :Tutorial: Monday, 16:00 -18:00, every second week, room MI 02.07.023 | + | :Tutorial: Monday, 16:00 -18:00, every second week, room MI 02.07.023, started Nov 7 |
| credits = 3 SWS (2V + 1Ü) / 4 Credits | | credits = 3 SWS (2V + 1Ü) / 4 Credits | ||
| audience =Elective topic in Informatik Bachelor/Master/Diplom subject area ''Algorithms and Scientific Computing'' | | audience =Elective topic in Informatik Bachelor/Master/Diplom subject area ''Algorithms and Scientific Computing'' | ||
Line 14: | Line 14: | ||
= <font color=red>News </font>= | = <font color=red>News </font>= | ||
+ | * In winter term 2011/12, this lecture will be held by [[Michael Bader]] with a focus on algorithms in high performance computing (and scientific computing). | ||
+ | * The lecture on Wednesday, Nov 2, was skipped due to the student's general assembly | ||
− | |||
<!-- | <!-- | ||
* <font color=black>Next tutorial on 07.02.2010.</font> | * <font color=black>Next tutorial on 07.02.2010.</font> | ||
Line 24: | Line 25: | ||
= Content = | = 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''). | ||
− | = | + | = Lecture Material = |
− | + | Lecture slides will be published here after the lessons: | |
− | + | * Oct 26: [http://www5.in.tum.de/lehre/vorlesungen/algowiss2/WS11/intro.pdf Intro] | |
− | + | * Oct 26, Nov 9: [http://www5.in.tum.de/lehre/vorlesungen/algowiss2/WS11/fundamentals.pdf Fundamentals - Parallel Architectures, Models, and Languages] | |
− | * [http://www5.in.tum.de/lehre/vorlesungen/ | + | * Nov 16, Nov 23: Dwarf no. 1 - [http://www5.in.tum.de/lehre/vorlesungen/algowiss2/WS11/denseLA.pdf Dense Linear Algebra]; |
− | * [http://www5.in.tum.de/lehre/vorlesungen/ | + | ** additional material: [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] |
− | * [http://www5.in.tum.de/lehre/vorlesungen/ | + | * Nov 30: Dwarf no. 5 - [http://www5.in.tum.de/lehre/vorlesungen/algowiss2/WS11/structured.pdf Structured Grids] |
− | * [http://www5.in.tum.de/lehre/vorlesungen/ | + | * Dec 7, Dec 14: [http://www5.in.tum.de/lehre/vorlesungen/algowiss2/WS11/sfc.pdf Structured Grids and Space-filling Curves] |
− | + | ** Maple worksheets: [http://www5.in.tum.de/lehre/vorlesungen/algowiss2/WS11/hilbert_adap.mws hilbert_adap.mws] (also as [http://www5.in.tum.de/lehre/vorlesungen/algowiss2/WS11/hilbert_adap.pdf PDF]); | |
+ | ** additional material: [http://www.springerlink.com/content/827mu1k516p87m47/ article by Frigo/Strumpen: The memory behavior of cache oblivious stencil computations] | ||
+ | * Dec 14, Dec 21: Dwarf no. 6 - [http://www5.in.tum.de/lehre/vorlesungen/algowiss2/WS11/unstructured.pdf Unstructured Grids and Partitioning] | ||
+ | ** additional material: [http://epubs.siam.org/sisc/resource/1/sjoce3/v20/i1/p359_s1 article by Karypis/Kumar: A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs ] | ||
+ | * Jan 11: Dwarf no. 2 - [http://www5.in.tum.de/lehre/vorlesungen/algowiss2/WS11/sparseLA.pdf Sparse Linear Algebra]: Application example (page rank) and data structures | ||
+ | * Jan 18, Jan 25: 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]) | ||
+ | * Feb 1: Dwarf no. 4: [http://www5.in.tum.de/lehre/vorlesungen/algowiss2/WS11/moldyn.pdf N-body methods] and [http://www5.in.tum.de/lehre/vorlesungen/algowiss2/WS11/moldyn_impl.pdf implementation] | ||
+ | = Tutorials = | ||
+ | Roughly every second week a two hour tutorial will take place (details at page top; days and time will be announced here and in the lectures). The assignments and their solutions will be gradually posted here. | ||
+ | {| class="wikitable" | ||
+ | |- | ||
+ | |'''Date'''|| '''Slides''' || '''Files''' | ||
+ | |- | ||
+ | |07.11.2011 || [http://www5.in.tum.de/lehre/vorlesungen/algowiss2/WS11/Tutorial/tutorial_01.pdf Slides - Introduction to Cuda] || [http://www5.in.tum.de/lehre/vorlesungen/algowiss2/WS11/CUDA/cuda_mmult.cu cuda_mmult.cu], [http://www5.in.tum.de/lehre/vorlesungen/algowiss2/WS11/CUDA/README-1.txt README-1.txt] | ||
+ | |- | ||
+ | |21.11.2011 || [http://www5.in.tum.de/lehre/vorlesungen/algowiss2/WS11/Tutorial/tutorial_02.pdf Slides - Further Details on Dense Linear Algebra]|| | ||
+ | |- | ||
+ | |05.12.2011 || [http://www5.in.tum.de/lehre/vorlesungen/algowiss2/WS11/Tutorial/tutorial_03.pdf Slides - Shallow Water Equation]; [http://www5.in.tum.de/lehre/vorlesungen/algowiss2/WS11/Tutorial/tutorial_03_worksheet.pdf Worksheet] || [http://www5.in.tum.de/lehre/vorlesungen/algowiss2/WS11/SWE/swe_cuda_bathy_frame.tar Code framework] | ||
+ | |- | ||
+ | |23.01.2012 || [http://www5.in.tum.de/lehre/vorlesungen/algowiss2/WS11/SpMV/tutorial_04/tutorial_04.pdf Slides - SpMV Kernels & Worksheet] || [http://www5.in.tum.de/lehre/vorlesungen/algowiss2/WS11/SpMV/SpMV.tar.gz Code framework] | ||
+ | |- | ||
+ | |} | ||
− | = | + | = Literature = |
− | + | * R. H. Bisseling: Parallel Scientific Computing - A structured approach using BSP and MPI, Oxford University Press, 2004. | |
<!-- | <!-- | ||
Line 66: | Line 95: | ||
= Prerequisites = | = Prerequisites = | ||
− | Lecture ''IN0019 Numerical Programming'' or similar basic knowledge in numerical methods. | + | Lecture ''IN0019 Numerical Programming'' or similar basic knowledge in numerical methods. Basic knowledge in parallel programming (lecture ''Parallel Programming'', ''Parallele Algorithmen und Höchstleistungsrechnen'', or similar) is helpful (as is a certain interest in problems from scientific computing and numerical simulation). |
+ | |||
[[Category:Teaching]] | [[Category:Teaching]] |
Latest revision as of 11:28, 1 February 2012
- Term
- Winter 11/12
- Lecturer
- Prof. Dr. Michael Bader
- Time and Place
- Lecture: Wednesday, 10:30 - 12:00 Uhr, room MI 02.07.023, started Oct 26
- Tutorial: Monday, 16:00 -18:00, every second week, room MI 02.07.023, started Nov 7
- Audience
- Elective topic in Informatik Bachelor/Master/Diplom subject area Algorithms and Scientific Computing
- Wirtschaftsinformatik Bachelor (Modul IN2002)
- Mathematik, Natur- und Ingenieurwissenschaften students are also welcome!
- Tutorials
- Daniel Butnaru, M.Sc, Christoph Kowitz, M.Sc.
- Exam
- details t.b.a.
- Semesterwochenstunden / ECTS Credits
- 3 SWS (2V + 1Ü) / 4 Credits
- TUMonline
- {{{tumonline}}}
News
- In winter term 2011/12, this lecture will be held by Michael Bader with a focus on algorithms in high performance computing (and scientific computing).
- The lecture on Wednesday, Nov 2, was skipped due to the student's general assembly
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).
Lecture Material
Lecture slides will be published here after the lessons:
- Oct 26: Intro
- Oct 26, Nov 9: Fundamentals - Parallel Architectures, Models, and Languages
- Nov 16, Nov 23: Dwarf no. 1 - Dense Linear Algebra;
- additional material: article by Elmroth et al. in SIAM Review
- Nov 30: Dwarf no. 5 - Structured Grids
- Dec 7, Dec 14: Structured Grids and Space-filling Curves
- Maple worksheets: hilbert_adap.mws (also as PDF);
- additional material: article by Frigo/Strumpen: The memory behavior of cache oblivious stencil computations
- Dec 14, Dec 21: Dwarf no. 6 - Unstructured Grids and Partitioning
- Jan 11: Dwarf no. 2 - Sparse Linear Algebra: Application example (page rank) and data structures
- Jan 18, Jan 25: Parallel Sparse Matrix-Vector Multiplication
- lecture material accompanying the book by R. Bisseling (see esp. the slides psc4_3.pdf, psc4_4.pdf, psc4_5.pdf, and psc4_6.pdf)
- Feb 1: Dwarf no. 4: N-body methods and implementation
Tutorials
Roughly every second week a two hour tutorial will take place (details at page top; days and time will be announced here and in the lectures). The assignments and their solutions will be gradually posted here.
Date | Slides | Files |
07.11.2011 | Slides - Introduction to Cuda | cuda_mmult.cu, README-1.txt |
21.11.2011 | Slides - Further Details on Dense Linear Algebra | |
05.12.2011 | Slides - Shallow Water Equation; Worksheet | Code framework |
23.01.2012 | Slides - SpMV Kernels & Worksheet | Code framework |
Literature
- R. H. Bisseling: Parallel Scientific Computing - A structured approach using BSP and MPI, Oxford University Press, 2004.
Prerequisites
Lecture IN0019 Numerical Programming or similar basic knowledge in numerical methods. Basic knowledge in parallel programming (lecture Parallel Programming, Parallele Algorithmen und Höchstleistungsrechnen, or similar) is helpful (as is a certain interest in problems from scientific computing and numerical simulation).