COMP 322: Fundamentals of Parallel Programming (Spring
...
2024)
InstructorsInstructor: | Mackale Joyner, DH 2063 |
---|
Zoran Budimlić, DH 3003 Adrienne Li, Austin Hushower, Claire Xu, Diep Hoang, Hunena Badat, Maki Yu, Mantej Singh, Rose Zhang, Victor Song, Yidi Wang | Admin Assistant: | Annepha Hurlock, annepha@rice.edu , DH 3122, 713-348-5186 | | |
Piazza site: | https://piazza.com/rice/spring2022/comp322 (Piazza is the preferred medium for all course communications) | Cross-listing: | ELEC 323 |
---|
Lecture location: | Herzstein |
---|
Amphitheater (online 1st 2 weeks)Amp | Lecture times: | MWF 1:00pm - 1:50pm |
---|
Lab locations: |
---|
Keck 100 (online 1st 2 weeks | Mon (Brockman 101) Tue (Herzstein Amp) | Lab times: | Mon 3:00pm - 3:50pm ( |
---|
Austin ClaireWed 30pm - 5:20pm (Hunena, Mantej, Yidi, Victor, Rose, Adrienne, Diep, Maki Course Syllabus
A summary PDF file containing the course syllabus for the course can be found here. Much of the syllabus information is also included below in this course web site, along with some additional details that are not included in the syllabus.
...
There are also a few optional textbooks that we will draw from during the course. You are encouraged to get copies of any or all of these books. They will serve as useful references both during and after this course:
- Fork-Join Parallelism with a Data-Structures Focus (FJP) by Dan Grossman (Chapter 7 in Topics in Parallel and Distributed Computing)
- Java Concurrency in Practice by Brian Goetz with Tim Peierls, Joshua Bloch, Joseph Bowbeer, David Holmes and Doug Lea
- Principles of Parallel Programming by Calvin Lin and Lawrence Snyder
- The Art of Multiprocessor Programming by Maurice Herlihy and Nir Shavit
Lecture Schedule
...
20222024) | Lecture | Assigned Reading | Assigned Videos (see Canvas site for video links) | In-class Worksheets | Slides | Work Assigned | Work Due | Worksheet Solutions |
---|
| 1008 | Lecture 1: Introduction |
| slides | | 1210 | Lecture 2: Functional Programming |
GList.java | | Fri | | 1412 | Lecture 3: Higher order functions |
| worksheet3 slides 17 | | | | | | | | 1917 | Lecture 4: Lazy Computation |
LazyList.javaLazy.java
| | | | 2119 | Lecture 5: Java Streams |
| worksheet5 | 2422 | Lecture 6: Map Reduce with Java Streams | Module 1: Section 2.4 | Topic 2.4 Lecture, Topic 2.4 Demonstration | worksheet6 | lec6-slides |
| | 2624 | Lecture 7: Futures | Module 1: Section 2.1 | Topic 2.1 Lecture , Topic 2.1 Demonstration | worksheet7 | lec7-slides |
| | 2826 | Lecture 8: Async, Finish, Computation Graphs |
, Ideal Parallelism232 2 1 Demonstration, Topic 1. |
3 3 lec8 | | 31 Async, FinishIdeal Parallelism, Data-Driven Tasks | Module 1: Section 1. |
1 1 1 | | Feb 02Jan 31 | Lecture 10: Event-based programming model |
| | | 0402 | Lecture 11: GUI programming |
as an example of event-based,futures/callbacks in GUI programming, Scheduling/executing computation graphs
| Module 1: Section 1.4 | Topic 1.4 Lecture , Topic 1.4 Demonstration |
| Homework 1 07Scheduling/executing computation graphs Abstract performance metrics, Parallel Speedup, Amdahl's Law | Module 1: Section 1. |
44 4 | | | 09 Parallel Speedup, Critical Path, Amdahl's Law Accumulation and reduction. Finish accumulators | Module 1: Section |
15 15 , 15 | 1109 | No class: Spring Recess |
| | | | | | | | 14 Accumulation and reduction. Finish accumulatorsData Races, Functional & Structural Determinism | Module 1: |
Section 36 | Topic 2.5 Lecture , Topic 2.5 Demonstration, Topic 2. |
3 3 | | | 16 Recursive Task Parallelism | | | | WS15-solution | | 18 Data Races, Functional & Structural DeterminismModule 1: Sections 2.5, 2.6 | Topic 2.5 Lecture , Topic 2.5 Demonstration, Topic 2.6 Lecture, Topic 2.6 DemonstrationHomework 2 | | 2119 | Lecture 17: Midterm Review |
| | | | | | 23 | | worksheet18 | Limitations of Functional parallelism.
Abstract vs. real performance. Cutoff Strategy | WS18-solution | | | 25 Fork/Join programming model. OS Threads. Scheduler Pattern Data-Parallel Programming model. Loop-Level Parallelism, Loop Chunking | Module 1: Sections |
278 27 1 Lecture, Topic 3.1 Demonstration , Topic 3.2 Lecture, Topic 3. |
7 28 Topic 28 , | | | 28 Confinement & Monitor Pattern. Critical sections
Global lock Barrier Synchronization with Phasers | Module |
2 5.1, 5.2, 5.6 51 51 Demonstration, Topic 5.2 Lecture, Topic 5.2 Demonstration, Topic 5.6 Lecture, Topic 5.6 DemonstrationWS204 Demonstration | worksheet20 | lec20-slides |
| | | Mar 02 Atomic variables, Synchronized statements Stencil computation. Point-to-point Synchronization with Phasers | Module 1: Sections 4.2, 4.3 | Topic 4.2 Lecture, Topic 4.2 Demonstration, Topic 4.3 Lecture, Topic 4.3 Demonstration |
Module 2: Sections 5.4, 7.2 | Topic 5.4 Lecture, Topic 5.4 Demonstration, Topic 7.2 Lecture | | Fri | 04Parallel Spanning Tree, other graph algorithms Fuzzy Barriers with Phasers | Module 1: Section 4.1 | Topic 4.1 Lecture, Topic 4.1 Demonstration |
| Homework 4 | Homework 3 07 Java Threads and LocksModule 2: Sections 7.1, 7.3 | Topic 7.1 Lecture, Topic 7.3 Lecture Fork/Join programming model. OS Threads. Scheduler Pattern |
| Topic 2.7 Lecture, Topic 2.7 Demonstration, Topic 2.8 Lecture, Topic 2.8 Demonstration | worksheet23 | lec23-slides |
| |
| Homework 3 (CP 1) | WS23-solution |
| 09 Java Locks - Soundness and progress guarantees Confinement & Monitor Pattern. Critical sections Global lock | Module 2: |
7Topic 7.5 Lecture Topic 5.1 Lecture, Topic 5.1 Demonstration, Topic 5.2 Lecture, Topic 5.2 Demonstration, Topic 5.6 Lecture, Topic 5.6 Demonstration | worksheet24 | lec24-slides |
| | 11 Dining Philosophers Problem Atomic variables, Synchronized statements | Module 2: Sections 5.4, 7. |
6 76 Lecture4 Lecture, Topic 5.4 Demonstration, Topic 7.2 Lecture | worksheet25 | lec25-slides |
| | 14 | | | | | | | 16 | | | | | | | | 18 | | | | | | | | 10 | 21 | | N-Body problem, applications and implementations Parallel Spanning Tree, other graph algorithms |
|
|
| | 23 Read-Write Locks, Linearizability of Concurrent ObjectsJava Threads and Locks | Module 2: Sections 7. |
343 4 3 Lecture | worksheet27 | lec27-slides |
| Homework 3 (CP 2) | WS27-solution |
| 25 Message-Passing programming model with ActorsJava Locks - Soundness and progress guarantees | Module 2: |
6.1, 6.2 61 Lecture, Topic 6.1 Demonstration, Topic 6.2 Lecture, Topic 6.2 DemonstrationWS285 Lecture | worksheet28 | lec28-slides |
| | 28 Active Object Pattern. Combining Actors with task parallelism Dining Philosophers Problem | Module 2: |
63, .4 6.3 Lecture, Topic 6.3 Demonstration, Topic 6.4 Lecture, Topic 6.4 Demonstration7.6 Lecture | worksheet29 | lec29-slides |
| | | 30 Task Affinity and locality. Memory hierarchy Read-Write Locks, Linearizability of Concurrent Objects | Module 2: Sections 7.3, 7.4 | Topic 7.3 Lecture, Topic 7.4 Lecture |
| | | Apr 01DataParallel Programming model. Loop-Level Parallelism, Loop ChunkingModule 1: Sections 3Passing programming model with Actors | Module 2: Sections 6.1, |
3, 3.3 3 3 3 Topic 3, Topic 3.3 Lecture, Topic 3.3 DemonstrationHomework 5 | Homework 4 04 Barrier Synchronization with Phasers Active Object Pattern. Combining Actors with task parallelism | Module |
1 Section Sections 6.3, 6.4 | Topic 6.3 Lecture, Topic 6.3 Demonstration, Topic 6.4 Lecture, |
Topic 3Topic 6.4 Demonstration | worksheet32 | lec32-slides |
| Homework 4 | Homework 3 (All) |
| | 06 Stencil computation. Point-to-point Synchronization with PhasersModule 1: Section 4.2, 4.3 | Topic 4.2 Lecture, Topic 4.2 Demonstration, Topic 4.3 Lecture, Topic 4.3 Demonstration | worksheet33 | lec33-slides | | | WS33-solution | | Task Affinity and locality. Memory hierarchy |
|
| worksheet33 | lec33-slides |
|
| WS33-solution |
|
| Fri | Apr 05 | Lecture 34 |
---|
| Fri | Apr 08 | Lecture 34: Fuzzy Barriers with Phasers | Module 1: Section 4.1 | Topic 4.1 Lecture, Topic 4.1 Demonstration | worksheet34 | lec34-slides | | | | |
---|
13 | Mon | Apr 11 | Lecture 35: Eureka-style Speculative Task Parallelism | |
lec35worksheet35 | | Apr 08 | No class: Solar Eclipse |
13 3635: Scan Pattern. Parallel Prefix Sum |
| | worksheet36 | lec36 | | | | |
| Homework 4 (CP 1) | WS35-solution |
|
| Fri | Apr |
15 3736: Parallel Prefix Sum applications |
| | worksheet37 | lec37 | | | 18 38lec3837: Overview of other models and frameworks |
| | | | | | | 20 3938: Course Review (Lectures 19- |
38lec39 | | | | | | | 22 4039: Course Review (Lectures 19- |
38lec40 | | | | Homework 5 | |
Lab Schedule
20222023) | Topic | Handouts | Examples |
---|
1 | Jan |
---|
10 |
|
- | Jan 15 | No lab this week (MLK) |
|
|
---|
2 | Jan |
---|
17 24Java Streams Jan 31 | Futures | lab4-handout | | 5 | Feb 07lab56 | 14Async / Finish | lab6-handout | 21719 | No lab this week (Midterm Exam) |
| | 28Recursive Task Cutoff Strategy | lab7 8 0704 | Recursive Task Cutoff Strategy | lab6 |
Java Threads | lab8 | 1411 | No lab this week (Spring Break |
) | | 9 21Concurrent Listslab910 | 28Actorslab1011 | 04Loop Parallelismlab11 11 | 18 | | | Grading, Honor Code Policy, Processes and Procedures
...
Labs must be submitted by the following Wednesday Monday at 4:30pm3pm. Labs must be checked off by a TA.
...