Omega Project Source Release, version 1.10

We have released version 1.1 of the Omega Project software, including:

The Omega library, a set of routines for manipulating linear constraints over integer variables, Presburger formulas, and Integer tuple relations and sets.
The code generation library, a set of routines for generating code to scan the points in the union of a number of convex sets. (requires the Omega library)
The Omega calculator, a text-based interface to the Omega library (requires both above libraries)
The Uniform library, a source to source parallelizing transformation system, described in Wayne Kelly's Ph.D. dissertation.
Petit, a educational/research tool for analyzing array data dependences (needs all three libraries)

Executables

We are working on building a set of executables. We current have the following versions available:

Omega Calculator
- Sun SPARC, Solaris 2.5

New or Recent Features

The Uniform library
An exact convex hull computation
An improved system for handling inexact relations, including taking upper and lower bounds, checking for subsets, and checking tautologies
An Example operator, that gives a sample solution to set or relation.
Better handling of existentially quantified variables: we can now negate and generate code for sets like:
```
        {[i] : 1 <= i <= n && exists (alpha :  i <= 10 alpha <= i+k)};
```
A number of bug fixes

Documentation

Documentation available includes:

Omega Calculator documentation (PostScript)
Omega Library interface documentation (Postscript)
Petit documentation (Postscript)
Installation instructions

The Omega library/calculator manipulates sets of integer tuples and relations between integer tuples. Some examples include:

{ [i,j] : 1 <= i,j <= 10};
{ [i] ->[i,j] : 1 <= i < j <= 10};
{ [i,j] ->[j,j'] : 1 <= i < j < j' <= n};

The conditions describing a set or tuple can be an formulas can described by an arbitrary Presburger formula. Relations and sets can be combined using functions such as composition, intersection, union and difference. It also provides routines to generate code to iterate over the points in an integer tuple set. The Omega library provides a high-level, C++ interface to our routines. The Omega calculator is a text-based interface to the Omega library.

The implementation of the Omega Calculator have been done by a number of people at the University of Maryland:

Wayne Kelly, Vadim Maslov, William Pugh, Evan Rosser, Tatiana Shpeisman, Dave Wonnacott

As usual, the Omega Project is located at

omega@cs.umd.edu

Web Accessibility