Theory of Parallel Systems (SMA 5509)
Lecture Notes
|
LEC # |
TOPICS |
|
Week 1 |
|
|
1 |
Dynamic Multithreading (PDF) (Courtesy of Ben Adida and Abhi Shelat. Used with permission.) |
|
Week 2 |
|
|
2 |
Cilk, Matrix Multiplication, and Sorting (PDF) |
|
3 |
Serial Performance and Caching (PDF) (Courtesy of Kenneth Barr and Zardosht Kasheff. Used with permission.) |
|
Week 3 |
|
|
4 |
Determinacy Detection and Race Detection (PDF) (Courtesy of Siddhartha Sen and Jim Sukha. Used with permission.) |
|
5 |
Consistency of the Memory Sub-System |
|
Week 4 |
|
|
6 |
Analyzing Space Bounds (PDF) (Courtesy of Jeremy Fineman and Siddhartha Sen. Used with permission.) |
|
Week 5 |
|
|
7 |
Memory Contention (PDF) (Courtesy of Barbara Mack and C. Scott Ananian. Used with permission.) |
|
8 |
Cilk Scheduler (PDF) (Courtesy of Barbara Mack and Kevin Matulef. Used with permission.) |
|
Week 6 |
|
|
9 |
Analysis of Cilk Scheduler (PDF) (Courtesy of Alexandru Caracas and C. Scott Ananian. Used with permission.) |
|
10 |
Cilk Implementation (PDF) |
|
Week 7 |
|
|
11 |
|
|
Week 8 |
|
|
12 |
|
|
13 |
Implementation of Memory Consistency (PDF) (Courtesy of Seth Gilbert and Xie Yong. Used with permission.) |
|
Week 9 |
|
|
14 |
Competitive Snoopy Caching |
|
15 |
Snoopy Caching and Spin-Block Problem |
|
Week 10 |
|
|
16 |
Hypercubic Networks 1 |
|
17 |
Hypercubic Networks 2 (PDF) |
|
Week 11 |
|
|
18 |
Hypercubic Networks 3 (PDF) (Courtesy of Sriram Saroop and Wang Junqing. Used with permission.) |
|
Week 12 |
|
|
19 |
Squish Routing |
|
20 |
Permuting Data on Parallel Disks |
|
Week 13 |
|
|
21 |
Sorting and Permuting |
|
22 |
Pick a Winner |
|
Week 14 |
|
|
23 |
|
|
24 |
Final Project Presentations (cont.) |
|
Week 15 |
|
|
25 |
Final Project Presentations (cont.) |
|
26 |
|
Assignments
Problem Set 1 (PDF)
Problem Set 2 (PDF)
Problem Set 3 (PDF)
Problem Set 4 (PDF)
Projects
Term projects will be presented in class for the last four class sessions. Your group is also responsible for a project report of 5-10 pages due on the last day of class. About one-third of your term project grade will be from your presentation and two-thirds will be from your project report.
For the final presentation, each group will have about 10-12 minutes times the number of students in your group to make your presentation, plus a few minutes for questions. All students in the group should participate actively in the presentation. Prepare PowerPoint® or other online presentation materials.
The Fall 2003 student projects are provided below.
|
STUDENTS |
PROPOSALS |
FINAL PRESENTATIONS |
FINAL PAPERS |
|
Improving Cilk |
|||
|
Kunal Agrawal and Siddhartha Sen, "Adaptively Parallel Processor Allocation for Cilk Jobs" |
(PDF) |
(PDF) |
(PDF) |
|
Alexandru Caracas, "Fast Serial-Append File I/O Mode Support for Cilk" |
(PDF) (Courtesy of Alexandru Caracas. Used with permission.) |
(PDF) (Courtesy of Alexandru Caracas. Used with permission.) |
(PDF) (Courtesy of Alexandru Caracas. Used with permission.) |
|
Jason Hickey and Tyeler Quentmeyer, "A Space-Efficient Global Scheduler for Cilk" |
(PDF) |
(PDF) |
(PDF) |
|
Sajindra Jayasena and Sharad Ganesh, "Automatic Conversion of Non Series-Parallel DAGs to Series Parallel DAGs" |
(PDF) (Courtesy of Sharad Ganesh and Sajindra Jayasena. Used with permission.) |
(PDF) (Courtesy of Sharad Ganesh and Sajindra Jayasena. Used with permission.) |
|
|
Transactional Cilk |
|||
|
C. Scott Ananian, "Language-Level Complex Transactions" |
(PDF) (Courtesy of C. Scott Ananian. Used with permission.) |
(PDF) (Courtesy of C. Scott Ananian. Used with permission.) |
|
|
Sean Lie, "An Evaluation of Nested Concurrent Transactions" |
(PDF) (Courtesy of Sean Lie. Used with permission.) |
(PDF) (Courtesy of Sean Lie. Used with permission.) |
(PDF) (Courtesy of Sean Lie. Used with permission.) |
|
Jim Sukha, "Atomic Transactions in Cilk" |
(PDF) (Courtesy of Jim Sukha. Used with permission.) |
(PDF) |
(PDF) (Courtesy of Jim Sukha. Used with permission.) |
|
Xie Yong, "Transactions in Cilk" |
(PDF)(Courtesy of Xie Yong. Used with permission.) |
(PDF) (Courtesy of Xie Yong. Used with permission.) |
(PDF) (Courtesy of Xie Yong. Used with permission.) |
|
Non-Determinacy Detection |
|||
|
Jeremy Fineman, "Linear Time Detection of Determinacy Races" |
(PDF) (Courtesy of Jeremy Fineman. Used with permission.) |
(PDF) (Courtesy of Jeremy Fineman. Used with permission.) |
(PDF) (Courtesy of Jeremy Fineman. Used with permission.) |
|
He Yuxiong, "Parallel Nondeterminator" |
|||
|
Wang Junqing, "Parallel Nondeterminator" |
(PDF) (Courtesy of Wang Junqing. Used with permission.) |
(PDF) |
|
|
Using Cilk |
|||
|
Kenneth C. Barr, "Accelerating Multiprocessor Simulation" |
|||
|
Zardosht Kesheff, "Parallelizing METIS" |
(PDF) (Courtesy of Zardosht Kasheff. Used with permission.) |
(PDF) (Courtesy of Zardosht Kasheff. Used with permission.) |
(PDF) (Courtesy of Zardosht Kasheff. Used with permission.) |
|
Paul Youn, "Parallelizing Sorting" |
|||
|
Pham Duc Minh, "Implement FIR Filter in Parallel Using Cilk" |
|||
|
Cache-Oblivious Algorithms |
|||
|
Advait D.Karande and Sriram Saroop, "Cache-Oblivious Sorting for Burrows-Wheeler Transform" |
(PDF) (Courtesy of Advait Karande and Sriram Saroop. Used with permission.) |
(PDF) (Courtesy of Advait Karande and Sriram Saroop. Used with permission.) |
(PDF) (Courtesy of Advait Karande and Sriram Saroop. Used with permission.) |
|
Zhang Jiahui and Neel Kamal, "New Cache-Oblivious Algorithms" |
(PDF) (Courtesy of Zhang Jiahu. Used with permission.) |
||
|
Seth Gilbert, "Cache-Oblivious, Lock-Free Algorithms" |
(PDF) (Courtesy of Seth Gilbert. Used with permission.) |
(PDF) (Courtesy of Jeremy Fineman and Seth Gilbert. Used with permission.) |
(PDF) (Courtesy of Seth Gilbert. Used with permission.) |