15-492: Parallel Algorithms (Fall 2007)

Instructor: Guy Blelloch, Office Hours Monday 1:30 - 2:30, WeH 7125 or by appointment.
Time: Tuesday and Thursday 12:00 - 1:20pm
Place: Wean 5302
TA: Kanat Tangwongsan, Office Hours Tuesday 1:30 - 2:30, WeH 7102 or by appointment.

Course Description: In this course students will learn about parallel algorithms. The emphasis will be on algorithms that can be used on shared-memory parallel machines such as multicore architectures. The course will include both a theoretical component and a programming component. Topics to be covered include: modeling the cost of parallel algorithms, lower-bounds, and parallel algorithms for sorting, graphs, computational geometry, and string operations. The programming language component will include data-parallelism, threads, futures, scheduling, synchronization types, transactional memory, and message passing.

Course Requirements: There will be bi-weekly assignments, a take-home midterm exam, and a final project. Each student will be required to scribe two lectures. Students will get an account on multi6.aladdin.cs.cmu.edu for use on some of the later assignments. We would like to thank Intel Corp. for donating this meachine and Microsoft for some help supporting the class through the Center for Computational Thinking.

Course Project: The final part of the course involves implementing parallel programs to solve real-world problems. A short project proposal (between 1/4 and 1/2 a page) is due Tuesday November 13th. The proposal should succintly describe the scope and goal of the project and a rough timeline. Each project is to be completed by 1 - 2 students. Here are some project ideas.

Scribe Schedule: Click here

Approximate Schedule:

Class Day Date Topic Notes
1 Tue Aug 28 Introduction (Scribe: ps|pdf) -
2 Thur Aug 30 Parallel Models I (Scribe: ps|pdf) Assignment 1 out [ps|pdf]
3 Tue Sep 4 Parallel Models II (Scribe: ps|pdf) -
4 Thur Sep 6 General Techniques (Scribe: pdf) Assignment 1 due
[Solutions: ps|pdf]
5 Tue Sep 11 Sets and Sequences I (Scribe: ps|pdf) Assignment 2 out [ps|pdf]
6 Thur Sep 13 Sets and Sequences II (Scribe: ps|pdf) -
7 Tue Sep 18 Merging (Scribe: ps|pdf) -
8 Thur Sep 20 Trees I (Scribe: ps|pdf) Assignment 2 due
9 Tue Sep 25 Trees II (Scribe: ps|pdf) Assignment 3 out [ps|pdf]
10 Thur Sep 27 Probability Bounds Tutorial (Optional)
(Slides: pdf, Scribe: ps|pdf)
11 Tue Oct 2 Graphs I (Scribe [very rough draft]: ps|pdf) -
12 Thur Oct 4 Graphs II (Scribe [very rough draft]: ps|pdf) Assignment 3 due
13 Tue Oct 9 Computational Geometry (Scribe [unedited]: ps|pdf) -
14 Thur Oct 11 Guest Lecture: Vijay Saraswat -
15 Tue Oct 16 String Processing
Paper: Simple Linear Work Suffix Array Construction
(Scribe [unedited]: ps| pdf)
Takehome Midterm Due
16 Thur Oct 18 Parallel Languages Assignment 4 out [ps|pdf]
17 Tue Oct 23 Futures -
18 Thur Oct 25 Cilk Assignment 4 due
19 Tue Oct 30 OpenMP Assignment 4 due
Assignment 5 out [ps|pdf]
20 Thur Nov 1 Scheduling I (Scribe [unedited]: ps| pdf) -
21 Tue Nov 5 Scheduling II -
22 Thur Nov 8 Asynchronous Algorithms I -
23 Tue Nov 13 Asynchronous Algorithms II Assignment 5 due
24 Thur Nov 15 Transactional Memory I -
25 Tue Nov 20 Transactional Memory II -
- Thur Nov 22 Thanksgiving -
26 Tue Nov 27 Transactional Memory III
HerlihyWing'90 (Linearizability)
27 Thur Nov 29 Message Passing -
28 Tue Dec 4 Other Programming Models -
29 Thur Dec 6 Review -
- Thur Dec 13 Final Project Due -

Reading List:

Scribes: Here is a LaTeX template.