Parallel Programming - FS '16

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

  • Overview

    eDoz Course Nr.
    252-0024-00L
    Lecturers
    Otmar Hilliges, Felix Friedrich.
    Assistants
    Aristeidis Mastorasaristeidis.mastoras+inf+ethz+ch, Roni Häckironi.haecki+inf+ethz+ch, Tobias Nägelinaegelit+student+ethz+ch, Benjamin Heppbenjamin.hepp+inf+ethz+ch, Stefan Stevsicstefan.stevsic+inf+ethz+ch, Jie Songjsong+student+ethz+ch, Kaan Karakaan.kara+inf+ethz+ch, Mohsen Ewaidamohsen.ewaida+inf+ethz+ch, Renato Marroquinrenato.marroquin+inf+ethz+ch, Alexander Pilzalexander.pilz+inf+ethz+ch, Marc Fischermarcfisc+student+ethz+ch, Dimitri Stanojevicstdimitr+student+ethz+ch, Noah Hollmannnoahho+student+ethz+ch, Lukas Rahmannlrahmann+student+ethz+ch, Timon Blattnertimonbl+student+ethz+ch
    Lecture
    Mon 10-12: HG E 7,
    Tue 10-12: ETF E 1.
    Exercise
    Mon 16-18: CAB G 52, HG F 26.5, ML H 43, ML J 37.1, NO D 11 and NO E 11.
    Thu 13-15: CAB G 57, CHN D 46, CHN D 48, HG E 33.5, ML F 40, ML H 43, NO E 11 and NO E 39.
    Fri 13-15: ML J 34.1 and ML J 34.3.
    Office hours
    coordinate via e-mail: otmar.hilliges@inf.ethz.ch
    ECTS credits
    7 credits

    Announcements

    10.02.2016
    Course Website for Spring 2016 online.

    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.
  • 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.


  • Schedule

    Wk. Date Content Slides
    1 22.02.2016
    Course Introduction
    Slides Slides (annotated)
    1 23.02.2016
    Introduction to Programming
    Slides Slides (annotated) Code
    2 29.02.2016
    Java Basics
    Slides Slides (annotated) Code
    2 01.03.2016
    Java Basics
    Slides Code
    3 07.03.2016
    Object Orientated Programming
    Slides Slides (annotated) Code
    3 08.03.2016
    Java Multi-Threading
    Slides Slides (annotated) Code
    4 14.03.2016
    Parallel Architectures
    Slides Slides (annotated)
    4 15.03.2016
    Parallel Programming Concepts
    Slides Slides (annotated)
    5 21.03.2016
    Parallel Programming Models
    Slides Slides (annotated)
    5 22.03.2016
    Task Parallelism in Java
    Slides Code Utils
    6 28.03.2016
    Easter break
    No slides
    6 29.03.2016
    Easter break
    No slides
    7 04.04.2016
    Fork/Join Framework & Algorithms
    Slides Slides (annotated) Code
    7 05.04.2016
    Transition to Concurrency
    Slides Slides (annotated)
    8 11.04.2016
    Shared Memory Concurrency, Locks and Races
    Slides Slides (final) Code
    8 12.04.2016
    Midterm (Mock) Exam
    Midterm Solution
    9 18.04.2016
    Behind Locks: More about Data Races,
    Solving Mutual Exclusion with Atomic Registers
    Slides Slides (final) Code
    9 19.04.2016
    Behind Locks II: Mutual Exclusion for more than two processes,
    Hardware Primitives for mutual exclusion.
    Slides Slides (final) Code
    10 25.04.2016
    Beyond Locks: Deadlocks, Semaphores and Barriers
    Slides Slides (final) Code
    10 26.04.2016
    Beyond Locks II: Producer/Consumer, Monitors
    Slides Slides (final) Code
    11 02.05.2016
    Beyond Locks III: Readers/Writers, Lock Granularity
    Slides Slides (final) Code Flashcard
    11 03.05.2016
    Without Locks I: Lock-free programming
    Slides Slides (final) Code Flashcard Flashcard
    12 09.05.2016
    Without Locks II: Lock-free programming
    Slides Slides (final) Code Flashcard Flashcard
    12 10.05.2016
    Theory of Concurrency
    Slides Slides (final)
    13 16.05.2016
    --- Pfingstmontag ---
    13 17.5.2016
    Transactional Memory
    Slides Slides (final) Code Flashcard
    14 23.05.2016
    Parallel Algorithms
    Slides Slides (final) Flashcard
    14 24.5.2016
    Message Passing
    Slides Slides (final) Flashcard
    15 30.05.2016
    Message Passing ctd
    Slides Slides (final)
    15 31.5.2016
    Consensus and Conclusion
    Slides Slides (final) Flashcard



    Exercises

    Exercise Assignment Due date
    Exercise 1 Handout Slides 2.3.2016
    Exercise 2 Handout Code Slides Solution 9.3.2016
    Exercise 3 Handout Code Slides Solution 16.3.2016
    Exercise 4 Handout Code Code Examples Slides Solution Solution 23.3.2016
    Exercise 5 Handout Slides Solution 6.4.2016
    Exercise 6 Handout Slides Code Code Examples Solution 13.4.2016
    Exercise 7 Handout Slides Code Solution Solution 20.4.2016
    Exercise 8 Handout Slides Code Solution Solution 27.4.2016
    Exercise 9 Handout Slides Code Solution Solution 4.5.2016
    Exercise 10 Handout Slides Code Solution 11.5.2016
    Exercise 11 Handout Slides Code Solution Solution 18.5.2016
    Exercise 12 Handout Slides Code Solution 25.5.2016
    Exercise 13 Handout Slides Code Solution Solution 1.6.2016



    Exams and Grading

    Class is part of Basisprüfung. There is a written, centralized exam after the end of the semester.

  • 100% of grade made up from written exam

  • Exercise sessions are not graded, however they are considered essential!

    Mock Exam (12.04.2016)

    There will be one non-graded mock exam on the 12.04.2016. The mock exam is for you to practice and get a preview of what to expect in the Basisprüfung.

    Old exams

    BP_2014_Summer (English) BP_2014_Summer (German) (Solution)
    BP_2014_Winter (English) BP_2014_Winter (German) (Solution)
    BP_2015_Summer (Solution)
    BP_2015_Winter (Solution)
    BP_2016_Summer (Solution)
    BP_2017_Winter (Solution)