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.