This repository will be used as the website for Parallelism and Concurrency CS-206. It will be updated weekly throughout the semester. This README contains general information about the class.
- previous-exams contains PDFs for the previous exams.
- exercises contains markdown documents for exercises and solutions.
- slides contains the slides presented in class.
- labs contains markdown documents for the labs.
We will use GitLab's issue tracker as a discussion forum. Feel free to open an issue if you have any comments or questions.
First-week tasks
- Join the Discord
- Log into gitlab: https://gitlab.epfl.ch/users/sign_in
- Please fill in this table with your GASPAR and SCIPER number
- Choose the group for the exercises
- This will initialize your GitLab repository for the course
- Follow the Tools Setup page.
- Do the example lab.
- Watch all videos under Parallelism 1: Introduction to Parallel Programming below
- Do the first graded lab.
Grading
The grading of the course is divided between exercies (5%), labs (25%), midterm exam (30%) and final exam (40%).
Staff
| Role | People |
|---|---|
| Professors | Martin Odersky, Viktor Kunčak |
| TAs | Aleksander Boruch-Gruszecki, Dragana Milovancevic, Guillaume Martres, Nicolas Stucki, Olivier Blanvillain |
| Student TAs | Antoine Masanet, Lucas Giordano, Kajetan Pyszkowski, Marco Vögeli, Quentin Guignard, Sara Djambazovska |
Course Schedule
Lectures are partially live (on Zoom) and partially prerecorded (on YouTube). Live sessions will be held on Wednesdays from 14:15 to 16:00. Weekly Discord sessions will be held on Wednesdays from 14:15 to 16:00 for exercises (if it is a week with exercises) and 16:15 to 18:00 for labs. You should watch the prerecorded lectures before doing the exercies. In the first week of the semester, there will be a live Zoom session on Wednesday at 14:15 to welcome you to the class and answer questions you might have, followed by a Discord session.
| Week | Date | Topic | Lectures (14:15-16:00) | Exercises (14:15-16:00) | Labs (16:15-18:00) |
|---|---|---|---|---|---|
| 1 | 24.02.21 | Parallelism 1 | Prerecorded | Welcome Zoom session | Lab 1 |
| 2 | 03.03.21 | Parallelism 2 | Prerecorded | Exercise 1 | Lab 1 & 2 |
| 3 | 10.03.21 | Parallelism 3 | Prerecorded | Exercise 2 | Lab 2 & 3 |
| 4 | 17.03.21 | Parallelism 4 | Prerecorded | Exercise 3 | Lab 3 & 4 |
| 5 | 24.03.21 | Concurrency 1 | Live | Lab 4 & 5 | |
| 6 | 31.03.21 | Concurrency 2 | Live | Lab 5 & 6 | |
| 7 | 07.04.21 | Easter | |||
| 8 | 14.04.21 | Midterm Exam | |||
| 9 | 21.04.21 | Concurrency 3 | Live | Lab 6 | |
| 10 | 28.04.21 | Actors 1 | Prerecorded | Exercise 4 | Lab 7 |
| 11 | 05.05.21 | Actors 2 | Prerecorded | Exercise 5 | Lab 7 |
| 12 | 12.05.21 | Spark 1 | Prerecorded | Exercise 6 | Lab 8 |
| 13 | 19.05.21 | Spark 2 | Prerecorded | Exercise 7 | Lab 8 & 9 |
| 14 | 26.05.21 | Spark 3 | Prerecorded | Exercise 8 | Lab 9 |
| 15 | 02.06.21 | Review for Final Exam |
Solutions to the exercises are released after each deadline. We do not provide solutions for the labs.
Before each Discord session, students should watch videos corresponding to that week's topic:
Intro
Parallelism 1: Introduction to Parallel Programming
- Introduction to Parallel Computing
- Parallelism on the JVM I
- Parallelism on the JVM II
- Running Computations in Parallel
- Monte Carlo Method to Estimate Pi
- First-Class Tasks
- How Fast are Parallel Programs?
- Benchmarking Parallel Programs
Parallelism 2: Basic Task Parallel Algorithms
- Parallel Sorting
- Data Operations and Parallel Mapping
- Parallel Fold (Reduce) Operation
- Associativity I
- Associativity II
- Parallel Scan (Prefix Sum) Operation
Parallelism 3: Data-Parallelism
- Data-Parallel Programming
- Data-Parallel Operations I
- Data-Parallel Operations II
- Scala Parallel Operations
- Splitters and Combiners
Parallelism 4: Data-Structures for Parallel Computing
- Implementing Combiners
- Parallel Two-phase Construction
- Conc-Tree Data Structure
- Amortized, Constant-Time Append Operation
- Conc-Tree Combiners
Concurrency 1, 2 & 3
- Live lectures
- Concurrency 1 (Zoom Recording) (YouTube version)
- Concurrency 2 (Zoom Recording) (YouTube version)
- Concurrency 3 (Zoom Recording) (YouTube version)
Actors 1
Actors 2
Spark 1: Spark Basics
- From Parallel to Distributed
- Latency
- RDDs, Spark's Distributed Collection
- RDDs: Transformations and Actions
- Evaluation in Spark: Unlike Scala Collections!
- Cluster Topology Matters
Spark 2: Reduction Operations & Distributed Key-Value Pairs
Spark 3: Partitioning and Shuffling
- Shuffling: What it is and Why it's important
- Partitioning
- Optimizing with Partitioners
- Wide vs Narrow Dependencies
Labs
Labs are individual assignments where you get to write Scala programs using the concepts learned during lectures. Labs are submitted by pushing your code on GitLab, see details in the grading and submission page.
| Labs | Name | Start date | Due date (23:59 AoE) |
|---|---|---|---|
| Lab 1 | Parallel Box Blur Filter | 24.02.21 | 07.03.2021 |
| Lab 2 | Reductions and Prefix Sums | 01.03.21 | 14.03.2021 |
| Lab 3 | K-Means | 08.03.21 | 21.03.2021 |
| Lab 4 | Barnes-Hut Simulation | 15.03.21 | 28.03.2021 |
| Lab 5 | Bounded Buffer | 22.03.21 | 04.04.2021 |
| Lab 6 | Lock-free Sorted List | 29.03.21 | 25.04.2021 |
| Lab 7 | Actors Binary Tree | 26.04.21 | 09.05.2021 |
| Lab 8 | Wikipedia | 10.05.21 | 23.05.2021 |
| Lab 9 | StackOverflow | 17.05.21 | 30.05.2021 |
Exercises
Exercises are pen and paper style questions that will help you consolidate the knowledge learned during lectures. Exercises should be done in groups and submitted on GitLab. You should form groups of up to five students for each exercise, solve the exercise remotely with your group (using Discord, Hangouts, Zoom, ...), and write your solutions in a text file. The first line of your solution file should list all the group members' SCIPER numbers. After you solve the exercise with your group, each member should submit a copy of this file to their GitLab repository following the instructions given in the problem statement. Exercises will be given a participation grade at the end of the semester, which accounts for 5% of the overall course grade.
| Exercises | Start date | Due date (23:59 AoE) |
|---|---|---|
| Exercise 1 | 01.03.2021 | 07.03.2021 |
| Exercise 2 | 08.03.2021 | 14.03.2021 |
| Exercise 3 | 15.03.2021 | 21.03.2021 |
| Exercise 4 | 26.04.2021 | 02.05.2021 |
| Exercise 5 | 03.05.2021 | 09.05.2021 |
| Exercise 6 | 10.05.2021 | 16.05.2021 |
| Exercise 7 | 17.05.2021 | 23.05.2021 |
| Exercise 8 | 24.05.2021 | 30.05.2021 |
Exams
The midterm exam will take place on 14.04.21. The midterm exam will cover all the material seen in the class up to week 6 (included).
The final exam will take place on 02.06.21. The final exam for our course, parallelism and concurrency has been scheduled for Saturday July 10th from 8.15 to 11.15 in rooms SG1, AAC137, CO1 and CE6. The final exam will cover all material seen during the semester.
Information about exams organization will be communicated by email.