Date 
Topic 
Notes / Reading Materials 
Tue, Jan 24 
Introduction 
 
Thu, Jan 26 
Analytical Modeling of Parallel Programs 
 Chapter 5 (Analytical Modeling of Parallel Programs), Introduction to Parallel Computing (2nd Edition) by Grama et al.
 Gene Amdahl, “Validity of the Single Processor Approach to
Achieving Large Scale Computing Capabilities”, Reprinted from the proceedings of the Spring Joint Computer Conference, AIFPS vol 30, pp. 483485, 1967.
 John L. Gustafson, “Reevaluating Amdahl's Law”, Communications of the ACM, 31(5), pp. 532533, 1988.

Tue, Jan 31 
The Cilk++ Concurrency Platform 

Thu, Feb 2 
Scheduling and Work Stealing 
 Chapter 27 (Multithreaded Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al.
 Nimar S. Arora, Robert D. Blumofe, and Charles G. Plaxton, “Thread Scheduling for Multiprogrammed Multiprocessors”, Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 119129, 1998.

Tue, Feb 7 
Analysis of the WorkStealing Scheduler 
 The Arora et al. Paper from Lecture 4.

Thu, Feb 9 
High Probability Bounds 
 Torben Hagerup and Christine Rüb, “A Guided Tour of Chernoff Bounds”, Information Processing Letters, 33(6), pp. 305308, 1990. (If you are unable access the paper please check Blackboard under Documents/Misc for a local copy)

Tue, Feb 14 
Basic Parallel Algorithmic Techniques 
 Guy E. Blelloch and Bruce M. Maggs, “Parallel Algorithms”, The Computer Science Handbook, Editor: Allen Tucker, Chapman & Hall/CRC, 2004.
 Chapter 2 (Basic Techniques), An Introduction to Parallel Algorithms (1992) by Joseph JáJá

Thu, Feb 16 
Analyzing DivideandConquer Algorithms 
 Chapter 27 (Multithreaded Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al.
 Chapter 4 (DivideandConquer), Introduction to Algorithms (3rd Edition) by Cormen et al.

Tue, Feb 21 
DivideandConquer: Partitioning for Selection and Sorting 
 Chapter 9 (Randomized Algorithms), Section 9.6.3 (A Parallel Randomized Quicksort Algorithm), An Introduction to Parallel Algorithms (1992) by Joseph JáJá
 Chapter 4 (Searching, Merging, and Sorting), Section 4.5 (Selection), An Introduction to Parallel Algorithms (1992) by Joseph JáJá

Thu, Feb 23 
Cache Performance of DivideandConquer Algorithms 
 Rezaul A. Chowdhury, HaiSon Le, and Vijaya Ramachandran, “Cacheoblivious Dynamic Programming for Bioinformatics”, IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 7 (3), pp. 495510, 2010.
 Rezaul A. Chowdhury and Vijaya Ramachandran, “Cacheefficient Dynamic Programming Algorithms for Multicores”, Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 207216, 2008.
 Umut A. Acar, Guy E. Blelloch, Robert D. Blumofe, “The Data Locality of Work Stealing”,
Proceedings of the 12th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 112, 2000.

Tue, Feb 28 
Project Proposals 
 
Thu, Mar 1 
Project Proposals ( continued )
Cache Performance of DivideandConquer Algorithms ( continued ) 
 
Tue, Mar 6 
Cache Performance of DivideandConquer Algorithms ( continued ) 
 
Thu, Mar 8 
Graph Algorithms: Connected Components 
 Guy E. Blelloch and Bruce M. Maggs, “Parallel Algorithms” (Section 4.3), The Computer Science Handbook, Editor: Allen Tucker, Chapman & Hall/CRC, 2004.

Tue, Mar 13 
Graph Algorithms: Minimum Spanning Trees (and Radix Sort) 
 Guy E. Blelloch and Bruce M. Maggs, “Parallel Algorithms” (Section 4.3), The Computer Science Handbook, Editor: Allen Tucker, Chapman & Hall/CRC, 2004.
 Baruch Awerbuch and Yossi Shiloach, “New Connectivity and MSF Algorithms for ShuffleExchange Network and PRAM”, IEEE Transactions on Computers, vol. 36 (10), pp. 12581263, 1987. (excluding Section IV)
 Faith E. Fich, Prabhakar L. Ragde, and Avi Wigderson, “Relations between ConcurrentWrite Models of Parallel Computation”, SIAM Journal on Computing, vol. 17 (3), pp. 606627, 1988. (proof of Theorem 1)
 Guy E. Blelloch, Charles E. Leiserson, Bruce M. Maggs, Charles G. Plaxton, Stephen J. Smith, and Marco Zagha, “A Comparison of Sorting Algorithms for the Connection Machine CM2”, Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 316, 1991. (Section 4)

Thu, Mar 15 
Graph Algorithms: Minimum Spanning Trees (and Radix Sort) ( continued ) 
 
Tue, Mar 20 
Graph Algorithms: Minimum Spanning Trees (and Radix Sort) ( continued ),
Graph Algorithms: Maximal Independent Set 
 Michael Luby, “A Simple Parallel Algorithm for the Maximal Independent Set Problem”, Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC), pp. 110, 1985.
 Chapter 12 (Parallel and Distributed Algorithms), Section 12.3 (Maximal Independent Sets), Randomized Algorithms (1st Edition) by Rajeev Motwani and Prabhakar Raghavan.
 Guy E. Blelloch, Jeremy T. Fineman, and Julian Shun, “Greedy Sequential Maximal Independent Set and Matching
are Parallel on Average”, To Appear in the Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2012.

Thu, Mar 22 
Graph Algorithms: Maximal Independent Set ( continued ) 
 
Tue, Mar 27 
Midterm (inclass) 
 
Thu, Mar 29 
Midterm Solutions, Graph Algorithms: Maximal Independent Set ( continued ) 
 
Tue, Apr 3 Thu, Apr 5 
Spring Break 
 
Tue, Apr 10 
The Message Passing Interface 
 Chapter 6 (Programming Using the MessagePassing Paradigm), Introduction to Parallel Computing (2nd Edition) by Grama et al.
 Chapter 2 (MessagePassing Computing), Parallel Programming (2nd Edition) by Wilkinson & Allen

Thu, Apr 12 
The Message Passing Interface ( continued ) 
 
Tue, Apr 17 
DistributedMemory Algorithms: Dense Matrices 
 Chapter 2 (Parallel Programming Platforms), Section 2.5.1 (Message Passing Costs in Parallel Computers), Introduction to Parallel Computing (2nd Edition) by Grama et al.
 Chapter 4 (Basic Communication Operations), Introduction to Parallel Computing (2nd Edition) by Grama et al.
 Chapter 6 (Programming Using the MessagePassing Paradigm), Introduction to Parallel Computing (2nd Edition) by Grama et al.
 Chapter 8 (Dense Matrix Algorithms), Section 8.2.2 (Cannon's Algorithm), Introduction to Parallel Computing (2nd Edition) by Grama et al.
 Chapter 10 (Graph Algorithms), Section 10.4.2 (Floyd's Algorithm), Introduction to Parallel Computing (2nd Edition) by Grama et al.

Thu, Apr 19 
DistributedMemory Algorithms: Dense Matrices ( continued ) 
 
Tue, Apr 24 
DistributedMemory Algorithms: Sorting and Searching 
 Chapter 9 (Sorting), Section 9.5 (Bucket and Sample Sort), Introduction to Parallel Computing (2nd Edition) by Grama et al.
 Chapter 6 (Programming Using the MessagePassing Paradigm), Section 6.6.10 (Example: Sample Sort), Introduction to Parallel Computing (2nd Edition) by Grama et al.
 Chapter 11 (Search Algorithms for Discrete Optimization Problems), Sections 11.4.111.4.4 (Parallel DepthFirst Search), Introduction to Parallel Computing (2nd Edition) by Grama et al.
 John H. Reif, “DepthFirst Search is Inherently Sequential”, Information Processing Letters, vol. 20 (5), pp. 229234, 1985. (If you are unable access the paper please check Blackboard under Documents/Misc for a local copy)

Thu, Apr 26 
Concurrent Data Structures: Queues and Stacks 
 Chapter 3 (Concurrent Objects), The Art of Multiprocessor Programming (2nd Edition) by Herlihy and Shavit.
 Chapter 10 (Concurrent Queues and the ABA Problem), The Art of Multiprocessor Programming (2nd Edition) by Herlihy and Shavit.
 Chapter 11 (Concurrent Stacks and Elimination), The Art of Multiprocessor Programming (2nd Edition) by Herlihy and Shavit.

Tue, May 1 
A Brief Introduction to Transactional Memory 
 Chapter 18 (Transactioanl Memory), Section 18.1, The Art of Multiprocessor Programming (2nd Edition) by Herlihy and Shavit.
 James Larus and Christos Kozyrakis, “Transactional Memory”, Communications of the ACM, vol. 51 (7), pp. 8088, 2008.

Thu, May 3 
Optimizing Energy Consumption 

Fri, May 11 
Final Exam 
 