Simplifying Polynomial Constraints Over Integers to Make Dependence Analysis More Precise

Loading...
Thumbnail Image

Files

CS-TR-3109.1.ps (221.49 KB)
No. of downloads: 218
CS-TR-3109.1.pdf (245.56 KB)
No. of downloads: 800

Publication or External Link

Date

1998-10-15

Advisor

Citation

DRUM DOI

Abstract

Why do existing parallelizing compilers and environments fail to parallelize many realistic FORTRAN programs? One of the reasons is that these programs contain a number of linearized array references, such as {\tt A(MNi+Nj+k)} or {\tt A(i(i+1)/2+j)}. Performing exact dependence analysis for these references requires testing polynomial constraints for integer solutions. Most existing dependence analysis systems, however, restrict themselves to solving affine constraints only, so they have to make worst-case assumptions whenever they encounter a polynomial constraint. In this paper we introduce an algorithm which exactly and efficiently solves a class of polynomial constraints which arise in dependence testing. Another important application of our algorithm is to generate code for loop transformation known as symbolic blocking (tiling). (Also cross-referenced as UMIACS-TR-93-68.1)

Notes

Rights