This course exposes students to the principal issues involved in software development for parallel computing and discusses a number of approaches to handle the problems and opportunities caused by the increased availability of parallel platforms.
The course includes lectures, assignments, self-study, and a project. 50% of your grade is determined by project work and 50% is determined by a written exam; the exam is given during the official examination period, and there is no makeup exam. Students must be able to program using Java and C/C++.
The course may cover: memory coherence and consistency models, implications for language-specific memory models, Java memory model, models of parallel programming and parallel program execution, performance models for parallel systems, transactional memory, compiler extraction of parallelism, language and compiler support for parallel programming, threads and their execution environment, synchronization, and implementation issues of these topics.
Lectures are given Mondays 13:15 - 16:00 in CAB G 61.
Recitation sessions take place Thursdays 13:15 -- 15:00 in LEE D 101 and ETZ E 9. Some of the recitation session hours will be devoted to other activities (tutorials, reviews, etc) or will be devoted to group meetings. Please watch this page for updates and announcements.
| Week | Monday | Thursday |
|---|---|---|
| 1 | 09/16: no lecture | 09/19: no recitation |
| 2 | 09/23: Introduction, Organization, Cache Refresher | 09/27: Caches |
| 3 | 09/30: Cache Coherency | 10/03: Cache Coherence Protocols Recap |
| 4 | 10/07: MPI Tutorial | 10/10: Advanced MPI Tutorial |
| 5 | 10/14: Memory Models | 10/17: Cluster Usage, Memory Models, Sequential Consistency |
| 6 | 10/21: Languages and Locks | 10/24: Locks, SPIN tutorial |
| 7 | 10/28: Fast Locks, Lock-Free, Consensus (Unrolled Animations) | 10/31: Wait-Free, Plotting |
| 8 | 11/04: Modelling | 11/07: Performance modelling |
| 9 | 11/11: Scalable Locks and Oblivious Algorithms | 11/14: Prefix scan, Research opportunities for students |
| 9 | 11/18: Balance Principles, Roofline Models, Scheduling, Modelling (contd.) | 11/21: Balance Principles, Scheduling |
| 10 | 11/26: SIMD | 11/28: Balance Principles, SIMD |
| 11 | 12/02: Neural network training (unrolled animations) | 12/05: Quiz |
| 12 | 12/09: Communication Models | 12/05: Network models |
If you want to discuss issues related to the class or ask questions, please subscribe to the class mailing list dphpc-2019. This list is read by the instructors as well as the TA, and any student of the class who voluntarily subscribed to it. So it is a great place to discuss questions about homework or the lecture slides.
We have a second mailing list dphpc-forum-2019 for the purpose of finding projects project teams, where all students are subscribed initially. We will remove you from this list, once we received an email about your team. See explanation below in the project section.
Assignments are an important part of the course. You will not learn this material from listening to a lecture alone and should do the assignments.
Note: Do not hesitate to write an email to your TA if you have trouble with the assignments!
| Number | Assignment | Description | Solution |
|---|---|---|---|
| 1 | Cache Benchmark | Determine the cache sizes of your computer by timing some operation. | |
| 2 | Parallel PI | See last slide of the first recitation session. PI-seq: download | download |
| 3 | SPIN models | See last slide of the recitation session | Assignment solution |
| 4 | Performance modeling | Assignment 4 | Assignment solution |
| Name | |
|---|---|
| Salvatore Di Girolamo | salvatore.digirolamo@inf.ethz.ch |
| Tal Ben-Nun | tal.bennun@inf.ethz.ch |
| Marcin Copik | marcin.copik@inf.ethz.ch |
| Maciej Besta | maciej.besta@inf.ethz.ch |
| Timo Schneider | timos@inf.ethz.ch |
| Number | Supervisor | Members | Project Description | Final Presentation |
|---|---|---|---|---|
| 1 | Marcin | Joshua Sammet, Marco Messerli, Leonard Knirsch, Alexander Morgenroth | Comparison of different parallel graph colouring algorithms in their performance exposed to different kinds of graph networks. | |
| 2 | Salvatore | Aurelio Dolfini, Marc Wanner, Dominik Helmreich and Jan Stratmann | Ant Colony Optimisation Algorithms | |
| 3 | Nobody | Lea Fritschi, Roman Haag, Michael Bernasconi, Giovanni Balduzzi | nothing submitted | |
| 4 | Tal | Isidor Schoch, Felix Illes, Konrad Handrick, Theo Smertnig | Graph Clustering via Maximum Flow | |
| 5 | Maciej | Peter Tatkowski, Sebastian Leisinger, Esref Özdemir, Tobias Holenstein | Subgraph Isomorphism | |
| 6 | Tal | Robin Vogtland, Roger Barton, Sebastian Balzer, Thomas Baumann | Fringe Search | |
| 7 | Timo | Maxime Raafat, Amélie Loher, Daria Lipsky, Angelina Heusler | Delaunay Triangulation | |
| 8 | Tal | Rich Harpur, Matthias Busenhart, Damian Heer, Manuel Winkler | Parallel Finite Element Method (FEM) | |
| 9 | Marcin | Daniel Stalder, Lukas Joss, Yannick Niedermayr, Fabrice Dal Farra | Parallel Minimal Spanning Tree Algorithms | |
| 10 | Salvatore | Mathias Born, Wouter Tonnon, Maren Wessel-Berg, Luca Beurer-Kellner | A Dynamically Load-Balanced Parallel Implementation of a Cellular Automata | |
| 11 | Tal | Sebastian Kurella, Justin MacPherson, Hannes Pfammatter, Valentin Anklin | Distribution and Parallelization of a Genetic Algorithm | |
| 12 | Marcin | Davide Staub, Lennart Espe, Berkay Berabi, Daniel Widmer | Vertex Coloring | |
| 13 | Tal | Samuel Martin, Josefine Leuenberger, Xiaohe Niu, Alice Mazzoleni | BFS | |
| 14 | Maciej | Ajaykumar Unagar, Chia-I Hu, Kenza Amara, Philipp Lindenberger | Subgraph Isomorphism | |
| 15 | Timo | Kosta Stojiljkovic, Han Yao Choong, Langwen Huang, Benjamin Langer | Parallelization of popular genome sequencing algorithms | |
| 16 | Maciej | Dimitrios Lekkas, Athina Sotiropoulou, Foteini Strati, Andreas Triantafyllos | Community Detection in Massive Networks | |
| 17 | Salvatore | Fabian Schuiki, Malte Brodmann, Samuel Riedel | Artificial Bee Colony Optimization | |
| 18 | Timo | Sandro Panighetti, Philippe Mazenauer, Vyacheslav Samokhvalov, Jonas Hansen | Parallel Push-Relabel | |
| 19 | Maciej | Hamilton Carrillo, Paulina Aguirre Fernandez de Hirt, Claudio Cannizzaro | Shortest Paths | |
| 20 | Marcin | Wei Qiu, Run Shen, Jinfan Chen | Markov chain Monte Carlo and Variational Inference OR Minimum Spanning Trees | |
| 21 | Salvatore | Tianjian Jiang, Flowers Macro, Singh Shashank | Parallel B+-Tree | |
| 22 | Maciej | Baumgartner Roger, Kistler Severin, Peter Emanuel, Senn Alain | Graph Coloring |
50% of your grade is determined by the project, and the other 50% of the grade is determined by a written 2 hr exam (Example Exam). You are not allowed to use any electronic devices or books, notes, etc. in the exam.