Empirical study on array subscripts and data dependencies

Results from an empirical study on array subscripts and data dependencies are reported. The state of the art in data dependence analysis and some parallel execution techniques are also examined. It is found that many subscripts contain symbolic terms with unknown values. A few methods to determine their values at compile time are evaluated. Arrays with coupled subscripts appear quite frequently. It may be necessary that all array dimensions be handled simultaneously in a dependence test, rather than just handling them separately as in current test algorithms. Nonzero coefficients of loop indices in most subscripts are found to be simple: they are either 1 or -1. This allows an exact real-valued test for one-dimensional or two-dimensional arrays. Dependencies with nonconstant distance are found to be rather common. This might have a significant impact on data synchronization, loop scheduling, and partitioning.