CSE 613 (#50842) Parallel Programming, Spring 2017

CSE 613 (#50842): Parallel Programming, Spring 2017

Lecture Time and Location. MoFr 1:00 pm - 2:20 pm, Javits 101, West Campus

Instructor. Rezaul A. Chowdhury (rezaul{at}cs{dot}stonybrook{dot}edu)
Office Hours. MoFr 3:00 pm - 4:30 pm, 239 New Computer Science Building

Course Description. We will explore algorithms and techniques for programming state-of-the-art shared-memory (e.g., multicores) and distributed-memory parallel computers. The course will include both theoretical and programming components. Topics to be covered include: analytical modeling of parallel programs, bounds on parallel performance, scheduling, synchronization, programming using the message-passing paradigm and for shared address-space platforms, parallel algorithms for dense matrix operations, sorting, searching, graphs, computational geometry, and dynamic programming, concurrent data structures, and transactional memory.

This course is supported by an educational grant from XSEDE (Extreme Science and Engineering Discovery Environment). We will use the computing environment provided by XSEDE for all homeworks and projects. Students will have access to the following supercomputing resources: Stampede, Comet and SuperMIC.

Prerequisites. Background in algorithms analysis (e.g., CSE 373 or CSE 548) and programming languages (e.g., C/C++) is required (or consent of instructor). Computer architecture background (e.g., CSE 320 or CSE 502) will be helpful, but not essential.

Recommended Textbooks.

Ananth Grama, George Karypis, Vipin Kumar, and Anshul Gupta. Introduction to Parallel Computing (2nd Edition), Addison Wesley, 2003.
Maurice Herlihy and Nir Shavit. The Art of Multiprocessor Programming (1st Edition), Morgan Kaufmann, 2008.
Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms (3rd Edition), MIT Press, 2009. (chapter 27 on Multithreaded Algorithms)
Joseph JáJá. An Introduction to Parallel Algorithms (1st Edition), Addison Wesley, 1992.
Peter Pacheco. Parallel Programming with MPI (1st Edition), Morgan Kaufmann, 1996.

Course Requirements. There will be 3 homework assignments (with both theory and programming components) and a final group project. Each student will be responsible for scribing one lecture. The course grade will be based on the following.

Homeworks: 40% (the highest score will be worth 20%, the lowest 8%, and the remaining one 12%)
Project: 45%
Scribe notes: 10%
Class paricipation and attendance: 5%

Download the Latex template for scribe notes.

Blackboard. Some course documents will be available through Blackboard.

Lecture Schedule.

Date	Topic	Notes / Reading Material
Mon, Jan 23	Introduction	-
Fri, Jan 27	Analytical Modeling of Parallel Programs	Chapter 5 (Analytical Modeling of Parallel Programs), Introduction to Parallel Computing (2nd Edition) by Grama et al.
Mon, Jan 30	Analytical Modeling of Parallel Programs (continued)	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.
Fri, Feb 3	The Cilk++ Concurrency Platform	Charles E. Leiserson, “The Cilk++ Concurrency Platform”, Proceedings of the 46th Annual Design Automation Conference (DAC), pp. 522-527, 2009. Intel Cilk++ SDK Programmer's Guide
Mon, Feb 6	The Cilk++ Concurrency Platform (continued)	Yuxiong He, Charles E. Leiserson, and William M. Leiserson“The Cilkview Scalability Analyzer”, Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 145-156, 2010.
Fri, Feb 10	The Cilk++ Concurrency Platform (continued) Greedy Scheduling Scheduling and Work Stealing (continued to next lecture)	Mingdong Feng and Charles E. Leiserson“Efficient Detection of Determinacy Races in Cilk Programs”, Proceedings of the 9th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 1-11, 1997. Matteo Frigo, Pablo Halpern, Charles E. Leiserson, and Stephen Lewin-Berlin“Reducers and other Cilk++ hyperobjects”, Proceedings of the 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 79-90, 2009. Chapter 27 (Multithreaded Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al.
Mon, Feb 13	Scheduling and Work Stealing	Chapter 27 (Multithreaded Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al.
Fri, Feb 17	Scheduling and Work Stealing (continued)	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.
Mon, Feb 20	Scheduling and Work Stealing (continued)	Umut A. Acar, Guy E. Blelloch, and 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.
Fri, Feb 24	High Probability Bounds Basic Parallel Algorithmic Techniques	[optional] Chapter 6 (Algorithms Involving Sequences and Sets), Section 6.9.2 (A Coloring Problem), Introduction to Algorithms - A Creative Approach (1st Edition) by Udi Manber. [optional] Chapter 1 (Introduction), Section 1.1 (A Min-Cut Algorithm), Randomized Algorithms (1st Edition) by Rajeev Motwani and Prabhakar Raghavan. Torben Hagerup and Christine Rüb, “A Guided Tour of Chernoff Bounds”, Information Processing Letters, 33(6), pp. 305-308, 1990. Guy E. Blelloch and Bruce M. Maggs, “Parallel Algorithms”, The Computer Science Handbook, Editor: Allen Tucker, Chapman & Hall/CRC, 2004.
Mon, Feb 27	Basic Parallel Algorithmic Techniques (continued)	Chapter 2 (Basic Techniques), An Introduction to Parallel Algorithms (1992) by Joseph JáJá
Fri, Mar 3	Analyzing Divide-and-Conquer Algorithms	Chapter 27 (Multithreaded Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al.
Mon, Mar 6	Analyzing Divide-and-Conquer Algorithms (continued)	Chapter 4 (Divide-and-Conquer), Introduction to Algorithms (3rd Edition) by Cormen et al.
Fri, Mar 10	Parallel Quicksort and Selection	Chapter 9 (Randomized Algorithms), Section 9.6.3 (A Parallel Randomized Quicksort Algorithm), An Introduction to Parallel Algorithms (1992) by Joseph JáJá
Mon, Mar 13	Spring Break	-
Fri, Mar 17	Spring Break	-
Mon, Mar 20	Parallel Quicksort and Selection (continued)	Chapter 4 (Searching, Merging, and Sorting), Section 4.5 (Selection), An Introduction to Parallel Algorithms (1992) by Joseph JáJá
Fri, Mar 24	Parallel Quicksort and Selection (continued)	-
Mon, Mar 27	Parallel 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.
Fri, Mar 31	Parallel Connected Components (continued)	-
Mon, Apr 3	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.
Fri, Apr 7	Class Canceled	-
Mon, Apr 10	Minimum Spanning Trees (and Radix Sort) (continued)	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) 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)
Fri, Apr 14	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”, In the Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2012.
Mon, Apr 17	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
Fri, Apr 21	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.
Mon, Apr 24	Distributed-Memory Algorithms: Dense Matrices (continued) Distributed-Memory Algorithms: Sorting and Searching	Chapter 10 (Graph Algorithms), Section 10.4.2 (Floyd's Algorithm), Introduction to Parallel Computing (2nd Edition) by Grama et al. 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.
Fri, Apr 28	-	-
Mon, May 1	-	-
Fri, May 5	-	-