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

• Cilk Manual 5.3.2: (pdf)
• Minicourse on Multithreaded Programming: (compressed postscript)

Week 2

• Lecture 3 - Sorting Code Handout (ps) (latex)
• C Code for Sorting (.c)
• ASM Code for Sorting (Excerpt) (.asm)

• Cache-Oblivious Algorithms
  • Prokop's Masters Thesis: (compressed postscript)
  • FOCS Paper: (compressed postscript)

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 Wednesday, 26-Nov-2003 14:55:39 EST

For website issues, contact the [an error occurred while processing this directive] 6895-staff@theory.lcs.mit.edu Copyright © 2003, M.I.T. All rights reserved

[an error occurred while processing this directive] [an error occurred while processing this directive]