Parallel Programming - FS '15

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 (e.g., GPUs) 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
  • Emerging parallel programming models (e.g., GPUs)
  • Case studies of building parallel programs starting from sequential algorithms

  • Overview

    eDoz Course Nr.
    252-0024-00L
    Lecturers
    Otmar Hilliges, Felix Friedrich
    Assistants
    Gerd Zellwegerzgerd+ethz+ch, Simon Gerbersimon.gerber+inf+ethz+ch, Moritz Hoffmannmoritzho+ethz+ch, Reto Achermannreto.achermann+inf+ethz+ch, Renato Marroquinrenato.marroquin+inf+ethz+ch, Dominik Honeggerdominik.honegger+inf+ethz+ch, Tobias Naegelitobias.naegeli+inf+ethz+ch, Stefan Kaestlestefan.kaestle+inf+ethz+ch, Jascha Grübeljgruebel+ethz+ch, Simon Peyerpeyers+ethz+ch, Dimitri Stanojevicstdimitr+ethz+ch, Lukas Vogelluvogel+ethz+ch
    Lecture
    Mon 10-12 HG E7,
    Tue 10-12 HG E7
    Exercise
    Mon 16-18 CAB G 52 and CHN D 44
    Thu 13-15 CAB G 57, CHN D 48, HG E 33.5, ML F 40, ML H 43 and NO E 11 NO E 39
    Fri 13-15 NO E 11 and NO E 39
    Office hours
    coordinate via e-mail: otmar.hilliges@inf.ethz.ch
    ECTS credits
    7 credits

    Announcements

    31.07.2015
    Errata and Remarks document available here
    07.05.2015
    Updated nqueens saveBoard() function in assignment11.zip so it is thread-safe.
    24.04.2015
    Updated SequentialList.java in assignment9.zip hand-out to clarify the assignment.
    24.04.2015
    Information about Midterm review added.
    13.04.2015
    Midterm grades published.
    30.03.2015
    PP-l13-LocksRaces_annotated.pdf uploaded which contains a clarification regarding Amdahl and Gustafson Law.
    26.03.2015
    Corrected Exercise numbers in assignment 6 slides.
    25.03.2015
    Midterm informations added.
    05.03.2015
    Exercise 3 hand-out updated with minor corrections.
    04.03.2015
    Exercise 3 is now online.
    25.02.2015
    Exercise 2 is now online.
    24.02.2015
    Slides of 23.03 updated with minor corrections for Slide 53 and 55.
    18.02.2015
    Exercise 1 is now online.
    11.02.2015
    Course Website for Spring 2015 online.

    Course Content

    Main text and reference book
  • Java Concurrency in Practice, 2006. Brian Goetz, Tim Peierls, Joshua Bloch, Joseph Bowbeer, David Holmes, Doug Lea. ISBN-13: 9780321349606
  • Introduction to Java Programming, 2014. Daniel Liang. ISBN-13: 9780133813463
  • 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.
  • OpenCL
  • OpenCL in Action, available via the ETH Library


  • Schedule

    Wk. Date Content Slides
    1 16.02.2015
    Course Introduction
    Slides
    1 17.02.2015
    Introduction to Programming
    Slides Slides (annotated) Code
    2 23.02.2015
    Java Basics I (Programming in the Small)
    Slides Slides (annotated) Code
    2 24.02.2015
    Java Basics II (Programming in the Large)
    Slides Slides (annotated) Code
    3 02.03.2015
    Java Basics III (Programming in the Large II)
    Slides Slides (annotated) Code
    3 03.03.2015
    Java Basics IV (Threads)
    Slides Slides (annotated) Code
    4 09.03.2015
    Parallel Architectures
    Slides Slides (annotated)
    4 10.03.2015
    Basic Parallelism Concepts
    Slides Slides (annotated)
    5 16.03.2015
    Parallel Models
    Slides Slides (annotated)
    5 17.03.2015
    Introduction to Task Parallelism
    Slides Code
    6 23.03.2015
    Task Parallelism in Java
    Slides Slides (annotated) Code
    6 24.03.2015
    Shared Memory Concurrency, Mutual exclusion, Locks
    Slides Slides (annotated)
    7 30.03.2015
    Synchronization: Locks and Data Races
    Slides Slides (annotated)
    7 31.03.2015
    !! Midterm Exam !!
    8 13.04.2015
    Synchronization: Beyond locks I
    Slides Slides (as presented) Code
    8 14.04.2015
    Synchronization: Beyond locks II
    Slides Slides (as presented) Code
    9 20.04.2015
    Synchronization: Behind Locks
    Slides Slides (as presented) Code
    9 21.04.2015
    Synchronization: Without Locks
    Slides Slides (as presented) Code
    10 27.04.2015
    A bit of Concurrency Theory
    Slides Slides (as presented)
    10 28.04.2015
    C sequential: from Java to C
    Slides Slides (as presented) Code
    11 04.05.2015
    C parallel: OpenMP
    Slides Slides (as presented) Code
    11 05.05.2015
    C parallel: OpenMP / MPI
    Slides Slides (as presented) Code
    12 11.05.2015
    MPI / Introduction to GPGPU Computing
    Slides Slides (as presented)
    12 12.05.2015
    Introduction to OpenCL
    Slides Slides (as presented) Code
    13 18.05.2015
    OpenCL: Memory Model and Synchronisation
    Slides Slides(as presented) Code
    13 19.05.2015
    OpenCL: Case Studies
    Slides Slides (as presented) Code
    14 26.05.2015
    Recap / Q&A Session
    Conclusion



    Exercises

    Exercise Assignment Due date
    Exercise 1 Handout Slides 25.02.2015
    Exercise 2 Handout Slides assignment2.zip solution2.zip 04.03.2015
    Exercise 3 Handout Slides assignment3.zip solution3.zip 11.03.2015
    Exercise 4 Handout Slides assignment4.zip threaddemo.zip Solution solution4.zip [new] 18.03.2015
    Exercise 5 Handout Slides Solution 25.03.2015
    Exercise 6 Handout assignment6.zip Slides [updated] Solution solution6.zip 01.04.2015
    Exercise 7 Handout assignment7.zip Solution [updated] solution7.zip 15.04.2015
    Exercise 8 Handout assignment8.zip Slides Solution solution8.zip 22.04.2015
    Exercise 9 Handout assignment9.zip [updated] Slides solution9.zip 29.04.2015
    Exercise 10 Handout assignment10.zip Slides solution10.zip 06.05.2015
    Exercise 11 Handout assignment11.zip Slides solution11.zip 13.05.2015
    Exercise 12 Handout assignment12.zip Slides solution12.zip 20.05.2015
    Exercise 13 Handout assignment13.zip solution13.zip 03.05.2015



    Exams and Grading

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

  • 80% of grade made-up from written exam
  • 20% of grade made-up from one Midterm exam

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

    Midterm Exam

    There will be one midterm on the 31.03.15. The midterm is during the lecture hours (10:15 − 12:00) and closed book. No additional material is allowed. The midterm will take place in three different rooms, please come directly to the correct room according to your last name.

    Midterm Material

    Relevant for the midterm are exercises 1 to (and including) 6 and the lectures from 16.02.2015 to (and including) 23.03.2015.

    Midterm Grades

    The grades are available here.

    Note that the midterm discussion will be part of the exercise sessions this week (16.4 - 20.4).

    Midterm Review

    You can review the midterm exam starting on the 28th of April every Tuesday and Wednesday from 2pm to 4pm until the end of the semester.