An Empirical Study of Fortran Programs for Parallelizing Compilers

In this paper, we report some results from an empirical study of program characteristics that are important to parallelizing compiler writers, especially in the area of data dependence analysis and program transformations. The state of the art in data dependence analysis and some parallel execution techniques are also examined. The major findings include: 1) Many subscripts contain symbolic terms with unknown values. A few methods to determine their values at compile time are evaluated. 2) Array references with coupled subscripts appear quite frequently. These subscripts must be handled simultaneously in a dependence test, rather than being handled separately as in current test algorithms. 3) Nonzero coefficients of loop indexes in most subscripts are found to be simple: they are either 1 or -1. It allows an exact real-valued test to be as accurate as an exact integer-valued test for one-dimensional or two-dimensional arrays. 4) Dependences with uncertain distance are found to be rather common, and one of the main reasons is the frequent appearance of symbolic terms with unknown values. This might have a significant impact on current techniques of data synchronization, loop scheduling, and partitioning.