Handouts and Papers
Week 1 |
Week 2 |
Week 3 |
Week 4 |
Week 5 |
Week 6 |
Week 7 |
Week 8 |
Week 9 |
Week 10 |
Week 11 |
Week 12 |
Week 13 |
Week 14 |
Week 15
Week 1
Week 2
- Lecture 3 - Sorting Code Handout
(ps)
(latex)
- C Code for Sorting
(.c)
- ASM Code for Sorting (Excerpt)
(.asm)
- Cache-Oblivious Algorithms
Week 3
- Lecture 3: Race Detection
- Efficient Detection of Determinacy Races in Cilk Programs:
(ps)
- Detecting Data Races in Cilk Programs that Use Locks:
(pdf)
- The LCA Problem Revisited:
(ps)
- Lecture 4: Consistency
- Using Cache Memory to Reduce Processor-Memory Traffic (MESI
protocol), Goodman: (pdf)
- How to Make a Correct Multiprocess Program Execute Correctly on a
Multiprocessor (defines Sequential Consistency), Lamport: (pdf)
- Computation-Centric Memory Models, Frigo and Luchangco: (compressed ps)
- Transactional Memory: Architectural Support for Lock-Free Data
Structures, Herlihy and Moss: (pdf)
- Data-Race Detection In Transaction Everywhere Parallel
Programming, Kai Huang: (pdf)
Week 4
- Lecture 5: Space Bounds
- Space-Efficient Scheduling of Multithreaded Computations,
Blumofe and Leiserson: (ps)
- Hoard: A Scalable Memory Allocator for Multithreaded
Applications, Berger, McKinley, Blumofe, and Wilson: (pdf)
- An Analysis of Dag-Consistent Distributed Shared-Memory
Algorithms, Blumofe, Frigo, Joerg, Leiserson, Randall: (ps)
- Space-Efficient Implementation of Nested Parallelism,
Narlikar and Blelloch: (pdf)
- A Scalable and Efficient Storage Allocator on Shared-Memory
Multiprocessors , Vee and Hsu: (pdf)
Week 5
- Lecture 6/7: Cilk Scheduler
- Executing Multithreaded Programs Efficiently, Robert
D. Blumofe: (ps.Z)
Week 6
Week 7
Week 8
Week 9
- Lecture 14: Randomized "Ski Rental" Problem
- Competitive Snoopy Caching, Karlin, Manasse, Rudolph,
and Sleator: (pdf)
- Competitive randomized algorithms for non-uniform problems,
Karlin, Manasse, McGeoch, Owicki: (pdf)
Week 10
Week 11
Week 12
Week 13
- Lecture 22: Picking Winners
- Making Commitments in the Face of Uncertainty: How to Pick a
Winner Almost Every Time Awerbuch, Azar, Fiat, Leighton: (pdf)
Week 14
Week 15
This document last modified