This course attacks the complexity of programming/designing fine-grained parallel architectures such as FPGAs and GPUs through the power of the polyhedral model, a mathematical formalism to (i) represent compute- and data-intensive loops and/or equations, (ii) analyze them to determine sequential or parallel schedules, and storage mappings, (iii) transform them using these schedules and storage mappings, and (iv) derive/generate sequential or parallel "codes."
The Fall 2015 edition of this class will focus on GPUs (Graphics Processing Units) and accelerators like the Intel Xeon Phi, Knights Brigge/Landing as our target architecture. We will also explore custom acclerators using Verilog on FPGA targets. For many assignments We will use the "fruit" machines in the HPC Lab (CS 325) and write, and derive programs in CUDA.
The polyhedral model is now used for automatic parallelization in a number production compilers such as gcc, llvm/Polly, IBM's XL series, and Reservoir Lab's R-Stream. There are active research groups on the polyhedral model at MIT (Amarasinghe), Illinois (Padua), Utah (Hall), Ohio State (Sayappan), Louisisana State (Ramanujam), IBM Research (Renganarayana, O'Keefe, etc.), Leiden (Kienhuis, Deprettere), Indian Institute of Science, Bangalore (Bondhugula) and many groups in France: IRISA, Rennes (Derrien, Quinton), ENS Lyon (Feautrier, Darte, Alias), Bordeaux (Barthou), INRIA (Cohen, Bastoul, Clauss, etc.)
Sanjay Rajopadhye is one of the inventors of the polyhedral model, and has been active in the field since his Ph.D. dissertation (Utah, 1986). At CSU, we take a unique view of the polyhedral model that combines the analytic quantitative power of the model with the expressivity and clean semantics of equational programming.
The official prerequisites are: either CS 453 compilers, or CS 475 parallel programming or instructor consent (e.g., if you have equivalent courses at another institution, or your background is different).
Please email/see the instructor if you do not have the prerequisites. In order to succeed in this course, you will also need (to quickly acquire) a working knowledge of C/C++ and parallel programming in OpenMP and/or CUDA. Additionally, you should have a solid background in discrete math and linear algebra.
In addition, two key ingredients are: (i) some mathematical maturity (this means that if you do not know the math, you should know how to pick it up as needed), and (ii) intellectual curiosity. Both are somewhat difficult to define, but you know it when you have it.
There is no required textbook for this course. All required material will be posted on the web. The schedule tab indicates each week's reading. You are responsible for doing the assigned reading prior to the lecture in which the material is to be covered.
Here are the formally graded elements of the course and associated weighting:
|Final Project |
(proposal, progress report, final report, work, poster)
| 30% |
Semester grades are determined by the weighted sum of points earned in each of these areas. A subjective curve (set by the instructor) is used to map points onto grades. Typically, the curve is set such that the class mean gets an B, one standard deviation above the mean is an A, one deviation below is a C, and so forth. However, the instructor retains the right to move the curve either direction. If the entire class is strong, the mean might be better than a B. Conversely, if the class as a whole is weak, the mean might be below a B.
Exams and projects will be done individually and grades assigned on an individual basis. At the discretion of the instructor, a substantial project may be done by a two-person team.
Midterm: The first midterm is in class (scheduled for Tuesday, Oct 6), and the second one is take home, that must be done individually. It be scheduled tentatively for mid November, If you have a family or medical emergency, let me know as soon as possible and be able to provide documentation to reschedule any midterm.
Projects: Unless otherwise specified, all assignments are to be submitted electronically. Specifics will be included in each assignment. Always check the assignment page for due dates. Late assignments submitted within 48 hours of the posted due date/time required will receive a 10% late penalty per 24 hour period. Electronic submission is closed 48 hours after assignments are due; students not having submitted by this time receive an automatic zero on the assignment. This late policy may be disabled for some assignments, in particular if the answer is to be discussed in class.
Exams and projects will be done individually and grades assigned on an individual basis. Further, students not already familiar with the CSU Honor Pledge should review this clear and simple pledge and always adhere to it.
All students are expected to conduct themselves professionally. We (the instructor and the GTA) assume you are familiar with the policies in the student information sheet for the department. The guidelines outlined in these documents will be followed in this course. Additionally, you are computing professionals. You should be familiar with the code of conduct for the primary professional society, ACM. You can read the ACM Code of Conduct HERE.
We work to maintain an environment supportive of learning in the classroom and laboratory. Towards that end, we require that you be courteous to and respectful of your fellow participants (i.e., classmates, instructors, GTAs and any tutors). In particular:
Midterm and Finals: Make-up exams are only given for extraordinary circumstances (e.g., illness, family emergency). Students must consult with the instructor as soon as possible, preferably before the start of the exam. Course examination dates are listed in the syllabus; be aware of them and plan accordingly.
Assignments: All assignments are to be submitted electronically through the Checkin tab. Specifics will be included in each assignment. Always check the assignment page for due dates. No late assignments will be accepted. Electronic submission is closed at the deadline when the assignment is due; students not having submitted programs receive an automatic zero on the assignment.
Any in-class midterms and the final exam will be held in the same classroom as regular lectures. While no change to the midterm dates is anticipated, the instructor reserves the right to change these dates with a weeks notice.