Lecture Time and Location. TuTh 10:00 am  11:20 am, Melville Library N4006, West Campus
Instructor. Rezaul A. Chowdhury (rezaul{at}cs{dot}stonybrook{dot}edu)
Office Hours. TuTh 12:30 pm  2:00 pm, 1421 Computer Science Building
Course Description. We will explore algorithms and techniques for programming stateoftheart sharedmemory (e.g., multicores) and distributedmemory 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 messagepassing paradigm and for shared addressspace 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, Kraken, Lonestar, Trestles and Keeneland.
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.
Course Requirements. There will be 3 homework assignments (with both theory and programming components), one exam (inclass final), and a final group project. Each student will be responsible for scribing one lecture. The course grade will be based on the following.
Blackboard. Some course documents will be available through Blackboard.
Lecture Schedule.
Date  Topic  Notes / Reading Material 
Tue, Aug 27  Introduction   
Thu, Aug 29  Introduction (continued)   
Thu, Sep 5  Analytical Modeling of Parallel Programs 

Tue, Sep 10  Analytical Modeling of Parallel Programs (continued) The Cilk++ Concurrency Platform 

Thu, Sep 12  The Cilk++ Concurrency Platform (continued) 

Tue, Sep 17  The Cilk++ Concurrency Platform (continued) 

Thu, Sep 19  Scheduling and Work Stealing 

Tue, Sep 24  Scheduling and Work Stealing (continued) Parallel Matrix Multiplication and Mergesort 

Thu, Sep 26  Parallel Matrix Multiplication and Mergesort (continued) 

Tue, Oct 1  The Master Theorem 

Thu, Oct 3  Parallel Quicksort and Selection 

Tue, Oct 8  Parallel Quicksort and Selection (continued) 

Thu, Oct 10  Parallel Quicksort and Selection (continued) 

Tue, Oct 15  Parallel Connected Components 

Thu, Oct 17  Parallel Connected Components (continued) 

Tue, Oct 22  Parallel Connected Components (continued) 

Thu, Oct 24  Project Progress Report (inclass presentation)   
Tue, Oct 29  Graph Algorithms: Minimum Spanning Trees (and Radix Sort) 

Thu, Oct 31  Graph Algorithms: Minimum Spanning Trees (and Radix Sort) (continued)   
Tue, Nov 5  Graph Algorithms: Minimum Spanning Trees (and Radix Sort) (continued)   
Thu, Nov 7  Graph Algorithms: Minimum Spanning Trees (and Radix Sort) (continued)   
Tue, Nov 12  The Message Passing Interface (Guest Lecturer: Jesmin Jahan Tithi) 

Thu, Nov 14  DistributedMemory Algorithms: Dense Matrices 

Tue, Nov 19  DistributedMemory Algorithms: Dense Matrices (continued) 

Thu, Nov 21  DistributedMemory Algorithms: Sorting and Searching 

Tue, Nov 26  DistributedMemory Algorithms: Sorting and Searching (continued)   
Tue, Dec 3  DistributedMemory Algorithms: Sorting and Searching (continued) 

Thu, Dec 5  Final Exam (inclass)  HW3 Due 
Programming Resources.