Efficient and exact data dependence analysis
Dror E. Maydan, John LeRoy Hennessy, Monica S. Lam · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · 1991
Data dependence testing is the basic step in detecting loop level parallelism in numerical programs. The problem is equivalent to integer linear programming and thus in general cannot be solved efficiently. Current methods in use employ inexact methods that sacrifice potential parallelism in order to improve compiler efficiency. This paper shows that in practice, data dependence can be computed exactly and efficiently. There are three major ideas that lead to this result. First, we have developed and assembled a small set of efficient algorithms, each one exact for special case inputs. Combined with a moderately expensive backup test, they are exact for all the cases we have seen in practice. Second, we introduce a memorization technique to save results of previous tests, thus avoiding calling the data dependence routines multiple times on the same input. Third, we show that this approach can both be extended to compute distance and direction vectors and to use unknown symbolic terms without any loss of accuracy or efficiency, We have implemented our algorithm in the SUIF system, a general purpose compiler system developed at Stanford. We ran the algorithm on the PERFECT Club Benchmarks and our data dependence analyzer gave an exact solution in all cases efficiently.
Cited by 215 works. doi:10.1145/113445.113447
Authors
References
- Theory of Linear and Integer Programming
- Structure and Interpretation of Computer Programs
- Integer Programming with a Fixed Number of Variables
- Optimizing supercompilers for supercomputers
- Automatic translation of FORTRAN programs to vector form
- The Perfect Club Benchmarks: Effective Performance Evaluation of Supercomputers
- Dependence Analysis for Supercomputing
- Speedup of ordinary programs
- Minkowski's Convex Body Theorem and Integer Programming
- Interprocedural dependence analysis and parallelization