Accession Number : ADA268069


Title :   Accurate Analysis of Array References


Descriptive Note : Master's thesis,


Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE


Personal Author(s) : Maydan, Dror E


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a268069.pdf


Report Date : 22 Sep 1992


Pagination or Media Count : 144


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.


Descriptors :   *DATA MANAGEMENT , *PARALLEL PROCESSING , TEST AND EVALUATION , ALGORITHMS , ARRAYS , LIMITATIONS , LOOPS , FLOW , BOUNDARIES , THESES , INPUT , COMPUTATIONS


Subject Categories : Computer Programming and Software


Distribution Statement : APPROVED FOR PUBLIC RELEASE