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.
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 Divide-and-Conquer Algorithms |
|
Thu, Mar 12 | Analyzing Divide-and-Conquer 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 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) |
|
Tue, Apr 28 | Distributed-Memory Algorithms: Dense Matrices |
|
Thu, Apr 30 | Distributed-Memory Algorithms: Dense Matrices (continued) |
|
Tue, May 5 | - | - |
Thu, May 7 | - | - |
Programming Resources.