COMP 515: Advanced Compilation for Vector and Parallel Processors (Fall 2013)
Sherry Nassar, email@example.com, DH 3140, 713-348-2031
MLC 103 (Martel College classroom), TTh 10:50am-12:05pm
Are you curious about what makes a parallelizing compiler tick, and what program properties enable or prevent software from executing efficiently on vector and parallel computers?
This question has taken on new importance with the ubiquity of multicore processors, and the increased interest in heterogeneous accelerators such as GPGPUs and FPGAs. To answer this question, this course will cover the foundations of advanced compilation techniques for vector and parallel computer systems, including the analysis of program dependence, program transformations to enhance parallelism, compiler management of the memory hierarchy, and inter-procedural data flow analysis. At the conclusion of the course, the students should be knowledgeable about the strengths and limitations of state-of-the-art compilers, both from the viewpoint of the compiler user as well as of the compiler designer. The techniques taught in the course should be relevant to anyone interested in enabling software to execute efficiently on vector and parallel computers, whether by hand or through the use of compilers.
Required Prerequisite: COMP 412 or equivalent
NOTE: topics for future lectures may be updated during the semester as the course progresses
- Lecture 1 (08/27/2013, Profs. Palem & Sarkar): Compiler Challenges for High Performance Architectures (Chapter 1)
- Lecture 2 (08/29/2013, Prof. Palem): Dependence: Theory and Practice (Chapter 2), Homework 1 assigned, due by 09/05/2013
- Lecture 3 (09/03/2013, Prof. Palem): Dependence: Theory and Practice (Chapter 2, contd)
- Lecture 4 (09/05/2013, Prof. Palem): Dependence Testing (Chapter 3)
- Lecture 5 (09/10/2013, Prof. Sarkar): Dependence Testing (Chapter 3, contd)
- Lecture 6 (09/12/2013, Prof. Sarkar): Dependence Testing (Chapter 3, contd), Homework 2 assigned, due by 09/24/2013
- No class (09/17/2013, self study): Prepare project proposal
- No class (09/19/2013, self study): Prepare project proposal
- Lecture 7 (09/24/2013, Prof. Sarkar): Dependence Testing (Chapter 3, contd), Preliminary Transformations (Chapter 4)
- Lecture 8 (09/26/2013, Prof. Sarkar): Preliminary Transformations (Chapter 4, contd), Homework 3 due by 10/08/2013
- Lectures 9 & 10 (10/01/2013 & 10/03/2013, Prof. Sarkar): Vectorization Algorithm (Chapter 2, contd), Enhancing Fine-Grained Parallelism (Chapter 5)
- Lecture 11 (10/08/2013, Prof. Sarkar): Enhancing Fine-Grained Parallelism (Chapter 5, contd), Homework 4 due by 10/17/2013
- Lecture 12 (10/10/2013, Prof. Sarkar): Enhancing Fine-Grained Parallelism (Chapter 5, contd), Coarse-Grained Parallelism (Chapter 6)
- Lecture 13 (10/21/2013, Prof. Sarkar): Coarse-Grained Parallelism (Chapter 6, contd)
- Lecture 14 (10/22/2013, Prof. Sarkar): Coarse-Grained Parallelism (Chapter 6, contd), Midterm Review
- Lecture 15 (10/24/2013, Prof. Palem): Control Dependence (Chapter 7)
- Lecture 16 (10/29/2013, Prof. Palem): Control Dependence (Chapter 7, contd)
- Lecture 17 (10/31/2013, Prof. Palem): Compiler Improvement of Register Usage (Chapter 8)
- Lecture 18 (11/05/2013, Prof. Palem): Compiler Improvement of Register Usage (Chapter 8, contd)
- Lecture 19 (11/07/2013, Prof. Palem): Managing Cache (Chapter 9)
- Lecture 20 (11/12/2013, Prof. Palem): Managing Cache (Chapter 9, contd)
- Lecture 21 (11/14/2013, Prof. Sarkar): Unimodular Transformations
- Lecture 22 (11/19/2013, Prof. Palem): Interprocedural Analysis and Optimization (Chapter 11)
- Lecture 23 (11/21/2013, Prof. Palem): Compiling Array Assignments (Chapter 13)
- Lecture 24 (11/26/2013, Prof. Sarkar): End-Semester Summary (Chapters 7, 8, 9, 11, 13), Exam 2 assigned, due by 12/09/2013
- Lecture 25 (12/03/2013): Student project presentations
- Lecture 26 (12/05/2013): Student project presentations
- Course text: Optimizing Compilers for Modern Architectures, Randy Allen & Ken Kennedy.
- Automatic Selection of High Order Transformations in the IBM XL Fortran Compilers. Vivek Sarkar. IBM Journal of Research and Development, 41(3), May 1997.
- A General Framework for Iteration-Reordering Loop Transformations. Vivek Sarkar and Radhika Thekkath. Proceedings of the ACM SIGPLAN 1992 Conference on Programming Language Design and Implementation (PLDI), San Francisco, California, pages 175-187, June 1992.
- Optimal Weighted Loop Fusion for Parallel Programs. Nimrod Megiddo and Vivek Sarkar. Proceedings of the Ninth Annual ACM Symposium on Parallel Algorithms and Architecture (SPAA), Newport, Rhode Island, June, 1997, pages 282-291.
- Array SSA form and its use in Parallelization. Kathleen Knobe and Vivek Sarkar. Proceedings of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, San Diego, California, January 1998.
Grading, Honor Code Policy, Processes and Procedures
Grading will be based on your performance on six homeworks (weighted 25% in all), one class project to be done in pairs (weighted 35%), and two exams (weighted 20% each). Each project team will be expected to give a one-hour presentation on their project at the end of the semester (Dec 3 or Dec 5), and to submit a report by December 13, 2013.
The purpose of the homeworks is to train you to solve problems and to help deepen your understanding of concepts introduced in class. Homeworks are due on the dates and times specified in the course schedule. Homework is worth full credit when turned in on time. A 10% penalty per day will be levied on late homeworks, up to a maximum of 6 days. No submissions will be accepted more than 6 days after the due date. If you believe we have made an error in grading your homework or exam, please bring the matter to our attention within one week after you receive the graded material.
You will be expected to follow the Honor Code in all homeworks and exams. All submitted homeworks are expected to be the result of your individual effort. You are free to discuss course material and approaches to homework problems with your other classmates, the teaching assistants and the professor, but you should never misrepresent someone else's work as your own. If you use any material from external sources, you must provide proper attribution (as shown here). Exams 1 and 2 are pledged under the Honor Code. They test your individual understanding and knowledge of the material. Collaboration on exams is strictly forbidden. Finally, it is also your responsibility to protect your homeworks and exams from unauthorized access.
If you believe we have made an error in grading your homework or exam, please bring the matter to our attention within one week.
Accommodations for Students with Special Needs
Students with disabilities are encouraged to contact us during the first two weeks of class regarding any special needs. Students with disabilities should also contact Disabled Student Services in the Ley Student Center and the Rice Disability Support Services.