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 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, 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 (in-class 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 (in-class 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 | Distributed-Memory Algorithms: Dense Matrices |
|
Tue, Nov 19 | Distributed-Memory Algorithms: Dense Matrices (continued) |
|
Thu, Nov 21 | Distributed-Memory Algorithms: Sorting and Searching |
|
Tue, Nov 26 | Distributed-Memory Algorithms: Sorting and Searching (continued) | - |
Tue, Dec 3 | Distributed-Memory Algorithms: Sorting and Searching (continued) |
|
Thu, Dec 5 | Final Exam (in-class) | HW3 Due |
Programming Resources.