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

Lecture Time and Location. TuTh 2:30 pm - 3:50 pm, CS 2129, West Campus

Instructor. Rezaul A. Chowdhury (rezaul{at}cs{dot}stonybrook{dot}edu)
Office Hours. TuTh 12:00 pm - 1:30 pm, 1421 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 and Trestles.

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.

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

Download the Latex template for scribe notes.

Blackboard. Some course documents will be available through Blackboard.

Lecture Schedule.

Date Topic Notes / Reading Material
Tue, Jan 26 All SBU Classes Canceled (Winter Storm) -
Thu, Jan 29 Introduction -
Tue, Feb 3 Analytical Modeling of Parallel Programs
Thu, Feb 5 The Cilk++ Concurrency Platform
Tue, Feb 10 The Cilk++ Concurrency Platform (continued)

Greedy Scheduling

Scheduling and Work Stealing (continued to next lecture)
  • 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.
  • 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.
Thu, Feb 12 Scheduling and Work Stealing (continued)
Tue, Feb 17 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.
Thu, Feb 19 No class -
Tue, Feb 24 High Probability Bounds
  • [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.
Thu, Feb 26 High Probability Bounds (continued)
Tue, Mar 3 Basic Parallel Algorithmic Techniques
  • Guy E. Blelloch and Bruce M. Maggs, “Parallel Algorithms”, The Computer Science Handbook, Editor: Allen Tucker, Chapman & Hall/CRC, 2004.
Thu, Mar 5 All SBU Classes Canceled (Winter Storm) -
Tue, Mar 10 Basic Parallel Algorithmic Techniques (continued)

Analyzing Divide-and-Conquer Algorithms
  • Chapter 2 (Basic Techniques), An Introduction to Parallel Algorithms (1992) by Joseph JáJá
  • Chapter 27 (Multithreaded Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al.
Thu, Mar 12 Analyzing Divide-and-Conquer Algorithms (continued)

Parallel Quicksort and Selection
  • Chapter 4 (Divide-and-Conquer), Introduction to Algorithms (3rd Edition) by Cormen et al.
  • Chapter 9 (Randomized Algorithms), Section 9.6.3 (A Parallel Randomized Quicksort Algorithm), An Introduction to Parallel Algorithms (1992) by Joseph JáJá
Tue, Mar 17 Spring Break -
Thu, Mar 19 Spring Break -
Tue, Mar 24 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á
Thu, Mar 26 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.
Tue, Mar 31 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.
Thu, Apr 2 Minimum Spanning Trees (and Radix Sort) (continued)
Tue, Apr 7 Minimum Spanning Trees (and Radix Sort) (continued)
Thu, Apr 9 Minimum Spanning Trees (and Radix Sort) (continued)

Maximal Independent Set
Tue, Apr 14 Cache Performance of Divide-and-Conquer Algorithms
(Lecturer: Jesmin Jahan Tithi)
Thu, Apr 16 Cache Performance of Divide-and-Conquer Algorithms (continued)
(Lecturer: Jesmin Jahan Tithi)
Tue, Apr 21 Maximal Independent Set (continued)
Thu, Apr 23 The Message Passing Interface (Lecturer: Jesmin Jahan Tithi)
  • 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
  • HW2 Due
Tue, Apr 28 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.
Thu, Apr 30 Distributed-Memory Algorithms: Dense Matrices (continued)
  • 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.
Tue, May 5 - -
Thu, May 7 - -

Programming Resources.