This course attacks the complexity of programming/designing fine-grained parallel architectures such as FPGAs and GPUs through the power of the polyhedral model. We use the a mathematical formalism called the polyhedral model to represent loop and/or equational computations, and to express transformations such as schedules and storage mappings in order to derive/generate sequential or parallel codes.
The Spring 2013 edition of this class will focus on GPUs (Graphics Processing Units) as our target architecture. We will use the "fruit machines" in the HPC Lab (CS 325) and write as well as systematically derive programs in CUDA. However, no prior CUDA/GPU experience is necessary, all that is neded will be covered in the class.
The polyhedral model is now used for automatic parallelization in a number production compilers such as gcc, 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 declarative, functional programming in the form 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 OpenMP parallel programming. Additionally, you should have a decent math 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 are NO required textbooks for this course! All required material will be posted on the web.
Here are the formally graded elements of the course and associated weighting:
|Final Project (proposal, progress report, final report, quality of work, poster,||30 % (2+3+5+15+5)|
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 a take home test that must be done individually. It will be provided online the seventh week of class at 3:30pm, Tuesday March 5 and will be DUE through electronic submission on Thursday March 7 by 1:55pm. If the midterm is late, 10% will be deducted. The midterm is more than 12 hours late it will receive a zero. If you have a family or medical emergency, let me know as soon as possible and be able to provide documentation to reschedule the midterm.
Projects: Unless otherwise specified, programming 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.
|Take home midterm||TBA|
|Project intermediate report||TBA|
|Project final paper||TBA|
All students taking this course are expected to participate actively. For all students, includes asking and responding to questions. Questions may be asked or answered in class, during office hours, or electronically.
All students are expected to conduct themselves professionally. We (the instructors and GTAs) assume you are familiar with the policies in the student information sheet for the department. Additionally, you are computing professionals, albeit perhaps just starting. 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: