As modern machines become more and more powerful, the applications that run on these machines are getting larger and more complex. The power of the underlying hardware also comes with considerable difficulty of exploitation. This dual evolution in complexity increases the semantic gap between applications and hardware. Sophisticated program transformations (starting from high level language specifications) are crucial to alleviate this mismatch. In this class, we will study cutting edge program transformation techniques for a wide variety of applications. These techniques will apply to a wide range of domains ranging from computational science to program synthesis from high level specifications.

Topics covered in the course include the following:

• Program Analysis
• Need for analysis
• Data-flow analysis
• Control and data dependence computation
• Array data-flow analysis
• Incremental Computation
• Semantics-based editors
• Program Differentiation
• Dense Matrix Computations
• Iteration and data spaces
• Dependence tests
• Linear loop transformations
• Automatic generation of block algorithms
• Sparse Matrix Computations
• Data-centric transformations
• Relational algebra model of sparse matrix code generation
• Program Synthesis
• Code generation from Kronecker product model of block-recursive algorithms
• Automatic Differentiation

Time and Place: TR 2:55-4:10 in Upson 4135.

Lecture Notes

• 01/21 Introduction - motivation for performance enhancing transformations
• 01/23 Linear loop transformation framework for perfectly nested affine loops - transformations as matrices
• 01/28 Dependence abstractions for perfectly nested loops, code generation, primitive polyhedral algebraic tools
• 01/30 Completion procedure, Linear loop transformation framework for data locality - access normalization.
• 02/04 Linear loop transformation framework for data locality - tiling
• SPMD code specification and generation. Additional reading:
• Ancourt et al on the algebraic framework for generating SPMD code
• Bau et al on computing alignments

Handouts