The Polyhedral Model Is More Widely Applicable Than You Think Mohamed-Walid Benabderrahmane 1 Louis-Noël Pouchet 1,2 Albert Cohen 1 Cédric Bastoul 1 1 ALCHEMY group, INRIA Saclay / University of Paris-Sud 11, France 2 The Ohio State University, USA
March 26, 2010
Introduction
CC 2010
Motivation: High Level Optimization Complex program transformations To exhibit and to exploit parallelism Type
implicit/explicit
Extraction
Instruction pipeline Superscalar VLIW-EPIC Vector Multithreading
implicit implicit explicit explicit explicit
hardware + compiler hardware + compiler compiler compiler compiler + system
To benefit from data locality Type
implicit/explicit
Extraction
Temporal locality Spatial locality
implicit (except on local memories) implicit (except on some DSPs)
compiler compiler
2
Introduction
CC 2010
Finding & Applying Transformations Very hard in general I Which transformations, in which order? I Is the semantics preserved? I Is it profitable (performance, energy...)?
Much easier within the scope of the polyhedral model I I I I
Complex sequences of optimizations in a single step Exact data dependence analysis Many existing optimizing algorithms But restricted to static control codes
Contributions:
I Extending the polyhedral model to handle full functions I Revisiting the framework to support these extensions I Demonstrate that codes with data-dependent control flow may benefit from existing techniques, even with conservative dependence approximations 3
Introduction
CC 2010
Outline
1
The Polyhedral Framework, Principles and Limitations
2
Extending the Polyhedral Model Analysis Transformations Code Generation
3
Experimental Results
4
Conclusion
4
The Polyhedral Framework
CC 2010
Polyhedral Representation For each program statement, capture its control array access semantics through parametrized affine (in)equalities: 1 A domain D : A~x +~a ≥ ~0 The bounds of the enclosing loops 2 A list of access functions f (~x) = F~x +~f To describe array references 3 A schedule θ(~x) = T~x +~t An affine function assigning logical dates to iterations
for (i = 1; i
