   Next: Value-based Dependence Analysis Up: Frameworks and Algorithms Previous: Frameworks and Algorithms

# Array Data Dependence Analysis

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:

• The way in which the Omega test extends FMVE to integers is designed so that in typical cases it imposes no speed penalty. In contrast, Lam et al. [MHL91b] compute a sample integer solution to verify the existence of solutions. The overhead of this computation is not needed in the many typical cases where we can detect that FMVE is exact over integers.
• If a dependence exists, it must be characterized by an abstraction such as direction vectors. Computing this may require many additional calls to a decision test method. By using the Omega test's ability to return symbolic answers, we can often construct a direction vector from the result returned by a single call to the Omega test.

• Careful engineering and internal algorithmic improvements have led to a factor of - speed improvement over our initial implementation.

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.   Next: Value-based Dependence Analysis Up: Frameworks and Algorithms Previous: Frameworks and Algorithms

Web Accessibility

omega@cs.umd.edu