Experiences with Constraint-based Array Dependence Analysis

Loading...
Thumbnail Image

Files

CS-TR-3371.ps (184.42 KB)
No. of downloads: 271
CS-TR-3371.pdf (227.6 KB)
No. of downloads: 1001

Publication or External Link

Date

1998-10-15

Advisor

Citation

DRUM DOI

Abstract

Array data dependence analysis provides important information for optimization of scientific programs. Array dependence testing can be viewed as constraint analysis, although traditionally general-purpose constraint manipulation algorithms have been thought to be too slow for dependence analysis. We have explored the use of exact constraint analysis, based on Fourier's method, for array data dependence analysis. We have found these techniques can be used without a great impact on total compile time. Furthermore, the use of general-purpose algorithms has allowed us to address problems beyond traditional dependence analysis. In this paper, we summarize some of the constraint manipulation techniques we use for dependence analysis, and discuss some of the reasons for our performance results. (Also cross-referenced as UMIACS-TR-94-122)

Notes

Rights