Lecture Time and Location. MF 1:00 pm  2:20 pm, Room 2120 (Old Computer Science Building), West Campus
Instructor. Rezaul A. Chowdhury (rezaul{at}cs{dot}stonybrook{dot}edu)
Office Hours. M 4:00 pm  5:30 pm, F 6:00 pm  7:30 pm, 239 New 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 (not final yet): Stampede 2 and Comet.
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 
Mon, Jan 28  Introduction   
Fri, Feb 1  Class Canceled   
Mon, Feb 4  Introduction (continued)   
Fri, Feb 8  Analytical Modeling of Parallel Programs 

Mon, Feb 11  Analytical Modeling of Parallel Programs (continued) The Cilk++ Concurrency Platform 

Fri, Feb 15  The Cilk++ Concurrency Platform (continued) 

Mon, Feb 18  The Cilk++ Concurrency Platform (continued) 

Fri, Feb 22  The Cilk++ Concurrency Platform (continued) Greedy Scheduling Analysis of a Work Stealing Scheduler 

Mon, Feb 25  Analysis of a Work Stealing Scheduler (continued) 

Fri, Mar 1  Introduction to OpenMP (Guest Lecturer: Md. Abdullah Shahneous Bari) 
 
Mon, Mar 4  Introduction to OpenMP (continued) (Guest Lecturer: Md. Abdullah Shahneous Bari) 
 
Fri, Mar 8  Analysis of a Work Stealing Scheduler (continued) High Probability Bounds 

Mon, Mar 11  Analysis of a Work Stealing Scheduler (continued) Basic Parallel Algorithmic Techniques 

Fri, Mar 15  Basic Parallel Algorithmic Techniques (continued) 

Mon, Mar 18  Spring Break   
Fri, Mar 22  Spring Break   
Mon, Mar 25  Basic Parallel Algorithmic Techniques (continued) Analyzing DivideandConquer Algorithms 

Fri, Mar 29  Analyzing DivideandConquer Algorithms (continued) Parallel Quicksort and Selection 

Mon, Apr 1  Parallel Quicksort and Selection (continued) 

Fri, Apr 5  The Message Passing Interface (Guest Lecturer: Zafar Ahmad) 

Mon, Apr 8  Parallel Quicksort and Selection (continued) Parallel Connected Components 

Fri, Apr 12  Parallel Connected Components (continued) Minimum Spanning Trees (and Radix Sort) 

Mon, Apr 15  Minimum Spanning Trees (and Radix Sort) (continued) 

Fri, Apr 19  Minimum Spanning Trees (and Radix Sort) (continued) 

Mon, Apr 22  Maximal Independent Set 

Fri, Apr 26  DistributedMemory Algorithms: Dense Matrices 

Mon, Apr 29  DistributedMemory Algorithms: Dense Matrices (continued) 

Fri, May 3  DistributedMemory Algorithms: Sorting and Searching 

Mon, May 6  DistributedMemory Algorithms: Sorting and Searching (continued) 

Fri, May 10  Concurrent Data Structures: Queues and Stacks 
