Fri, 3 Mar 1995 23:53:44 GMT

Related articles |
---|

Version 0.91 of the Omega Calculator and Omega Library available ejr@cs.umd.edu (1995-03-03) |

Newsgroups: | comp.compilers |

From: | ejr@cs.umd.edu (Evan Rosser) |

Keywords: | arithmetic, available, FTP, WWW |

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

Date: | Fri, 3 Mar 1995 23:53:44 GMT |

Version 0.91 of the Omega Calculator and Omega Library is now

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

More information is available on the World Wide Web at:

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

Version 0.91 contains a number of minor improvements and enhancements

over version 0.90.

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.

Some compiler applications we have implemented using the Omega Library are:

- Exact array dependence analysis

- Iteration reordering transformations for scientific codes

- Detection of redundant synchronizations

- Generation of code for multiple overlapping iteration spaces.

We hope to get feedback from this release about our interface. If you

have an interest in using the Omega library in your work, please look

over the interface and give us feedback. We will be much more likely

to listen to requests for changes in the interface now than after we

release version 1.0.

The interface of this current version will hopefully change and

improve for version 1.0 as a result of feedback from users and our

continuing work. However, we are unlikely to make any changes that

would require substantial changes for people writing code that

interfaces with version 0.91. We intend to release version 1.0

sometime in the late spring.

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

To give you an idea of what the Omega calculator and library can do,

I've enclosed below same output from the Omega calculator. The input

is echoed on lines starting with #

# Omega Calculator [v0.91, Feb 95]:

# #

# # Some examples from the documentation for the Omega Calculator

# # This is the input for figures 2 and 3.

# #

#

# R := { [i] -> [i'] : 1 <= i,i' <= 10 && i' = i+1 };

#

# R;

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

#

# inverse R;

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

#

# domain R;

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

#

# range R;

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

#

# R compose R;

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

#

# R+;

{[i] -> [i'] : 1 <= i < i' <= 10}

# # closure of R = R union (R compose R) union (R compose R ...

# complement R;

{[i] -> [i'] : i <= 0} union

{[i] -> [i'] : 10 <= i} union

{[i] -> [i'] : i <= i'-2} union

{[i] -> [i'] : i' <= i}

#

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

#

# S;

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

#

# R(S);

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

# # apply R to S

# R \ S;

{[i] -> [i+1] : 5 <= i <= 9}

# # restrict domain of R to S

# R / S;

{[i] -> [i+1] : 4 <= i <= 9}

# # restrict range of R to S

# (R\S) union (R/S);

{[i] -> [i+1] : 4 <= i <= 9}

#

# (R\S) intersection (R/S);

{[i] -> [i+1] : 5 <= i <= 9}

#

# (R/S) - (R\S);

{[4] -> [5] }

#

# S*S;

{[i] -> [i'] : 5 <= i <= 25 && 5 <= i' <= 25}

# # cross product

# D := S - {[9:16:2]} - {[17:19]};

#

# D;

{[i] : 5 <= i <= 8} union

{[i] : Exists ( alpha : 2alpha = i && 6 <= i <= 16)} union

{[i] : 20 <= i <= 25}

#

# T := { [i] : 1 <= i <= 11 & exists (a : i = 2a) };

#

# T;

{[i] : Exists ( alpha : 2alpha = i && 2 <= i <= 10)}

#

# Hull T;

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

#

# Hull D;

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

#

# codegen D;

for(t1 = 5; t1 <= 8; t1++) {

s1(t1);

}

for(t1 = 10; t1 <= 16; t1 += 2) {

s1(t1);

}

for(t1 = 20; t1 <= 25; t1++) {

s1(t1);

}

#

# codegen {[i,j] : 1 <= i+j,j <= 10};

for(t1 = -9; t1 <= 9; t1++) {

for(t2 = max(-t1+1,1); t2 <= min(-t1+10,10); t2++) {

s1(t1,t2);

}

}

#

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.