Mon, 20 Jun 1994 20:19:02 GMT

Related articles |
---|

Omega Calculator version 0.7 available vadik@cs.umd.edu (1994-06-20) |

Newsgroups: | comp.compilers |

From: | vadik@cs.umd.edu (Vadim Maslov) |

Keywords: | tools, available, FTP, parallel |

Organization: | U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742 |

Date: | Mon, 20 Jun 1994 20:19:02 GMT |

The beta release of version 0.7 of the Omega Calculator is now

available for anonymous ftp from ftp.cs.umd.edu:pub/omega/OmegaCalc.

Version 0.7 is the first publicly released Omega Calculator version.

The implementation of the Omega Calculator has been done by a number

of people at the University of Maryland:

Wayne Kelly, Vadim Maslov, William Pugh,

Evan Rosser, Tatiana Shpeisman, Dave Wonnacott

Enclosed is README file from the distribution.

This is a beta release of version 0.7 of the Omega Calculator.

The Omega calculator is a text-based interface to the Omega library,

a set of routines developed for manipulating

* Presburger formulas,

* Integer tuple sets, and

* Integer tuple relations

This beta release surely contains a number of undiscovered bugs

as well as known, undocumented bugs we haven't got around

to fixing yet. This release is being distributed to let people

see where we are going with our research, and learn whether

more robust and documented versions of our software might be

useful in their research. This version will expire on July 31st,

1994. By that point, a new, improved version should be available.

The ftp site for our software is ftp.cs.umd.edu/pub/omega. The

Omega calculator is in the subdirectory OmegaCalc. Information

about the Omega project is also available via www:

http://www.cs.umd.edu/projects/omega

At the moment, we are only making executables available via

anonymous ftp. Source code is available by request (so that

we to conform to g++-lib's distribution requirements), but not

via ftp. The current source is unsupported and guaranteed to change

without notice. We _highly_recommend_ that you wait for a supported

source release if you want to use our source - we plan to release this

soon, together with a description of the high level C++ interface. If

you really must have the source now, send a 1000 word essay on why

you can't wait, to omega@cs.umd.edu ;-). The Omega library will be

freely available for experimentation or incorporation in research

or commercial tools (and will be freed from g++-lib).

Presburger Formulas

===================

Presburger formulas are those formulas that can be built using

linear constraints over integer variables, the usual logical

connectives ("and", "or" and "not") and universal and existential

quantifiers ("there exists" and "forall").

Within the realm of Presburger formulas, the Omega calculator is

exact. The worst-case cost of determining the satisfablity of

Presburger formulas is suspected to be $2^{2^{2^{O(n)}}}$, and

our worst case performance is no better than this. For simple

cases arising in situations such as dependence analysis and

compiling High Performance Fortran, our performance is acceptable.

We have recently been focused on improving the functionality

of our library rather than the performance. It is currently

4-8 times slower than our previous implementation. Some of

this will improve in the near future, but our speed will

probably never match that of our previous implementation

due to the high-level, abstract interface provided by the

new library.

The Omega calculator

====================

The Omega 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] ->[i+1,j+1] : 1 <= i, j <= n};

The conditions describing a set or tuple can be an

formulas can described by an arbitrary Presburger formula.

The Omega calculator can also manipulate relations and sets

using standard operations such as union, intersection,

difference, inverse and composition.

In the following examples, input to the calculator is

prefixed with "#":

# R := { [i] -> [i+1] : 1 <= i <= 9 };

# S := {[i] : 5 <= i <= 15 };

# inverse R;

{[In_1] -> [In_1-1] : 2 <= In_1 <= 10}

# domain R;

{[i] : 1 <= i <= 9}

# range R;

{[In_1] : 2 <= In_1 <= 10}

# R compose R;

{[i] -> [i+2] : 1 <= i <= 8}

# S;

{[i] : 5 <= i <= 15}

# R(S);

{[Out_1] : 6 <= Out_1 <= 10}

# symbolic n;

# {[iw] -> [ir] :

# 1 <= iw, ir <= 2n and iw=ir

# and ! exists ( ik,jk : 1 <= ik <= 2n && 1 <= jk < n and

# iw <= ik = ir and 2jk = ir )

# and ! exists ( ik,jk : 1 <= ik <= 2n && 1 <= jk < n and

# iw <= ik = ir and 2jk+1 = ir )

# };

{[iw] -> [iw] : n = 1 && 1 <= iw <= 2}

union {[1] -> [1] : 1 <= n}

union {[2n] -> [2n] : 1 <= n}

# I := {[i,j]: 1 <= i <= 101 && exists (alpha : i = 2 alpha) &&

# 2n+i <= j <=401 && exists (alpha : j = 2 alpha)};

# iterations I;

if n <= 199 then

for i = 2 to min((-2n+400),100) step 2 do

for j = (2n+i) to 400 step 2 do

<element>

#

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.