Version 0.91 of the Omega Calculator and Omega Library available

ejr@cs.umd.edu (Evan Rosser)
Fri, 3 Mar 1995 23:53:44 GMT

          From comp.compilers

Related articles
Version 0.91 of the Omega Calculator and Omega Library available ejr@cs.umd.edu (1995-03-03)
| List of all articles for this month |

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.