N.: Loop transformations: convexity, pruning and optimization

High-level loop transformations are a key instrument in mapping computational kernels to effectively exploit resources in modern processor architectures. However, determining appropriate compo-sitions of loop transformations to achieve this remains a signif-icantly challenging task; current compilers may achieve signifi-cantly lower performance than hand-optimized programs. To ad-dress this fundamental challenge, we first present a convex char-acterization of all distinct, semantics-preserving, multidimensional affine transformations. We then bring together algebraic, algorith-mic, and performance analysis results to design a tractable opti-mization algorithm over this highly expressive space. The frame-work has been implemented and validated experimentally on a representative set of benchmarks run on state-of-the-art multi-core platforms. Categories and Subject Descriptors D 3.4 [Programming lan