Computer Science Department

CS 675: Advanced Parallel Programming
Fall 2008

Class meets: Tu-Th 9:30-10:45 AM in Engr E-202

Announcements:

Watch this space (and the Fall 2008 Schedule Page) for last minute information.

Wed July 23 (11:00 am): Asssignments will normally be announced here but details will be posted off the schedule page.

Course Overview

In this course, we will read and review papers about various program analyses for automatic parallelization in the polyhedral model.

The initial part (about the first four weeks) will follow a lecture style to introduce the background material.

The main part of the course will involve readings from the literature, discussion and presentation by students.

A major component of the course will be a related research project of the student's choosing that must involve a prototype implementation of some kind. The research project will also involve writing and presenting reports, and proposals.

This course does not involve a textbook or any exams. Prerequisites for this course include CS575, CS560 or instructor approval.

Topics and Syllabus

The course will cover the following main topics (the order may be changed and possibly interleaved). More details on the schedule page.

Foundations of the polyhedral model. This part will cover (i) equational programming; (ii) basic operations on polyhedra; (iii) closure properties; (iv) change-of-basis transformations; and (v) the Alphabets language and related software tools that we will use (the COREquations code generator(s) and the AlphaZ client).
Scheduling. This is a well researched topic, and we will cover a number of important papers, starting with Karp Miller and Winograds' 1967 classic, and move on through the work of Lamport, systolic scheduling, Allen-Kennedy, Darte-Vivien, Wolf-Lam, and Feautrier.
Imperative program analysis (aka dependence analysis). We will cover Pugh's Omega test and Feautrier's exact data-flow analysis.
Communication and Synchronization. Message vectorization, Lim-Lam, etc.
Code generation We will cover the Omega code generator, Wilde-Quillere-Rajopadhye, CLooG, etc.
Automatic parallelization systems We will cover PluTO, LOOPO, GRAPHITE, and AlphaZ.

Term Project/Paper

Your term project will be either a detailed study and associated implementation out of the papers we studied, or an implementation of some modules related to the AlphaZ system. Here is a list of suggestions (most projects will involve additional specialized readings).

Details

Instructor: Sanjay Rajopadhye USC 223, (email: Sanjay.Rajopadhye@colostate.edu), (phone: 491-7323)
Office Hours: Please see Sanjay's weekly schedule.
Tentative Grading: Assignments/Paper Critiques 30%, Project 50%, Presenting and Leading paper discusssion: 10%, Class participation: 10%.
The university calendar has scheduled the final exam on Friday, December 19, at 9:10-11:10 AM, in the classroom. This class does not have a final exam. Your final project report (the last thing that you will turn in for this class) will be due on Wednesday, December 17 at 5:00 pm.
Important Information: Be sure to read the Computer Science Department Student Information Sheet. You are expected to be aware of the policies outlined there.