Paper Info
Title
Optimistic Delinearization of Parametrically Sized Arrays
Abstract
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.
Year
DOI
Venue
2015
10.1145/2751205.2751248
International Conference on Supercomputing
Keywords
Field
DocType
polyhedral analysis, linear memory layout, multi-dimensional arrays
ENCODE,Pointer (computer programming),Computer science,Parallel computing,Dependence analysis,Compiler,Real-time computing,Parametric statistics,Integer programming,Parametric array,Offset (computer science)
Conference
Citations 
PageRank 
References 
6
0.45
6
Authors
5
Name
Order
Citations
PageRank
Tobias Grosser127116.04
Sebastian Pop260.45
Louis-noël Pouchet388047.61
P. Sadayappan44821344.32
Sebastian Pop5191.51