Table of Content 
Recently Updated

AnnouncementsBlog Posts
Dec 08, 2010
Oct 07, 2010
Sep 23, 2010
Navigate space 
General Information
Lectures :
Tuesday & Thursday 11:00 AM  12:15 PM Siebel 1111
Final: Tue dec 14th 1:30 = 3:30 PM.
Contact:
Marc Snir
Siebel 4232
email: snir@illinois.edu^{}snir@illinois.edu^{}
Phone: 244 6568
URL: http://www.cs.illinois.edu/homes/snir^{}
http://www.cs.illinois.edu/homes/snir^{}
Office Hours: Tuesday 12 pm (but please check in advance)
Topic:
Theory of Parallel Computing.
Prerequisite:
CS 473 or equivalent. Previous experience in parallel computing is useful, but not required
Grade:
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
Resources:
Lecture Notes: to be made available (and corrected) as we go. Help is appreciated
Books and papers: List will grow as we go
Topics (DRAFT)
 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
 Packetrouting algorithms
 Toplogyspecific 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
Sources
Books
These books cover course material
 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.
General introduction books for parallel programming
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, AddisonWesley 2008. Good introduction
 Michael J. Quinn, Parallel Programming in C with MPI and OpenMP, McGrowHill 2003. Programming oriented
 Timothy G. Mattson, Beverly A. Sanders, Berna L. Massingill, Patterns for Parallel Programming. AddisonWesley 2004. For patternoriented people
 Ananth Grama, George Karypis, Vipin Kumar, and Anshul Gupta, Introduction to Parallel Computing (2nd Edition). AddisonWesley, 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).
More applied books
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.
Papers
Lectures
 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 911th^{}, VLSI Complexity
 Lecture 21, Nov 30thDec 2nd^{} Work Stealing