News
- 13.2.2019: Please select your preferred exercise group. Based on your preferences we will publish the group assignment on 19.2.
- 19.2.2019: Group assignment is online. As the space in each room is limited, please attend your assigned exercise group. If you are not in the list please contact Pavol Bielik
- 26.2.2019: Added supplementary material with Command Line Basics
Overview
The purpose of this course is to introduce students to parallel programming. By the end of the course students will be able to design and implement working parallel programs in traditional (e.g., Java Threads) and emerging parallel programming models. Moreover, students will master fundamental concepts in parallelism and be able to reason about the correctness, performance, and the construction of parallel programs using different parallel programming paradigms (e.g., task parallelism, data parallelism) and mechanisms (e.g., threads, tasks, locks, communication channels). Finally, the course will examine how parallel programming methodologies can be applied in different algorithmic domains by investigating parallelization of algorithms.
Topics include:
- Basic parallel programming concepts
- Parallel programming using Java
- Synchronization techniques
- Case studies of building parallel programs starting from sequential algorithms
Course Content
Main text and reference book
- Introduction to Java Programming, 2014. Daniel Liang. ISBN-13: 9780133813463
- Java Concurrency in Practice, 2006. Brian Goetz, Tim Peierls, Joshua Bloch, Joseph Bowbeer, David Holmes, Doug Lea. ISBN-13: 9780321349606
- The Art of Multiprocessor Programming, 2011. Maurice Herlihy, Nir Shavit. Morgan Kaufmann. Also available online in the ETH network.
Related resources, text and reference books
- Sophomoric Parallelism and Concurrency (from: spac)
- The Little Book of Semaphores
- Programming concurrency on the JVM, 2011. Venkat Subramaniam
- Structured Parallel Programming: Patterns for Efficient Computation, 2012. Michael McCool, Arch Robison, James Reinders.
- Patterns for Parallel Programming, 2004. Timothy G. Mattson, Beverly A. Sanders, Berna L. Massingill.
- A minicourse on multithreaded programming. Charles E. Leiserson, Harald Prokop.
- (Optional) Inside the Java Virtual Machine. 2000. Bill Venners.
Introduction to Java books (freely available)
- How to Think Like a Computer Scientist, 2012. Allen B. Downey.
- Introduction to Programming Using Java, 2011. David J. Eck.
Presentation Schedule
All course materials are password protected using your ETHZ credentials.
| Date | Title | Slides |
|---|---|---|
| Feb 19 | Introduction & Course Overview |
|
| Feb 20 | Java Recap and JVM Overview |
|
| Feb 26/27 | Introduction to Threads and Synchronization |
|
| Mar 5 | Introduction to Threads and Synchronization |
|
| Mar 6/12/13 | Parallel Architectures |
|
| Mar 19 | Basic Concepts in Parallelism |
|
| Mar 20 | Parallel Programming Models: Task and Data Parallelism |
|
| Mar 26/27 | ForkJoin Framework and Task Parallel Algorithms |
|
| Apr 2 | Shared Memory Concurrency, Locks and Data Races |
|
| Apr 9 | Data Races, Solving Mutual Exclusion with Atomic Registers |
|
| Apr 10 | Solving Mutual Exclusion for many processes, Hardware Primitives for mutual exclusion |
|
| Apr 16 | Spinlocks, Deadlocks, Semaphores |
|
| Apr 17 | Beyond Locks II: Semaphore, Barrier, Producer-Consumer, Monitors |
|
| Apr 30 | Readers/Writers Lock, Lock Granularity: Coarse Grained, Fine Grained, Optimal, and Lazy Synchronization |
|
| May 7 | Lock Tricks, Skip Lists, and Without Locks I |
|
| May 8 | Without Locks II |
|
| May 14 | Linearizability, Sequential Consistency, Consensus |
|
| May 15 | Sequential Consistency, Consensus and Transactional Memory |
|
| May 21 | Transactional Memory & Programming based on Message Passing |
|
| May 22 | Finish STM & Distributed Memory Programming: Actors, CSP, and MPI |
|
| May 28 | Message Passing & Parallel Sorting (A taste of parallel algorithms!) |
|
Exercises
Students should bring their laptops to the exercise sessions as most of the exercises involve programming.
| Week | Title | Due Date | Assignment | Slides | Solution |
|---|---|---|---|---|---|
| 1 | Introduction | - |  |
||
| 2 | Introduction to Multi-threading | 3.3.2019 |  |
|
|
| 3 | Multi-threading | 10.3.2019 | |
|
|
| 4 | Parallel Models | 17.3.2019 | |
|
|
| 5 | Divide and Conquer | 24.3.2019 | |
|
|
| 6 | Task Parallelism | 30.3.2019 | |
|
|
| 7 | Synchronization and Resource Sharing | 7.4.2019 | |
|
|
| 8 | Synchronization II | 14.4.2019 | |
|
|
| 9 | Beyond Locks | 28.4.2019 | |
|
|
| 10 | Advanced Synchronization Mechanisms | 13.5.2019 | |
|
|
| 11 | Advanced Synchronization Mechanisms | 20.5.2019 | |
|
|
| 12 | Consensus | 27.5.2019 | |
|
|
| 13 | Transactional Memory | 3.6.2019 | |
|
Supplementary Materials
| Title | Slides | |
|---|---|---|
| Command Line Basics |
|
Exams and Grading
There is a written, centralized exam after the end of the semester. Exercise sessions are not graded.
- 100% of grade determined by final Exam
Old Exams
2017 Summer Questions
2017 Winter Questions
2016 Summer Questions 2016 Summer Solution