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 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 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.
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.
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) 

Thu, Feb 12  Scheduling and Work Stealing (continued) 

Tue, Feb 17  Scheduling and Work Stealing (continued) 

Thu, Feb 19  No class   
Tue, Feb 24  High Probability Bounds 

Thu, Feb 26  High Probability Bounds (continued) 

Tue, Mar 3  Basic Parallel Algorithmic Techniques 

Thu, Mar 5  All SBU Classes Canceled (Winter Storm)   
Tue, Mar 10  Basic Parallel Algorithmic Techniques (continued) Analyzing DivideandConquer Algorithms 

Thu, Mar 12  Analyzing DivideandConquer Algorithms (continued) Parallel Quicksort and Selection 

Tue, Mar 17  Spring Break   
Thu, Mar 19  Spring Break   
Tue, Mar 24  Parallel Quicksort and Selection (continued) 

Thu, Mar 26  Parallel Connected Components 

Tue, Mar 31  Minimum Spanning Trees (and Radix Sort) 

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 DivideandConquer Algorithms (Lecturer: Jesmin Jahan Tithi) 

Thu, Apr 16  Cache Performance of DivideandConquer Algorithms (continued) (Lecturer: Jesmin Jahan Tithi) 

Tue, Apr 21  Maximal Independent Set (continued) 

Thu, Apr 23  The Message Passing Interface (Lecturer: Jesmin Jahan Tithi) 

Tue, Apr 28  DistributedMemory Algorithms: Dense Matrices 

Thu, Apr 30  DistributedMemory Algorithms: Dense Matrices (continued) 

Tue, May 5     
Thu, May 7     
Programming Resources.