High-level loop transformations and polyhedral compilation

High-level loop transformations change the order in which basic computations in a program are executed and are of great importance to achieving parallelism and optimized reuse of memory. Polyhedral compilation is a framework for analyzing and/or constructing such restructuring transformations that is widely used in high-level synthesis tools and in production compilers such as gcc/graphite, LLVM/Polly and the IBM XL compilers. This framework is based on the polyhedral model, a compact abstraction for (parts of) programs that are "sufficiently regular". The key feature of this model is that it is instance based, allowing for a representation and treatment of individual dynamic executions of a statement inside a loop nest and/or individual array elements. After a brief introduction to the application of high-level loop transformations such as loop distribution, loop fusion and loop tiling to obtain parallelism or locality, this lecture describes the core concepts behind polyhedral compilation and how they relate to loop transformations. These concepts mainly include dependence analysis, schedules and data-layout transformations. The lectures finishes with an overview of some available software and a more detailed discussion of one of these tools, an automatic parallelizer called PPCG that targets GPUs.http://www.asci.tudelft.nl/pages/courses.php?course_id=18status: publishe