Basic Information

News

Course overview

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.

Course schedule

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.

Tentative schedule of lectures

Week Monday Thursday
0 09/14: no lecture due to Knabenschiessen 09/17: MPI Tutorial
1 09/21: Organization (6up) and Introduction (6 up) 09/25: Projects / Advanced MPI Tutorial
2 09/28: Cache Coherence (6up) 10/01: Cache Organization / Cache Coherence
3 10/05: Memory Models (6up) 10/08: Sequential Consistency
4 10/12: Linearizability (6up) 10/15: Linearizability
5 10/19: Languages and Locks (6up) 10/22: Languages and Locks
6 10/26: Locks and Lock Free (6up) 10/29: Locks and Lock Free Algorithms, Locks in C
7 11/02: Project Presentations 11/05: Sequential Consistency
8 11/06: Amdahls Law (6up) Notes 11/09: Amdahls Law (Solutions)
9 11/16: Roofline Model (6up), Balance Principles 11/19: Roofline and Balance Principles
10 11/23: Locks and Lock-free contd. (6up) 11/26: SPIN Tutorial
11 11/30: Lock-Free and distributed memory (6up), Benchmarking (paper, slides) 12/03: Consensus number proofs
12 12/07: LogGP model (6up) 12/03: Communication Cost Models
13 12/14: Final Presentations

Mailinglist

If you want to discuss issues related to the class, please subscribe to the class mailinglist. 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.

Assignments

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 SPIN (see last slides for assignment) SPIN Solution

Teams

Number Members Project Description Final Presentation
1 Wallimann Kevin, Baum Johannes, Untergassmair Matthias Topological Sorting
2 Alessandro De Palma, Lukas Gianinazzi, Pavel Kalvoda Mincut using Karger-Stein
3 Dario Bösch, Lukas Kuster, Roger Koradi Parallel Priority Queue
4 Marcel Schneider, Theodoros Theodoridis, Baranidharan Mohan Parallel BFS
5 Tijana Zivic, Benjamin Weber iVertex Coloring
6 Balz Guenat, Amirreza Bahreini, Christopher Signer Parallel Gumtree
7 Serge Balzan, Tobias Kaiser, Stefan Dietiker XML Processing
8 Simon Frasch, Eric Sinner, Till Ehrengruber Hoshen-Kopelman Algorithm
9 Prabhakaran Santhanam, Johannes de Fine Licht, Fabian Wermelinger kd-Tree
10 Adrian Spurr, Viktor Wegmayr, Dominik Kovacs Brain MRF modelling
11 Daniele Palossi, Simon Pintarelli, Marija Kranjcevic Single Source Shortest Paths
12 Patrick Schwarz, Raphael Grob, David Schmidig Connected Components
13 Phillippe Zindel, Marc Zuest Maximum Flow

Template for project report

Grading

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.

Resources

To implement your project you can utilize our Xeon Phi server. A single-page tutorial om how to run OpenMP programs on it can be found here. There exist a large number of books on programming multi-processors, multi-core system, or threads. These books may explore some topics in more depth than the lectures, or may provide background information. None of these books is mandatory. Copies of the first two books are "on reserve" the CS library.

Excursion to Lugano (February 15, 2016)