Semi-Automatic Composition of Loop Transformations for Deep Parallelism and Memory Hierarchies
Semi-Automatic Composition of Loop Transformations for Deep Parallelism and Memory Hierarchies
复制标题
DOI：
10.1007/s10766-006-0012-3
复制
发表时间：
2006-06
影响因子：
1.5
通讯作者：
Sylvain Girbal;Nicolas Vasilache;Cédric Bastoul;Albert Cohen;David Parello;Marc Sigler;O. Temam
中科院分区：
文献类型：
--
作者：
Sylvain Girbal;Nicolas Vasilache;Cédric Bastoul;Albert Cohen;David Parello;Marc Sigler;O. Temam
现代编译器负责将源程序的理想操作语义转换成一种形式，从而有效地利用高度复杂的异构机器。由于优化问题与巨大的和非结构化的搜索空间相关联，这种组合任务通常很难实现，导致可扩展性差和令人失望的持续性能。我们解决这一挑战的工作程序表示本身，使用半自动优化的方法来证明，目前的编译器经常遭受不必要的约束和复杂性，可以避免在语义上更丰富的转换框架。从技术上讲，本文的目的有三个方面：（1）示出接近操作语义的语法代码表示导致体系结构感知循环变换的严格的阶段排序和繁琐的表达，（2）示出可能需要多么复杂的变换序列来实现显著的性能益处，（3）便于自动搜索程序变换序列，改进了经典的多面体表示，以更好地支持更简单，结构化的搜索空间中的运筹学策略。建议的框架依赖于一个统一的多面体表示的循环和语句，使用规范化规则，允许灵活和富有表现力的转换排序。这种表示允许扩展多面体依赖分析的可扩展性，并延迟（自动）合法性检查，直到转换序列结束。我们的工作利用多面体代码生成算法的进步，并已在现代研究编译器中实现。
Modern compilers are responsible for translating the idealistic operational semantics of the source program into a form that makes efficient use of a highly complex heterogeneous machine. Since optimization problems are associated with huge and unstructured search spaces, this combinational task is poorly achieved in general, resulting in weak scalability and disappointing sustained performance. We address this challenge by working on the program representation itself, using a semi-automatic optimization approach to demonstrate that current compilers offen suffer from unnecessary constraints and intricacies that can be avoided in a semantically richer transformation framework. Technically, the purpose of this paper is threefold: (1) to show that syntactic code representations close to the operational semantics lead to rigid phase ordering and cumbersome expression of architecture-aware loop transformations, (2) to illustrate how complex transformation sequences may be needed to achieve significant performance benefits, (3) to facilitate the automatic search for program transformation sequences, improving on classical polyhedral representations to better support operation research strategies in a simpler, structured search space. The proposed framework relies on a unified polyhedral representation of loops and statements, using normalization rules to allow flexible and expressive transformation sequencing. Thisrepresentation allows to extend the scalability of polyhedral dependence analysis, and to delay the (automatic) legality checks until the end of a transformation sequence. Our work leverages on algorithmic advances in polyhedral code generation and has been implemented in a modern research compiler.