Dec 08, 2010
Oct 07, 2010
Sep 23, 2010
Tuesday & Thursday 11:00 AM - 12:15 PM Siebel 1111
Final: Tue dec 14th 1:30 = 3:30 PM.
Phone: 244 6568
Office Hours: Tuesday 1-2 pm (but please check in advance)
Theory of Parallel Computing.
CS 473 or equivalent. Previous experience in parallel computing is useful, but not required
80% Final 20% Homework
Homework is done individually, unless said otherwise.
What does the course teach:?
Theory of Parallel Computing
What it does not teach?
Parallel programming, parallel architectures – the practical aspects of parallelism
Why should you take it?
Parallelism is ubiquitous: and microprocessor has multiple cores; clusters, clouds, supercomputers are all around us. Any CS student should have some basic understanding of parallel computing. Any graduate student that wants to do research related to parallel computing should, IMHO, have a deeper (i.e., more theoretical) understanding of the topic. Take the course if you are in this category, or if you like theory. Don't take the course if you are allergic to theory.
What is the topic?
Parallel computing: the use of multiple concurrent threads in order to speed up computations. The main theory issue is complexity.
Concurrent computing: the coordination of concurrent threads; concurrency may be part of the problem (reactive system), or may be used for convenience. The focus is on correct and efficient coordination mechanisms
Lecture Notes: to be made available (and corrected) as we go. Help is appreciated
Books and papers: List will grow as we go
- Circuit model of computation
- presentation and discussion
- metrics: work, depth, speedup, efficiency
- Brent's theorem
- IO complexity and pebbling games
- Red/blue pebbling, lower bounds
- Simple model of communication complexity, lower bounds
- Graph properties, expanders, bisection...
- Algebraic circuits
- reduction and parallel prefix circuits
- PRAM model
- linked list parallel prefix and symmetry breaking
- postal model, LogP model and variations
- collective communication
- Packet-routing algorithms
- Toplogy-specific algorithms (butterflies, hypercubes and meshes)
- sorting and routing
- Coordination with shared memory
- work stealing
- distributed coordination , diffracting trees, sorting networks
- Possible additions
- PRAM simulation on networks
- NESL simulation
- Systolic algorithms
- Complexity classes, P and NC
- Quantum computing
- F. Thomson Leighton, Introduction to Parallel Algorithms and Architectures.Morgan Kaufmann, 1992. 831 pages. Very good theory book, focused on algorithms for specific topologies.
- Maurice Herlihy and Nir Shavit, The art of Multiprocessor Programming. Elsevier, 2008. Strong focus on shared memory programming and concurrency
- William James Dally and Brian Patrick Towles, Principles and Practices of Interconnection Networks. Morgan Kaufmann, 2004. The title says it.
- Donald E Knuth, The Art of Computer Programming; Vol. 3 / Sorting and Searching, 1973. Section 5.3.4 is a good introduction to sorting networks. Besides, nobody should graduate in CS without studying Knuth.
These books do not cover material in this course, but are useful for people with no background in parallel computing
- Calvin Lin, Larry Snyder, Principles of Parallel Programming, Addison-Wesley 2008. Good introduction
- Michael J. Quinn, Parallel Programming in C with MPI and OpenMP, McGrow-Hill 2003. Programming oriented
- Timothy G. Mattson, Beverly A. Sanders, Berna L. Massingill, Patterns for Parallel Programming. Addison-Wesley 2004. For pattern-oriented people
- Ananth Grama, George Karypis, Vipin Kumar, and Anshul Gupta, Introduction to Parallel Computing (2nd Edition). Addison-Wesley, 2003. More algorithm oriented.
- Barry Wilkinson and Michael Allen (2005) Parallel Programming (2nd Edition). Looks decent, and is soft cover.
- Bruce Lester, The art of Parallel Programming (2nd Edition). 1st World Publishing (2006).
There is also a plethora of more applied books, such as
- Clay Breshears,The Art of Concurrency: A Thread Monkey's Guide to Writing Parallel Applications. O'Reilly 2009.
- Lecture 1 Aug 24th Circuits, Brent Theorem, Communication complexity
- Lecture 2 Aug 26th Communication Complexity
- Lecture 3 Aug 31st Algebraic circuits, reduction and scan
- Lecture 4 Sept 2, lower bounds on scan, optimal depth scan
- Lecture 5, Sept 7, Existence of expanders.
- Lecture 6, Sept 9. Expanders and linear algebra
- Lecture 7, Sept 16. PRAM, APRAM
- Lecture 8, Sept 21st. Scan on linked list
- Lecture 9, Sept 23rd. Optimal deterministic scan
- Lecture 10, Sept 28th, Complete proof (rebalancing with expanders)
- Lecture 11, Sept 30, PRAM algorithms -- connectivity
- Lecture 12, Oct 5th, Communication complexity (I/O complexity)
- Lecture 13, Oct 7th, Communication complexity (permutations, sorting, transpose, FFT)
- Lecture 14, Oct 12th., Sorting Networks
- Lecture 15th, Oct 14th, AKS Sorting Network
- Lecture 16th, Oct 19th, Cole's logarithmic sorting
- Lecture 17th Oct 21st. Routing, l.b. on deterministic routing
- Lecture 18th, Oct 26th, Randomized routing
- Lecture 19th Oct 28th, Nov 2 Butterfly randomized sorting
- Lecture 20 Nov 9-11th, VLSI Complexity
- Lecture 21, Nov 30th-Dec 2nd Work Stealing