COMP 322: Fundamentals of Parallel Programming (Spring
...
2020)
Instructor: | Mackale Joyner, DH 20712063 | Head TA: | Srdan Milakovic | Co-Instructor: | Zoran Budimlić, DH 3134 | Graduate TAs: | Jonathan SharmanCai (hw), Paul Jiang (lab 1pm), William Su (lab 4pm) |
|---|---|---|---|---|---|---|---|
| Admin Assistant: | Annepha Hurlock, annepha@rice.edu, DH 3122, 713-348-5186 | Undergraduate TAs: | Liam Bonnage, Harrison BrownKrishna Goel, Ryan Green, Ryan Han, Rishu Harpavat, Namanh Kapur, Tian Lan, Tam Le, Eva Ma, Hamza Nauman, Rutvik Patel, Aryan Sefidi,Tory Songyang, Jiaqi Wang, Erik Yamada, Yifan Yang Zishi Wang | ||||
Piazza site: | https://piazza.com/class/jmwfpr1i85n7l4configure-classes/spring2020/comp322 (Piazza is the preferred medium for all course communications, but you can also send email to comp322-staff at rice dot edu if needed) | Cross-listing: | ELEC 323 | ||||
Lecture location: | Herring Sewell Hall 100301 | Lecture times: | MWF 1:00pm - 1:50pm | ||||
Lab locations: | Herring Sewell Hall 100301 | Lab times: | Thursday, 4, 1:00pm - 1:50pm, 4:00pm - 4:50pm |
Course Syllabus
...
There are no required textbooks for the class. Instead, lecture handouts are provided for each module as follows. You are expected to read the relevant sections in each lecture handout before coming to the lecture. We will also provide a number of references in the slides and handouts.The links to the latest versions of the lecture handouts are included below:
- Module 1 handout (Parallelism)
- Module 2 handout (Concurrency)
- There is no lecture handout for Module 3 (Distribution and Locality). The instructors will refer you to optional resources to supplement the lecture slides and videos.
...
Lecture Schedule
Week | Day | Date (20182020) | Lecture | Assigned Reading | Assigned Videos (see Canvas site for video links) | In-class Worksheets | Slides | Work Assigned | Work Due1 | ||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | Mon | Jan 0713 | Lecture 1: Task Creation and Termination (Async, Finish) | Module 1: Section 1.1 | worksheet1 | lec1-slides |
|
| |||||||||||||||
| Wed | Jan 0915 | Lecture 2: Computation Graphs, Ideal Parallelism | Module 1: Sections 1.2, 1.3 | Topic 1.2 Lecture, Topic 1.2 Demonstration, Topic 1.3 Lecture, Topic 1.3 Demonstration | worksheet2 | lec2-slides | Homework 1 |
| ||||||||||||||
| Fri | Jan 1117 | Lecture 3: Abstract Performance Metrics, Multiprocessor Scheduling | Module 1: Section 1.4 | Topic 1.4 Lecture, Topic 1.4 Demonstration | worksheet3 | lec3-slides |
| ||||||||||||||||
2 | Mon | Jan 20 | No lecture, School Holiday (Martin Luther King, Jr. Day) | ||||||||||||||||||||
| Wed | Jan 22 14 | Lecture 4: Parallel Speedup and Amdahl's Law | Module 1: Section 1.5 | Topic 1.5 Lecture, Topic 1.5 Demonstration | worksheet4 | lec4-slides | Quiz for Unit 1 | |||||||||||||||
| FriWed | Jan 1624 | Lecture 5: Future Tasks, Functional Parallelism ("Back to the Future") | Module 1: Section 2.1 | Topic 2.1 Lecture, Topic 2.1 Demonstration | worksheet5 | lec5-slides | Quiz for Unit 1 | |||||||||||||||
3 | FriMon | Jan | 1827 | Lecture 6: | Memoization Finish Accumulators | Module 1: Section 2.23 | Topic 2. | 23 Lecture, Topic 2. | 23 Demonstration | worksheet6 | lec6-slides | 3 | Mon | Jan 21 | No lecture, School Holiday (Martin Luther King, Jr. Day) | ||||||||
| Wed | Jan 2329 | Lecture 7: Finish Accumulators Map Reduce | Module 1: Section 2.34 | Topic 2.3 4 Lecture, Topic 2.3 4 Demonstration | worksheet7 | lec7-slides | Homework 2 | Homework 1 | Fri | Jan 25 | Lecture 8: Map Reduce | Module 1: Section 2.4 | Topic 2.4 Lecture, Topic 2.4 Demonstration | ||||||||||
| Fri | Jan 31 | Lecture 8 | worksheet8 | lec8-slides |
| Quiz for Unit 1 | 4 | Mon | Jan 28 | Lecture 9: Data Races, Functional & Structural Determinism | Module 1: Sections Section 2.5, 2.6 | Topic 2.5 Lecture, Topic 2.5 Demonstration, Topic 2.6 Lecture, Topic 2.6 Demonstration | worksheet9worksheet8 | lec9lec8-slides |
| Quiz for Unit 1 | ||||||
4 | Mon | Feb 03 | Wed | Jan 30 | Lecture 109: Java’s Fork/Join Library | Module 1: Sections 2.7, 2.8 | Topic 2.7 Lecture, Topic 2.8 Lecture, | worksheet10worksheet9 | lec10lec9-slides | Quiz for Unit 2 | |||||||||||||
| WedFri | Feb 0105 | Lecture 1110: Loop-Level Parallelism, Parallel Matrix Multiplication, Iteration Grouping (Chunking) | Module 1: Sections 3.1, 3.2, 3.3 | Topic 3.1 Lecture , Topic 3.1 Demonstration , Topic 3.2 Lecture, Topic 3.2 Demonstration , Topic 3.3 Lecture , Topic 3.3 Demonstration | worksheet11 | lec11-slidesworksheet10 | lec10-slides | 5 | Mon | |||||||||||||
| Feb 04Fri | Feb 07 | Lecture 12: 11: Iteration Grouping (Chunking), Barrier Synchronization | Module 1: Section Sections 3.3, 3.4 | Topic 3.3 Lecture , Topic 3.3 Demonstration, Topic 3.4 Lecture , Topic 3.4 Demonstration | worksheet12worksheet11 | lec12lec11-slides | ||||||||||||||||
5 | Mon | WedFeb | 0610 | Lecture | 1312: Parallelism in Java Streams, Parallel Prefix Sums | Module 1: Section 3.7 | Topic Topic 3.7 Java Streams, Topic 3.7 Java Streams Demonstration | worksheet13worksheet12 | lec13lec12-slides | Homework 3 (includes 2 intermediate checkpoints) | Homework 2 | - | Fri | Feb 08 | Quiz for Unit 2Spring Recess | ||||||||
Wed | Feb 12 | Lecture 13 | 6 | Mon | Feb 11 | Lecture 14: Iterative Averaging Revisited, SPMD pattern | Module 1: Sections 3.5, 3.6 | Topic 3.5 Lecture , Topic 3.5 Demonstration , Topic 3.6 Lecture, Topic 3.6 Demonstration | worksheet14 | worksheet13 | lec14lec13-slides | Homework 3 (includes 2 intermediate checkpoints) Quiz for Unit 3 | Quiz for Unit Homework 2 | ||||||||||
- | FriWed | Feb 1314 | Spring Recess | ||||||||||||||||||||
6 | Mon | Feb 17 | Lecture 14: DataLecture 15: Data-Driven Tasks | Module 1: Section Sections 4.5 | Topic 4.5 Lecture Topic 4.5 Demonstration | worksheet15worksheet14 | lec15lec14-slides | ||||||||||||||||
| WedFri | Feb 1519 | Lecture 1615: Point-to-point Synchronization with Phasers | Module 1: Sections Section 4.2, 4.3 | Topic 4.2 Lecture , Topic 4.2 Demonstration, Topic 4.3 Lecture, Topic 4.3 Demonstration | worksheet16worksheet15 | lec16lec15-slides | Quiz for Unit 3 | |||||||||||||||
7 | Mon | Feb 18 | Lecture 17: Midterm Summary | lec17-slides | |||||||||||||||||||
| Fri | Feb 21 | Lecture 16: Pipeline Parallelism, Signal Statement, Fuzzy Barriers | Module 1: Sections 4.4, 4.1 | Topic 4.4 Lecture , Topic 4.4 Demonstration, Topic 4.1 Lecture, Topic 4.1 Demonstration | worksheet16 | lec16-slides | Quiz for Unit 4 | Quiz for Unit 3 | ||||||||||||||
7 | Mon | Feb 24 | Lecture 17: Midterm Review | lec17-slides |
| Wed | Feb 20 | Midterm Review (interactive Q&A) | |||||||||||||||
| FriWed | Feb 2226 | Lecture 18: Abstract vs. Real Performance | worksheet18 | lec18-slides | Homework 3, Checkpoint-1 | |||||||||||||||||
| Fri | Feb 28 | 8 | Mon | Feb 25 | Lecture 19: Pipeline Parallelism, Signal Statement, Fuzzy Barriers | Module 1: Sections 4.4, 4.1 | Critical Sections, Isolated construct (start of Module 2) | Module 2: Sections 5.1, 5.2, 5.6, | Topic 5.1 Lecture, Topic 5.1 Demonstration, Topic 5.2 Lecture, Topic 5.2 Demonstration, Topic 5.6 Lecture, Topic 5.6 DemonstrationTopic 4.4 Lecture , Topic 4.4 Demonstration, Topic 4.1 Lecture, Topic 4.1 Demonstration, | worksheet19 | lec19-slides | Homework 3, Checkpoint-1Quiz for Unit 4 | ||||||||||
8 | WedMon | Feb 27Mar 02 | Lecture 20: Critical sections, Isolated construct, Parallel Spanning Tree algorithm, Atomic variables (start of Module 2) | Module 2: Sections 5.1, 5.2, 5.3, 5.4, 5.65 | Topic 5.1 Lecture, Topic 5.1 Demonstration, Topic 5.2 Lecture, Topic 5.2 Demonstration, Topic 5.3 Lecture, Topic 5.3 Demonstration, Topic 5.4 Lecture, Topic 5.4 Demonstration, Topic 5.6 5 Lecture, Topic 5.6 5 Demonstration | worksheet20 | lec20-slides |
| |||||||||||||||
| FriWed | Mar 0104 | Lecture 21: Read-Write Isolation, Review of Phasers Actors | Module 2: Section 5.5 | Topic 5.5 Lecture, Topic 5.5 Demonstration | worksheet21 | lec21-slides | Quiz for Unit 5 | Quiz for Unit 4 | 9 | Mon | Mar 04 | Lecture 22: Actors | Module 2: 6.1, 6.6.1, 6.2 | Topic 6.1 Lecture , Topic 6.1 Demonstration , Topic 6.2 Lecture, Topic 6.2 Demonstration | worksheet22 worksheet21 | lec22lec21-slides |
| |||||
| FriWed | Mar 06 | Lecture 2322: Actors (contd) | Module 2: 6.3, 6.4, 6.5, 6.6 | Topic 6.3 Lecture, Topic 6.3 Demonstration, Topic 6.4 Lecture , Topic 6.4 Demonstration, Topic 6.5 Lecture, Topic 6.5 Demonstration , Topic 6.6 Lecture, Topic 6.6 Demonstration | worksheet23 | lec23-slidesworksheet22 | lec22-slides | Quiz for Unit 6Homework 3, Checkpoint-24 | ||||||||||||||
9 | MonFri | Mar 08 | Lecture 24: Java Threads, Java synchronized statement | Module 2: 7.1, 7.2 | Topic 7.1 Lecture, Topic 7.2 Lecture | worksheet24 | lec24-slides | 09 | No class | Quiz for Unit 5 | - | M-F | Mar 11 - Mar 15Spring Break |
| |||||||||
| Wed | 10Mar 11 | MonNo class | Mar 18 | Lecture 25: Java synchronized statement (contd), wait/notify | Module 2: 7.2 | Topic 7.2 Lecture | worksheet25 | lec25-slides
|
| |||||||||||||
| WedFri | Mar 13 | No class | ||||||||||||||||||||
| - | M-F | Mar 16 - Mar 20 | Spring Break | 20Lecture 26: Java Locks, Linearizability of Concurrent Objects | Module 2: 7.3, 7.4 | Topic 7.3 Lecture, Topic 7.4 Lecture | worksheet26 | lec26-slides | Homework 4 (includes one intermediate checkpoint)
| Homework 3 (all) | |||||||||||||
10 | FriMon | Mar 2223 | Lecture 27: Safety and Liveness Properties, Java Synchronizers, Dining Philosophers Problem23: Actors (contd) | Module 2: 76.5, 7.6 | Topic 76.5 6 Lecture, Topic 76.6 LectureDemonstration | worksheet27 | lec27lec23-slides | Quiz for Unit 7 | Quiz for Unit 6 |
| |||||||||||||
Wed | 11 | Mon | Mar 25 | Lecture | 28: Message Passing Interface (MPI), (start of Module 3)24: Java Threads, Java synchronized statement | Module 2: 7.1, 7.2 | Topic 7 | Topic 8 | .1 Lecture, Topic | 87.2 Lecture | , Topic 8.3 Lecture,lec24 | worksheet28 | lec28-slides |
| |||||||||
| FriWed | Mar 27 | Lecture 29: Message Passing Interface (MPI, contd) | Topic 8.4 Lecture, Topic 8.5 Lecture, Topic 8 Demonstration Video | worksheet29 | lec29-slides | Quiz for Unit 8 | ||||||||||||||||
| Fri | Mar 29 | Lecture 30: Distributed Map-Reduce using Hadoop and Spark frameworks | Topic 9.1 Lecture (optional, overlaps with video 2.4), Topic 9.2 Lecture, Topic 9.3 Lecture | worksheet30 | lec30-slides | Quiz for Unit 7 | ||||||||||||||||
12 | Mon | Apr 01 | Lecture 31: TF-IDF and PageRank Algorithms with Map-Reduce | Topic 9.4 Lecture, Topic 9.5 Lecture, Unit 9 Demonstration | worksheet31 | lec31-slides | Quiz for Unit 9 |
| |||||||||||||||
| Wed | Apr 03 | Guest Lecture |
| Homework 4 Checkpoint-1 | ||||||||||||||||||
| Fri | Apr 05 | Lecture 32: Partitioned Global Address Space (PGAS) programming models | Lectures 10.1 - 10.5, Unit 10 Demonstration (all videos optional – unit 10 has no quiz) | worksheet32 | lec32-slides |
| Quiz for Unit 8 | 13 | Mon | Apr 08 | Lecture 33: Combining Distribution and Multithreading | worksheet33 | lec33-slides | |||||||||
25: Java Threads, Java synchronized statement (contd), wait/notify | Module 2: 7.1, 7.2 | Topic 7.1 Lecture, Topic 7.2 Lecture | lec25-slides | Homework 3, Checkpoint-2 | |||||||||||||||||||
11 | Mon | Mar 30 | Lecture 26: Java Threads (exercise) | lec26-handout | Quiz for Unit 6 | Quiz for Unit 5 | |||||||||||||||||
| Wed | Apr 01 | Lecture 27: Java Locks | Module 2: 7.3 | Topic 7.3 Lecture | lec27-slides |
| ||||||||||||||||
| Fri | Apr 03 | Lecture 28: Linearizability of Concurrent Objects | Module 2: 7.4 | Topic 7.4 Lecture | lec28-slides |
Homework 4 (includes one intermediate checkpoint)
| Homework 3 (all)
| |||||||||||||||
12 | Mon | Apr 06 | Lecture 29: Java Locks (exercise) | lec29-handout | Quiz for Unit 6 | ||||||||||||||||||
| Wed | Apr 08 | Lecture 30: Safety and Liveness Properties, Java Synchronizers, Dining Philosophers Problem | Module 2: 7.5, 7.6 | Topic 7.5 Lecture, Topic 7.6 Lecture | lec30-slides | Quiz for Unit 7 |
| |||||||||||||||
| Fri | Apr 10 | Lecture 31: Message Passing Interface (MPI), (start of Module 3) | Topic 8.1 Lecture, Topic 8.2 Lecture, Topic 8.3 Lecture | lec31-slides |
| |||||||||||||||||
13 | Mon | Apr 13 | Lecture 32: Message Passing Interface (MPI, contd) | Topic 8.4 Lecture | lec32-slides | Homework 4 Checkpoint-1 | |||||||||||||||||
| Wed | Apr 15 | Lecture 33: Message Passing Interface (MPI, contd) | Topic 8.5 Lecture, Topic 8 Demonstration Video | lec33-slides |
|
| ||||||||||||||||
| Fri | Apr 17 | Lecture 34: Task Affinity with Places | Quiz for Unit 8 | Quiz for Unit 7 | ||||||||||||||||||
14 | Mon | Apr 20 | Lecture 35: Eureka-style Speculative Task Parallelism | lec35 | |||||||||||||||||||
| Wed | Apr 10 | Lecture 34: Task Affinity with Places | worksheet34 | lec34-slides | Homework 5 | Homework 4 (all) | ||||||||||||||||
| Fri | Apr 12 | Lecture 35: Eureka-style Speculative Task Parallelism | worksheet35 | lec35-slides |
| Quiz for Unit 9 | ||||||||||||||||
14 | Mon | Apr 15 | Lecture 36: Algorithms based on Parallel Prefix (Scan) operations | worksheet36 | lec36-slides |
| |||||||||||||||||
| Wed | Apr 1722 | Lecture 3736: Algorithms based on Parallel Prefix (Scan) operations, contd. | worksheet37 | lec37lec36-slides |
| Homework 4 (all) | ||||||||||||||||
| Fri | Apr 1924 | Lecture 3837: Course Review (Lectures 2019-3834) | lec38lec37-slides | Quiz for Unit 8 | Homework 5 | |||||||||||||||||
| - | |||||||||||||||||||||||
Lab Schedule
Lab # | Date (20192020) | Topic | Handouts | Examples | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | Infrastructure Setup | lab0-handout- | ||||||||
1 | Jan 1016 | Async-Finish Parallel Programming with abstract metrics | lab1-handout | |||||||
| - | No lab this week | |||||||||
2 | Jan 1730 | Futures | lab2-handout - | |||||||
3 | Jan 24Feb 06 | Cutoff Strategy and Real World Performance | lab3-handout | - | 4 | Jan 31 | Java's ForkJoin Framework | lab4-handout | - | |
- | Feb 7
| No lab this week - Spring Recess | - | |||||||
| 54 | Feb 1420 | DDFs | lab4-handout | lab5-handout | - | |||||
- | Feb 27 | No lab this week (midterm exam)
| ||||||||
5 | Mar 05 | 6 | Feb 28 | Loop-level Parallelism | lab6lab5-handout | lab6lab5-intro | ||||
7- | Mar 7 | Isolated Statement and Atomic Variables | lab7-handout | - | - | Mar 14 |
|
| ||
- |
| Isolated Statement and Atomic Variables | No lab this week - Spring Break||||||||
| 8- | Mar 21 | Actors | lab8-handout | |||||||
| -9 |
| Mar 28 | Java Threads, Java Locks | lab9-handout | ||||||
-10 |
| Apr 4 | Message Passing Interface (MPI) | lab10-handout | ||||||
- | 11 | Apr 11 | Apache Spark | lab11-handout | ||||||
- |
|
| Eureka-style Speculative Task Parallelism | |||||||
| - | Java's ForkJoin Framework |
Grading, Honor Code Policy, Processes and Procedures
...