Accurate Analysis of Array References
Abstract
This thesis addresses the problem of data dependence analysis, the base step in detecting loop level parallelism in scientific programs. Traditional data dependence analysis research has concentrated on the simpler problem of affine memory disambiguation. Many algorithms have been developed that conservatively approximate even this simpler problem. Using a series of algorithms, each one guaranteed to be exact for a certain class of input, we are able to devise a new method that in practice solves exactly and efficiently the affine memory disambiguation problem. Because our system is exact, we can devise an experiment to test the effectiveness of affine memory disambiguation at approximating the full dependence problem. We discover that the lack of dataflow information on array elements is the key limitation of affine memory disambiguators. We develop a new representation and algorithm to efficiently calculate these data-flow dependences. Finally, we address the problem of interprocedural data dependence analysis. By using an array summary representation that is guaranteed to be exact when applicable, we can combine summaries with inlining to exactly and efficiently analyze affine array references across procedure boundaries. Taken together, our algorithms generate the more accurate information that will be needed to exploit parallelism in the future.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 22, 1992
- Accession Number
- ADA268069
Entities
People
- Dror E. Maydan
Organizations
- Stanford University