Array data dependence analysis is the problem of determining when two computations refer to or update the same elements of an array. This information is essential for determining the legal and appropriate transformations of a program. For example, in order to run both loops of Figure 1 in parallel, we must make sure that no array element is written multiple times, or is both read and written. An element is written in iteration and read in iteration if there exist integer solutions to the equation in Figure 1 (there aren't any).
Checking for the existence of integer solutions to a set of linear constraints is an NP-complete problem. Traditionally, approximate and/or incomplete methods with fast worst-case performance have been used for dependence analysis [Wol89][Ban88]. Conventional wisdom held that exact methods were too expensive to be used for dependence testing and that most cases could be accurately solved by traditional methods.
The Omega test [Pug92] is a set of routines for manipulating linear constraints over integer variables. I implemented a dependence testing algorithm using the Omega test within Michael Wolfe's tiny tool and found the Omega test to be very fast, taking less than 0.5 milliseconds to analyze most array pairs on a Sun Sparc IPX. The time taken to analyze a program with the Omega test is typically 1-5%of the time required to compile it with f77 -O2.
The Omega test is based on an extension of Fourier-Motzkin Variable Elimination (FMVE) [DE73] to integer programming. Other researchers have suggested the use of FMVE for dependence analysis [MHL91b][WT92] but only as a last resort after exact and fast, but incomplete, methods have failed to give decisive answers. I [Pug92] proved that in cases where the fast but incomplete methods of Lam et al. [MHL91b] apply, the Omega test is guaranteed to have low-order polynomial time complexity. The Omega test typically needs less than 0.1 milliseconds to solve trivial dependence analysis problems, such as those handled by the SIV test [GKT91]. We have even found that the Omega test is substantially faster than some implementations of traditional techniques (although these implementations have not been engineered for speed).
There are several reasons why the Omega test is as efficient as it is for dependence testing:
For many typical, realistic cases traditional techniques are accurate. However, in these cases the Omega test is not substantially slower (and may be faster) than traditional techniques.