Theory of Parallel Computing

Skip to end of metadata
Go to start of metadata

Table of Content

Recently Updated


Blog Posts

  • Blog post: Course Survey created by
    Dec 08, 2010
  • Blog post: Lectures 10-12 created by
    Oct 07, 2010
  • Blog post: Lecture 9 redux created by
    Sep 23, 2010
    Navigate space

    General Information


    Tuesday & Thursday 
11:00 AM - 12:15 PM Siebel 1111

    Final: Tue dec 14th 1:30 = 3:30 PM.


    Marc Snir  

    Siebel 4232  


    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

    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
    • 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


    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, 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).
    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.
    Unable to render {include} Couldn't find a page to include called: Papers


    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
    Enter labels to add to this page:
    Please wait 
    Looking for a label? Just start typing.