Keynote at IMPACT'11 workshop

Approximations in the polyhedral model

The polyhedral model is often viewed as limited, by nature, to a restricted class of programs, the set of nested loops with static control, affine loop counters, and affine accesses to arrays. But, actually, it is more than that. It is really a "model", in the sense that it is indeed not the real life (of programs) but it is nevertheless a useful representation that approximates it. It is always beneficial to develop transformations and optimizations in the polytope model with this perspective in mind, i.e., as being applicable to more programs, more general situations, provided that these programs are approximated in a suitable way. In this talk, I will recall several cases where the polytope model can be used to handle approximated programs: the detection of parallelism in loops with approximated dependences, the derivation of optimized communications with local reuse, the reuse of memory with lattice-based array folding, the analysis of while loops. Other important approximations, which will not be covered, concern fuzzy data-flow analysis and array region analysis, and the link with abstract interpretation.

  • Alain Darte is a senior research scientist with CNRS, leader of the Compsys team. His main scientific interests are in mathematical tools, high-level program transformations, and back-end code optimizations, for the generation of optimized programs as well as the synthesis of hardware accelerators.