The Omega Project:

Frameworks and Algorithms for the Analysis and Transformation of Scientific Programs

For the most recent release of Petit, the Uniform Library, the Omega Library, and Omega calculator, please use the Omega Project repository at

William Pugh and the entire Omega Project Team

Omega Project Technical Reports

The Omega project has two major components. One component is the Omega test, a system for manipulating sets of affine constraints over integer variables. When we started work on the Omega test for dependence testing, it was designed as a decision test for the existence of integer solutions to affine constraints. We found that by having the Omega test return symbolic answers, rather than yes/no answers, we could perform standard data dependence analysis quicker. As we have explored more difficult issues in analysis and transformation of scientific programs, we have extended the Omega test to the point where it is a complete system for simplifying and verifying Presburger formulas (Presburger formulas contain affine constraints, the usual logical connectives, and existential and universal quantifiers). Of course, the Omega test cannot simplify all Presburger formulas efficiently (there is a 2^(2^n) nondeterministic lower bound and a 2^(2^(2^n)) deterministic upper bound on the time required to verify Presburger formulas). However, in practice the Omega test is reasonably efficient for the tasks for which we currently use it.

The other component of my research is developing frameworks for analyzing and transforming programs. We have utilized the Omega test in research on asking more sophisticated questions than are usually asked when analyzing programs; on using this information to pinpoint parallelism unexploited by conventional techniques; and on developing a unified framework for reordering transformations. These methods are described using simple cases of Presburger formulas. The descriptions and implementations of these techniques can be simple and clear since they need not be concerned with the techniques used by the Omega test to simplify the formulas.

As a general philosophy, we've tried to develop exact methods and frameworks that are efficient enough to be practical, as opposed to developing inexact methods that may be faster and accurate enough for practical use. We find that studying exact methods gives me a better insight into the problems we study, that it is easier to extend exact methods to make them faster than it is to extend inexact methods to make them more exact, and that exact methods can more easily be applied to new problems.

My research group has done only very limited studies of the efficiency and effectiveness of our methods on real FORTRAN codes. While these are important, doing such studies well requires a robust, optimizing FORTRAN compiler (which we do not have access to) and substantial effort. Also, applying our techniques to real codes requires extensions still under development (for procedure calls and arbitrary control flow). As a number of other research groups incorporate the Omega test into their software, we hope to get feedback from them and pursue collaborative research.

next up prev

Next: Array Data Dependence

Where to get Omega project software

Omega project software is available for anonymous FTP:

Research described here has been supported by a Packard Fellowship and the National Science Foundation under grants CCR9157384, CCR9619808 and ASC9720199. Any opinions, findings and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).