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. 483-485, 1967.
- John L. Gustafson, “Reevaluating Amdahl's Law”, Communications of the ACM, 31(5), pp. 532-533, 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. 119-129, 1998.
|
Tue, Feb 7 |
Analysis of the Work-Stealing 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. 305-308, 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 Divide-and-Conquer Algorithms |
- Chapter 27 (Multithreaded Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 4 (Divide-and-Conquer), Introduction to Algorithms (3rd Edition) by Cormen et al.
|
Tue, Feb 21 |
Divide-and-Conquer: 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 Divide-and-Conquer Algorithms |
- Rezaul A. Chowdhury, Hai-Son Le, and Vijaya Ramachandran, “Cache-oblivious Dynamic Programming for Bioinformatics”, IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 7 (3), pp. 495-510, 2010.
- Rezaul A. Chowdhury and Vijaya Ramachandran, “Cache-efficient Dynamic Programming Algorithms for Multicores”, Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 207-216, 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. 1-12, 2000.
|
Tue, Feb 28 |
Project Proposals |
- |
Thu, Mar 1 |
Project Proposals ( continued )
Cache Performance of Divide-and-Conquer Algorithms ( continued ) |
- |
Tue, Mar 6 |
Cache Performance of Divide-and-Conquer 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 Shuffle-Exchange Network and PRAM”, IEEE Transactions on Computers, vol. 36 (10), pp. 1258-1263, 1987. (excluding Section IV)
- Faith E. Fich, Prabhakar L. Ragde, and Avi Wigderson, “Relations between Concurrent-Write Models of Parallel Computation”, SIAM Journal on Computing, vol. 17 (3), pp. 606-627, 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 CM-2”, Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 3-16, 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. 1-10, 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 (in-class) |
- |
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 Message-Passing Paradigm), Introduction to Parallel Computing (2nd Edition) by Grama et al.
- Chapter 2 (Message-Passing Computing), Parallel Programming (2nd Edition) by Wilkinson & Allen
|
Thu, Apr 12 |
The Message Passing Interface ( continued ) |
- |
Tue, Apr 17 |
Distributed-Memory 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 Message-Passing 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 |
Distributed-Memory Algorithms: Dense Matrices ( continued ) |
- |
Tue, Apr 24 |
Distributed-Memory 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 Message-Passing 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.1-11.4.4 (Parallel Depth-First Search), Introduction to Parallel Computing (2nd Edition) by Grama et al.
- John H. Reif, “Depth-First Search is Inherently Sequential”, Information Processing Letters, vol. 20 (5), pp. 229-234, 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. 80-88, 2008.
|
Thu, May 3 |
Optimizing Energy Consumption |
|
Fri, May 11 |
Final Exam |
- |