...
Instructor: | Prof. Vivek Sarkar, DH 3080 | Graduate TA: | Prasanth Chatarasi |
---|---|---|---|
| Please send all emails to comp322-staff at rice dot edu | Graduate TA: | Peng Du |
Assistant: | Penny Anderson, anderson@rice.edu, DH 3080 | Graduate TA: | Xian Fan |
Undergrad TAs: | Matthew Bernhard, Nicholas Hanson-Holtry, Yi Hua, | ||
|
|
| Yoko Li, Ayush Narayan, Derek Peirce, Maggie Tang, |
Cross-listing: | ELEC 323 | Bing Xue, Wei Zeng, Glenn Zhu | |
|
| Course consultants: | Vincent Cavé, Shams Imam |
Lectures: | Herzstein Hall 210 | Lecture times: | MWF 1:00pm - 1:50pm |
Labs: | TBD | Lab times: | Wednesday, 07:00pm - 08:30pm |
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 included in the syllabus.
Course Objectives
The primary goal of COMP 322 is to introduce you to the fundamentals of parallel programming and parallel algorithms, using by following a pedagogic approach that exposes you to the intellectual challenges in parallel software without enmeshing you in the jargon and lower-level details of today's parallel systems. A strong grasp of the course fundamentals will enable you to quickly pick up any specific parallel programming model system that you may encounter in the future, and also prepare you for studying advanced topics related to parallelism and concurrency in more advanced courses such as COMP 422.
To ensure that students gain a strong knowledge of parallel programming foundations, the classes and homeworks will place equal emphasis on both theory and practice. The programming component of the course will mostly use the Habanero-Java Library (HJ-lib) pedagogic extension to the Java language developed in the Habanero Extreme Scale Software Research project at Rice University. The course will also introduce you to real-world parallel programming models including Java Concurrency, MapReduce, MPI, OpenCL and CUDA. An important goal is that, at the end of COMP 322, you should feel comfortable programming in any parallel language for which you are familiar with the underlying sequential language (Java or C). Any parallel programming primitives that you encounter in the future should be easily recognizable based on the fundamentals studied in COMP 322.
Course Overview
COMP 322 provides the student with a comprehensive introduction to the building blocks of parallel software, which includes the following concepts:
- Primitive constructs for task creation & termination, synchronization, task and data distribution
- Abstract models: parallel computations, computation graphs, Flynn's taxonomy (instruction vs. data parallelism), PRAM model
- Parallel algorithms for data structures that include arrays, lists, strings, trees, graphs, and key-value pairs
- Common parallel programming patterns including task parallelism, pipeline parallelism, data parallelism, divide-and-conquer parallelism, map-reduce, concurrent event processing including graphical user interfaces.
These concepts will be introduced in three modules:
- Deterministic Shared-Memory Parallelism: creation and coordination of parallelism (async, finish), abstract performance metrics (work, critical paths), Amdahl's Law, weak vs. strong scaling, data races and determinism, data race avoidance (immutability, futures, accumulators, dataflow), deadlock avoidance, abstract vs. real performance (granularity, scalability), collective & point-to-point synchronization (phasers, barriers), parallel algorithms, systolic arrays.
- Nondeterministic Shared-Memory Parallelism and Concurrency: critical sections, atomicity, isolation, high level data races, nondeterminism, linearizability, liveness/progress guarantees, actors, request-response parallelism, Java Concurrency, locks, condition variables, semaphores, memory consistency models.
- Distributed-Memory Parallelism and Locality: memory hierarchies, cache affinity, data movement, message-passing (MPI), communication overheads (bandwidth, latency), MapReduce, accelerators, GPGPUs, CUDA, OpenCL, energy efficiency, resilience.
...
The desired learning outcomes fall into three major areas (course modules):
1) Fundamentals of Parallelism: creation and coordination of parallelism (async, finish), abstract performance metrics (work, critical paths), Amdahl's Law, weak vs. strong scaling, data races and determinism, data race avoidance (immutability, futures, accumulators, dataflow), deadlock avoidance, abstract vs. real performance (granularity, scalability), collective & point-to-point synchronization (phasers, barriers), parallel algorithms, systolic algorithms.
2) Fundamentals of Concurrency: critical sections, atomicity, isolation, high level data races, nondeterminism, linearizability, liveness/progress guarantees, actors, request-response parallelism, Java Concurrency, locks, condition variables, semaphores, memory consistency models.
3) Fundamentals of Distributed-Memory Parallelism: memory hierarchies, locality, cache affinity, data movement, message-passing (MPI), communication overheads (bandwidth, latency), MapReduce, accelerators, GPGPUs, CUDA, OpenCL, energy efficiency, resilience.
To achieve these learning outcomes, each class period will include time for both instructor lectures and in-class exercises based on assigned reading and videos. The lab exercises will be used to help students gain hands-on programming experience with the concepts introduced in the lectures.
To ensure that students gain a strong knowledge of parallel programming foundations, the classes and homeworks will place equal emphasis on both theory and practice. The programming component of the course will mostly use the Habanero-Java Library (HJ-lib) pedagogic extension to the Java language developed in the Habanero Extreme Scale Software Research project at Rice University. The course will also introduce you to real-world parallel programming models including Java Concurrency, MapReduce, MPI, OpenCL and CUDA. An important goal is that, at the end of COMP 322, you should feel comfortable programming in any parallel language for which you are familiar with the underlying sequential language (Java or C). Any parallel programming primitives that you encounter in the future should be easily recognizable based on the fundamentals studied in COMP 322.
Prerequisite
The prerequisite course requirements are COMP 182 and COMP 215. COMP 322 should be accessible to anyone familiar with the foundations of sequential algorithms and data structures, and with basic Java programming. COMP 221 is also recommended as a co-requisite.
Textbooks
There are no required textbooks for the class. Instead, lecture handouts are provided for each module as follows:
- Module 1 handout (Deterministic Shared-Memory Parallelism)
- Module 2 handout (Nondeterministic Shared-Memory Parallelism and Concurrency)
- Module 3 handout (Distributed-Memory Parallelism and Locality)
...
- 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
Past Offerings of COMP 322
Lecture Schedule
Week | Day | Date (2015) | Topic | Reading | Videos | In-class Worksheets | Slides | Code Examples | Work Assigned | Work Due |
---|---|---|---|---|---|---|---|---|---|---|
1 | Mon | Jan 12 | Lecture 1: The What and Why of Parallel Programming, Task Creation and Termination (Async, Finish) | Module 1: Sections 0.1, 0.2, 1.1 | worksheet1 | lec1-slides | Demo File: ReciprocalArraySum.java |
| ||
| Wed | Jan 14 | 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 | Demo File: Search.java | Topic 1.2 Lecture Quiz , Topic 1.2 Demo Quiz , Topic 1.3 Lecture Quiz , Topic 1.3 Demo Quiz |
|
| Fri | Jan 16 | Lecture 3: , Abstract Performance Metrics, Multiprocessor Scheduling | Module 1: Section 1.4 | Topic 1.4 Lecture, Topic 1.4 Demonstration | worksheet3 | lec3-slides | Worksheet File: Search.java Homework 1 Files: QuicksortUtil.java , QuicksortSeq.java , QuicksortPar.java | Homework 1, Topic 1.4 Lecture Quiz , Topic 1.4 Demo Quiz, Topic 1.6 Lecture Quiz , Topic 1.6 Demo Quiz | |
2 | Mon | Jan 19 | No lecture, School Holiday (Martin Luther King, Jr. Day) | |||||||
| Wed | Jan 21 | Lecture 4: Parallel Speedup and Amdahl's Law | Module 1: Section 1.5 | Topic 1.5 Lecture, Topic 1.5 Demonstration | worksheet4 | lec4-slides | Demo File: VectorAdd.java | Topic 1.5 Lecture Quiz , Topic 1.5 Demo Quiz | |
| Fri | Jan 23 | No lecture (inclement weather) | All 12 lecture & demo quizzes in Unit 1 are due by 5pm CST today | ||||||
3 | Mon | Jan 26 | Lecture 5: Future Tasks, Functional Parallelism | Module 1: Section 2.1 | Topic 2.1 Lecture , Topic 2.1 Demonstration | worksheet5 | lec5-slides | Demo File(s): ReciprocalArraySumFutures.java, BinaryTreesSeq.java, BinaryTrees.java | ||
| Wed | Jan 28 | Lecture 6: Finish Accumulators | Module 1: Section 2.3 | Topic 2.3 Lecture , Topic 2.3 Demonstration | worksheet6 | lec6-slides | Demo File: Nqueens.java |
| |
| Fri | Jan 30 | Lecture 7: Data Races, Functional & Structural Determinism | Module 1: Sections 2.5, 2.6 | Topic 2.5 Lecture , Topic 2.5 Demonstration, Topic 2.6 Lecture , Topic 2.6 Demonstration | lec7-slides | Demo File: ReciprocalArraySum.java | Homework 1 | ||
4 | Mon | Feb 02 | Lecture 8: Map Reduce | Module 1: Section 2.4 | Topic 2.4 Lecture , Topic 2.4 Demonstration | worksheet8 | lec8-slides | Demo File(s): WordCount.java, words.txt Worksheet Files: WordCount.java , words.txt Homework 2 Files: GeneralizedReduce.java, GeneralizedReduceApp.java, SumReduction.java, TestSumReduction.java | Homework 2 | |
| Wed | Feb 04 | Lecture 9: Memoization | Module 1: Section 2.2 | Topic 2.2 Lecture , Topic 2.2 Demonstration | worksheet9 | lec9-slides | Demo File: PascalsTriangleWithFuture.java Worksheet File: PascalsTriangleMemoized.java Worksheet Solution: PascalsTriangleMemoizedSolution.java | ||
| Fri | Feb 06 | Lecture 10: Abstract vs. Real Performance | worksheet10 | lec10-slides | |||||
5 | Mon | Feb 09 | Lecture 11: Loop-Level Parallelism, Parallel Matrix Multiplication | Topic 3.1 Lecture, Topic 3.1 Demonstration, Topic 3.2 Lecture , Topic 3.2 Demonstration | worksheet11 | lec11-slides | Demo File: ForallWithIterable.java, VectorAddForall.java, MatrixMultiplicationMetrics.java | |||
| Wed | Feb 11 | Lecture 12: Iteration Grouping (Chunking), Barrier Synchronization | Topic 3.3 Lecture , Topic 3.3 Demonstration , Topic 3.4 Lecture , Topic 3.4 Demonstration | worksheet12 | lec12-slides | Demo File: MatrixMultiplicationPerformance.java, BarrierInForall.java | |||
| Fri | Feb 13 | Lecture 13: Iterative Averaging Revisited | Topic 3.5 Lecture , Topic 3.5 Demonstration , Topic 3.6 Lecture , Topic 3.6 Demonstration | worksheet13 | lec13-slides | Demo File: OneDimAveragingGrouped.java, OneDimAveragingBarrier.java Worksheet File: OneDimAveragingBarrier.java |
| ||
6 | Mon | Feb 16 | Lecture 14: Data-Driven Tasks and Data-Driven Futures | Topic 4.5 Lecture , Topic 4.5 Demonstration | worksheet14 | lec14-slides | Demo File: DataDrivenFutures4.java | Homework 2 | ||
| Wed | Feb 18 | Lecture 15: Review of Module-1 HJ-lib API's | worksheet15 | lec15-slides | Homework 3 Files: SeqScoring.java | Homework 3 | |||
| Fri | Feb 20 | Lecture 16: Point-to-point Synchronization with Phasers | Topic 4.2 Lecture , Topic 4.2 Demonstration | worksheet16 | lec16-slides | Demo File: Phaser3Asyncs.java | |||
7 | Mon | Feb 23 | Lecture 17: Phasers (contd), Signal Statement, Fuzzy Barriers | Topic 4.1 Lecture , Topic 4.1 Demonstration | worksheet17 | lec17-slides | Demo File: PhaserSignal.java | |||
| Wed | Feb 25 | Lecture 18: Midterm Summary, Take-home Exam 1 distributed | lec18-slides | Exam 1 | |||||
| F | Feb 27 | No Lecture (Exam 1 due by 4pm today) | Exam 1 | ||||||
- | M-F | Feb 28- Mar 08 | Spring Break |
|
|
|
| |||
8 | Mon | Mar 09 | Lecture 19: Critical sections, Isolated construct, Parallel Spanning Tree algorithm | Topic 5.1 Lecture, Topic 5.1 Demonstration, Topic 5.2 Lecture, Topic 5.2 Demonstration, Topic 5.3 Lecture, Topic 5.3 Demonstration | worksheet19 | lec19-slides |
| |||
| Wed | Mar 11 | Lecture 20: Speculative parallelization of isolated constructs (Guest lecture by Prof. Swarat Chaudhuri) | worksheet20 | lec20-slides | Homework 3 | ||||
| Fri | Mar 13 | Lecture 21: Read-Write Isolation, Atomic variables | Topic 5.4 Lecture , Topic 5.4 Demonstration , Topic 5.5 Lecture, Topic 5.5 Demonstration, Topic 5.6 Lecture, Topic 5.6 Demonstration | worksheet21 | lec21-slides |
| |||
9 | Mon | Mar 16 | Lecture 22: Actors | Topic 6.1 Lecture, Topic 6.1 Demonstration, Topic 6.2 Lecture, Topic 6.2 Demonstration, Topic 6.3 Lecture, Topic 6.3 Demonstration | worksheet22 | lec22-slides | Homework 4 Files: hw4_files.zip |
| ||
| Wed | Mar 18 | Lecture 23: Actors (contd) | 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-slides |
|
| ||
| Fri | Mar 20 | Lecture 24: Monitors, Java Concurrent Collections, Linearizability of Concurrent Objects | Topic 7.4 Lecture | worksheet24 | lec24-slides |
|
|
| |
10 | Mon | Mar 23 | Lecture 25: Linearizability (contd), Intro to Java Threads | Topic 7.1 Lecture | worksheet25 | lec25-slides |
|
|
| |
| Wed | Mar 25 | Lecture 26: Java Threads (contd), Java synchronized statement | Topic 7.2 Lecture | worksheet26 | lec26-slides |
| |||
| Fri | Mar 27 | Lecture 27: Java synchronized statement (contd), advanced locking | Topic 7.3 Lecture | worksheet27 | lec27-slides |
|
|
| |
11 | Mon | Mar 30 | Lecture 28: Safety and Liveness Properties | Topic 7.5 Lecture | worksheet28 | lec28-slides |
|
|
| |
| Wed | Apr 01 | Lecture 29: Dining Philosophers Problem | Topic 7.6 Lecture | worksheet29 | lec29-slides |
|
| Homework 4 (due by 11:55pm on April 2nd) | |
- | Fri | Apr 03 | Midterm Recess | |||||||
12 | Mon | Apr 06 | Lecture 30: Message Passing Interface (MPI) | worksheet30 | lec30-slides | Homework 5 files: hw5_files.zip | Homework 5 |
| ||
| Wed | Apr 08 | Lecture 31: Partitioned Global Address Space (PGAS) languages (Guest lecture by Prof. John Mellor-Crummey) | worksheet31 | lec31-slides |
|
|
| ||
| Fri | Apr 10 | Lecture 32: Message Passing Interface (MPI, contd) | worksheet32 | lec32-slides |
|
|
| ||
13 | Mon | Apr 13 | Lecture 33: Task Affinity with Places | worksheet33 | lec33-slides |
| ||||
| Wed | Apr 15 | Lecture 34: GPU Computing | worksheet34 | lec34-slides |
|
|
| ||
| Fri | Apr 17 | Lecture 35: Memory Consistency Models | worksheet35 | Homework 6 (written only) |
| ||||
14 | Mon | Apr 20 | Lecture 36: Comparison of Parallel Programming Models | worksheet36 | lec36-slides |
| Homework 5 (due by 11:55pm on Monday, April 21st) | |||
| Wed | Apr 22 | NO CLASS (time allocated to work on homeworks) |
|
|
| ||||
| Fri | Apr 24 | Lecture 37: Course Review (lectures 19-35), Take-home Exam 2 distributed, Last day of classes | lec37-slides | Exam 2 | Homework 6 (due by 11:55pm on April 25th, penalty-free extension till May 2nd) | ||||
- | Fri | May 01 | Exam 2 due by 4pm today |
|
|
| Exam 2 |
...