Array access analysis
Encyclopedia
In computer science
, array access analysis is a compiler analysis used to decide the read and write access patterns to elements or portions of arrays.
The major data type manipulated in scientific programs is the array. The define/use analysis on a whole array is insufficient for aggressive compiler optimization
s such as auto parallelization and array privatization. Array access analysis aims to obtain the knowledge of which portions or even which elements of the array are accessed by a given code segment (basic block
, loop, or even at the procedure
level).
Array access analysis can be largely categorized into exact (or reference-list-based) and summary methods for different tradeoffs of accuracy and complexity. Exact methods are precise but very costly in terms of computation and space storage, while summary methods are approximate but can be computed quickly and economically.
Typical exact array access analysis include linearization and atom images. Summary methods can be further divided into array sections, bounded regular sections using triplet notation, linear-constraint methods such as data access descriptors and array region analysis.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, array access analysis is a compiler analysis used to decide the read and write access patterns to elements or portions of arrays.
The major data type manipulated in scientific programs is the array. The define/use analysis on a whole array is insufficient for aggressive compiler optimization
Compiler optimization
Compiler optimization is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the amount of memory occupied...
s such as auto parallelization and array privatization. Array access analysis aims to obtain the knowledge of which portions or even which elements of the array are accessed by a given code segment (basic block
Basic block
In computing, a basic block is a portion of the code within a program with certain desirable properties that make it highly amenable to analysis. Compilers usually decompose programs into their basic blocks as a first step in the analysis process...
, loop, or even at the procedure
Subroutine
In computer science, a subroutine is a portion of code within a larger program that performs a specific task and is relatively independent of the remaining code....
level).
Array access analysis can be largely categorized into exact (or reference-list-based) and summary methods for different tradeoffs of accuracy and complexity. Exact methods are precise but very costly in terms of computation and space storage, while summary methods are approximate but can be computed quickly and economically.
Typical exact array access analysis include linearization and atom images. Summary methods can be further divided into array sections, bounded regular sections using triplet notation, linear-constraint methods such as data access descriptors and array region analysis.