The Omega Project and Constraint Based Analysis Techniques in High Performance Computing

William Pugh
Professor Emeritus of Computer Science at the University of Maryland at College Park

The Omega test paper was one of the first to suggest general use of an exact algorithm for array data dependence analysis, which is the problem of determining if two array references are aliased. Knowing this is essential to knowing which loops can be run in parallel. Array data dependence is essentially the problem of determining if a set of affine constraints have an integer solution. This problem is NP-complete, but the paper described an algorithm that was both fast in practice and always exact. More important than the fact that the Omega test was exact was that it also could use arbitrary affine constraints (as opposed to many existing algorithms which could only use constraints occurring in certain pre-defined patterns), and could produce symbolic answers, rather than just yes/no answers. This work was the foundation of the Omega project and library, which significantly expanded the capabilities of the Omega test and added to the range of problems and domains that it could be applied to. The Omega library could calculate things such as actual data flow (rather than just aliasing), analyze and represent loop transformations, calculate array sections that needed to be communicated and generate loop nests. 

This talk will describe both the Omega test, the context in which the paper was originally written, the Omega project and the field of constraint-based program analysis and transformation that it helped open up.