Theory of Parallel Computing

Course Overview: This course will cover all the topics mentioned below

·         Circuit model of computation

o    presentation and discussion

o    metrics: work, depth, speedup, efficiency

o    Brent's theorem

·         IO complexity and pebbling games

o    Red/blue pebbling, lower bounds

o    Simple model of communication complexity, lower bounds

o    Graph properties, expanders, bisection...

·         Algebraic circuits

o    reduction and parallel prefix circuits

·         PRAM model

o    linked list parallel prefix and symmetry breaking

·         postal model, LogP model and variations

o    collective communication

·         Packet-routing algorithms

·         Toplogy-specific algorithms (butterflies, hypercubes and meshes)

o    sorting and routing

·         Coordination with shared memory

o    work stealing

o    distributed coordination , diffracting trees, sorting networks

·         Possible additions

o    PRAM simulation on networks

o    NESL simulation

o    Systolic algorithms

o    Complexity classes, P and NC

o    Quantum computing

Download PDF Lectures

1. Lecture 1 Aug 24th  Circuits, Brent Theorem, Communication complexity
2. Lecture 2 Aug 26th  Communication Complexity
3. Lecture 3 Aug 31st Algebraic circuits, reduction and scan
4. Lecture 4 Sept 2, lower bounds on scan, optimal depth scan
5. Lecture 5, Sept 7, Existence of expanders.
6. Lecture 6, Sept 9. Expanders and linear algebra
7. Lecture 7, Sept 16. PRAM, APRAM
8. Lecture 8, Sept 21st. Scan on linked list
9. Lecture 9, Sept 23rd. Optimal deterministic scan
10. Lecture 10, Sept 28th, Complete proof (rebalancing with expanders)
11. Lecture 11, Sept 30, PRAM algorithms -- connectivity
12. Lecture 12, Oct 5th, Communication complexity (I/O complexity)
13. Lecture 13, Oct 7th, Communication complexity (permutations, sorting, transpose, FFT)
14. Lecture 14, Oct 12th., Sorting Networks
15. Lecture 15th, Oct 14th, AKS Sorting Network
16. Lecture 16th, Oct 19th, Cole's logarithmic sorting
17. Lecture 17th Oct 21st. Routing, l.b. on deterministic routing
18. Lecture 18th, Oct 26th, Randomized routing
19. Lecture 19th Oct 28th, Nov 2  Butterfly randomized sorting
20. Lecture 20 Nov 9-11th, VLSI Complexity
21. Lecture 21, Nov 30th-Dec 2nd Work Stealing