CSE 590 (#50569): Topics in Computer Science (Supercomputing), Spring 2012

Lecture Time and Location. TuTh 5:20 pm - 6:40 pm, Earth & Space 069, 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

Grader. Gaurav Menghani

Course Description. We will explore algorithms and techniques for programming on various state-of-the-art parallel computing platforms. The course will be split into two parts. The first part will consist of 10-15 lectures with 2-3 lectures devoted to each of the following five topics.

  1. Shared-memory parallelism (and Cilk)
  2. Distributed-memory parallelism (and MPI)
  3. GPGPU computing (and CUDA)
  4. MapReduce and Hadoop
  5. Cloud computing
During the the second part of the course students will present interesting research papers in areas covered in the class as well as on cache-efficient and energy-efficient computations.

The course will have a significant programming component in the form of programming assignments and a final group project.

This course is supported by educational grants from AWS (Amazon Web Services) and XSEDE (Extreme Science and Engineering Discovery Environment). We will use the computing environments provided by these two services for all homeworks and projects.

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 Texts. No specific textbook will be followed. However, here is a list of some useful books.

  1. Ananth Grama, George Karypis, Vipin Kumar, and Anshul Gupta. Introduction to Parallel Computing (2nd Edition), Addison Wesley, 2003.
  2. Maurice Herlihy and Nir Shavit. The Art of Multiprocessor Programming (1st Edition), Morgan Kaufmann, 2008.
  3. Peter Pacheco. Parallel Programming with MPI (1st Edition), Morgan Kaufmann, 1996.
  4. David Kirk and Wen-mei Hwu. Programming Massively Parallel Processors: A Hands-on Approach (1st Edition), Morgan Kaufmann, 2010.
  5. Jimmy Lin and Chris Dyer. Data-Intensive Text Processing with MapReduce, Morgan and Claypool Publishers, 2010.
  6. Tom White. Hadoop: The Definitive Guide (2nd Edition), Yahoo Press, 2010.
  7. Toby Velte, Anthony Velte, and Robert Elsenpeter. Cloud Computing, A Practical Approach (1st Edition), McGraw-Hill Osborne Media, 2009.

Course Requirements. During the first part of the course there will be 4 programming assignments. During the second part each student will present one paper (at most 1 hour), write a report on a paper presented by another student, and complete a group project. The group project will also include three group presentations: one 10-15 min project proposal at the start of the 6th week of classes, one 10-15 min project progress report presentation after spring break, and one 25-30 min project presentation towards the end of the course. The course grade will be based on the following.

Blackboard. Some course documents (e.g., homework assignments) will be available through Blackboard. The following documents have already been uploaded.

Programming Resources.

Lecture Schedule.

Date Topic Notes / Reading Materials
Tue, Jan 24 Introduction -
Thu, Jan 26 Analytical Modeling and Limits of Parallelism
Tue, Jan 31 The Cilk++ Concurrency Platform
Thu, Feb 2 Analyzing Multithreaded Algorithms
  • Chapter 27 (Multithreaded Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al.
  • Chapter 4 (Divide-and-Conquer), Introduction to Algorithms (3rd Edition) by Cormen et al.
Tue, Feb 7 The Message Passing Interface
  • Chapter 6 (Programming Using the Message-Passing Paradigm), Introduction to Parallel Computing (2nd Edition) by Grama et al.
  • Chapter 2 (Message-Passing Computing), Parallel Programming (2nd Edition) by Wilkinson & Allen
Thu, Feb 9 Analyzing Distributed Memory Algorithms
  • Chapter 2 (Parallel Programming Platforms), Section 2.5.1 (Message Passing Costs in Parallel Computers), Introduction to Parallel Computing (2nd Edition) by Grama et al.
  • Chapter 4 (Basic Communication Operations), Introduction to Parallel Computing (2nd Edition) by Grama et al.
  • Chapter 6 (Programming Using the Message-Passing Paradigm), Introduction to Parallel Computing (2nd Edition) by Grama et al.
Tue, Feb 14
Thu, Feb 16		 GPGPU Computing & CUDA
Tue, Feb 21
Thu, Feb 23		 MapReduce & Hadoop
Tue, Feb 28
Thu, Mar 1		 Project Proposals -
Tue, Mar 6 Paper Presentation -
Thu, Mar 8 Paper Presentation -
Tue, Mar 13 Paper Presentation -
Thu, Mar 15 Paper Presentation -
Tue, Mar 20 Paper Presentation -
Thu, Mar 22 Paper Presentation -
Tue, Mar 27 Paper Presentation -
Thu, Mar 29 Paper Presentation -
Tue, Apr 3
Thu, Apr 5		 Spring Break -
Tue, Apr 10
Thu, Apr 12		 Project Progress Reports -
Tue, Apr 17 Paper Presentation -
Thu, Apr 19 Paper Presentation -
Tue, Apr 24 Paper Presentation -
Thu, Apr 26 Paper Presentation -
Tue, May 1 Paper Presentation -
Thu, May 3 Paper Presentation -

Homeworks.

Projects.