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 LEE D 101.
Recitation sessions take place Thursdays 13:15 -- 15:00 in LEE D 101 and take place when announced. Some of the lecture 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 |
|---|---|---|
| 0 | 09/19: no lecture | 09/22: MPI Tutorial (white bg) |
| 1 | 09/26: Organization - Introduction (1pp) (6pp) | 09/29: Projects - Advanced MPI Tutorial |
| 2 | 10/03: Cache Coherence & Memory Models (1pp) (6pp) | 10/06: Cache Organization - Introduction to OpenMP |
| 3 | 10/10: Memory Models (1pp) (6pp) | 10/13: Sequential Consistency + OpenMP Synchronization |
| 4 | 10/17: Linearizability (1pp) (6pp) | 10/20: Linearizability |
| 5 | 10/24: Languages and Locks (1pp) (6pp) | 10/27: Locks |
| 6 | 10/31: Amdahl's Law (1pp) (6pp) - Notes | 11/03: Amdahl's Law |
| 7 | 11/07: Project presentations | 11/10: No recitation session |
| 8 | 11/14: Roofline Model (1pp) (6pp) - Notes | 11/17: Roofline Model |
| 9 | 11/21: Balance Principles (1pp) (6pp) - Notes on Balance Principles / Scheduling (1pp) (6pp) - Nodes on Scheduling | 11/24: Balance Priciples & Scheduling |
| 10 | 11/28: Locks and Lock-Free (1pp) (6pp) | 12/01: SPIN Tutorial |
| 11 | 12/05: Lock-Free and distributed memory (1pp) (6pp) | 12/08: Benchmarking - (paper) |
| 12 | 12/12: Guest lecture - Dr. Tobias Grosser | 12/15: Network Models |
| 13 | 12/19: Final Presentations |
Assignments are an important part of the course. You will not learn this material from listening to a lecture alone -- you have to 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 | Assignment 1 (last slide) | Parallel Pi with MPI | Solution |
| 2 | Assignment 2 | Cache Organization / Cache Coherence | Solution Benchmark |
| 3 | Assignment 3 | Sequential Consistency | Solution |
| 4 | Assignment 4 | Linearizability | Solution |
| 5 | Assignment 5 | Locks | Solution |
| 6 | Assignment 6 | Roofline & Balance Principles | Solution |
| 7 | Assignment 7 (last two slides) | SPIN | Solution |
| Number | Members | Project Description | Final Presentation |
|---|---|---|---|
| 1 | Niklas Hofmann, Razvan Damachi, Stefan Irimescu | Parallel k-shortest paths | |
| 2 | Maximilian Wurm, Sabir Akhadov, Madelin Schumacher | Cloud Task Scheduling with Parallel ACO | |
| 3 | Renggli Cédric, Christoph Heiniger | Sparse Vector Reduction | |
| 4 | Blum Sonja, Bamert Mauro, Wolf Felix, Rauchenstein Felix | Connected Components | |
| 5 | Andreas Zingg, Marc Fischer, Bozhidara Ivanova | Parallel Convex Hull | |
| 6 | Stefano Weidmann, Philip Müller, Manuel Rodriguez | Maximum Flow | |
| 7 | Lukas Drescher, Anton Permenev | Causal Graph Learning | |
| 8 | Marek Červák, Lorenzo Martini, Aleksander Matusiak | Parallel Convex Hull | |
| 9 | Nika Mansourighiasi, Lu Chen, Andrea Solo | Approximate String Matching | |
| 10 | Conradin Roffler, Isabelle Roesch, Samuel Ueltschi, Thomas Meier | Maximum Cardinality Matching | |
| 11 | Cedric Münger, Yannick Schaffner, Stephan Zehnder | Delaunay Triangulation | |
| 12 | Margomenos Spyridon, Peter Güttinger | First Reaction Method | |
| 13 | Rosenthal Jonathan, Jonas Kuratli, Jonathan Maurer | Design of a Parallel Chess Engine |
50% of your grade is determined by the project, and the other 50% of the grade is determined by a written 2 hr exam. You are not allowed to use any electronic devices or books, notes, etc. to the exam.