Simplifying Polynomial Constraints Over Integers to Make Dependence
Analysis More Precise
Simplifying Polynomial Constraints Over Integers to Make Dependence
Analysis More Precise
Files
Publication or External Link
Date
1998-10-15
Authors
Maslov, Vadim
Pugh, William
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(M*N*i+N*j+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)