Optimistic Delinearization of Parametrically Sized Arrays
Optimistic Delinearization of Parametrically Sized Arrays
复制标题
参数大小数组的乐观去线性化
DOI：
10.1145/2751205.2751248
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Sebastian Pop
中科院分区：
文献类型：
--
作者：
T. Grosser;J. Ramanujam;L. Pouchet;P. Sadayappan;Sebastian Pop
许多传统代码利用线性化的数组引用（即，对一维数组的引用）来编码对多维数组的访问。这也适用于许多优化的库和众所周知的LLVM中间表示，它们将数组访问线性化。在许多情况下，唯一可用的信息是数组基指针和一维偏移量。对于参数数组范围的问题，此偏移量通常是一个多变量多项式。由于不能使用具有整数线性规划（ILP）求解器的标准公式，因此阻碍了诸如数据依赖性分析之类的数据分析。在本文中，我们提出了一种去线性化的方法，即，恢复对参数大小的数组的访问的多维性质。在静态信息不足的情况下，所开发的算法产生运行时的条件，以验证恢复的多维形式。获得的访问描述提高了数据依赖分析的精度。在LLVM/Polly系统的背景下，使用一些基准测试的实验评估揭示了显着的性能优势，由于依赖分析的精度提高，并增强优化的机会，利用后的编译器去线性化。
A number of legacy codes make use of linearized array references (i.e., references to one-dimensional arrays) to encode accesses to multi-dimensional arrays. This is also true of a number of optimized libraries and the well-known LLVM intermediate representation, which linearize array accesses. In many cases, the only information available is an array base pointer and a single dimensional offset. For problems with parametric array extents, this offset is usually a multivariate polynomial. Compiler analyses such as data dependence analysis are impeded because the standard formulations with integer linear programming (ILP) solvers cannot be used. In this paper, we present an approach to delinearization, i.e., recovering the multi-dimensional nature of accesses to arrays of parametric size. In case of insufficient static information, the developed algorithm produces run-time conditions to validate the recovered multi-dimensional form. The obtained access description enhances the precision of data dependence analysis. Experimental evaluation in the context of the LLVM/Polly system using a number of benchmarks reveals significant performance benefits due to increased precision of dependence analysis and enhanced optimization opportunities that are exploited by the compiler after delinearization.