Compilation of Structured Polyhedral Equations

Abstract—The polyhedral model is an established mathemat-ical formalism for automatic parallelization of an important class of programs. In 1989, Mauras defined ALPHA, a poly-hedral equational language based on systems of affine recur-rence equations over polyhedral domains. In 1995, Dupont de Dinechin introduced subsystems in ALPHA to allow modularity and structured programming. Such hierarchical structure is now regaining importance when polyhedral programs are tiled with parametric tile sizes. Such tiling transformations are non-linear, and render the program representation “out of the scope ” of polyhedral representation. Current approaches apply them at the final, code-generation step. Structured polyhedral programs offer an alternative solution, the ability to work with a polyhedral specification of programs with parametric tile sizes. This paper addresses the issue of code generation and compilation of such structured ALPHA programs. We implement this in our polyhedral transformation framework (AlphaZ). We also give examples to illustrate the ability to express the complex programs and to demonstrate the code generation. I