Lazy Array Data-Flow Dependence Analysis

The implementation of the algorithm described in the paper:


        "Lazy Array Data-Flow Dependence Analysis" by Vadim Maslov
        which appears in the proceedings of the
        ACM '94 Conf. on Principles of Programming Languages


is available by anonymous FTP.


Here's the README file that gives details.


Vadim Maslov.
-------------------------------------------------------------


This is the README file for version 3.3.1 of the distribution of the Omega
test, which is available via anonymous ftp from ftp.cs.umd.edu (128.8.128.8)
in the directory pub/omega/lazy.




============== special note begin ===============


This distribution should be used by the people who want to get
implementation of the data dependence analysis algorithm described
in the paper:


        "Lazy Array Data-Flow Dependence Analysis" by Vadim Maslov
        which appears in the proceedings of the
        ACM '94 Conf. on Principles of Programming Languages.


The paper is available from the same directory:
1. Postscript version has the name pub/omega/lazy/Lazy_paper.ps.Z
2. DVI version has the name pub/omega/lazy/Lazy_paper.dvi




Here's the abstract of the paper:


        Automatic parallelization of real FORTRAN programs does not live up to
        users expectations yet, and dependence analysis algorithms which
        either produce too many false dependences or are too slow contribute
        significantly to this. In this paper we introduce data-flow
        dependence analysis algorithm which exactly computes value-based
        dependence relations for program fragments in which all subscripts,
        loop bounds and IF conditions are affine. Our algorithm also computes
        good affine approximations of dependence relations for non-affine
        program fragments. Actually, we do not know about any other algorithm
        which can compute better approximations.


        And our algorithm is efficient too, because it is lazy. When
        searching for write statements that supply values used by a given read
        statement, it starts with statements which are lexicographically close
        to the read statement in iteration space. Then if some of the read
        statement instances are not ``satisfied'' with these close writes, the
        algorithm broadens its search scope by looking into more distant
        writes. The search scope keeps broadening until all read instances
        are satisfied or no write candidates are left.


        We timed our algorithm on several benchmark programs and the timing
        results suggest that our algorithm is fast enough to be used in
        commercial compilers --- it usually takes 5 to 15 percent of {\tt f77
        -O2} compilation time to analyze a program. Most programs in the
        100-line range take less than 1 second to analyze on a SUN
        SparcStation IPX.




The algorithm was implemented in a framework of Omega/Tiny tool
by Vadim Maslov. See below to find Tiny history and other capabilities.




This release and future versions
-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*


The sole purpose of this distribution is to make freely available
the implementation of the lazy dependence analysis algorithm.
It should not be considered as a release of Tiny/Omega tool in its entirety.


A new and improved version is currently under developement.
This new version differs substantially from the current version,
and people are discouraged from building things on top of this
version, because they may need to be discarded to use the next
release.




How to find sources for the algorithm
-------------------------------------


Take a look at files src/lazy.c and src/lexmax.c.




How to use the algorithm
------------------------


0. Compile Tiny. Compilation is described in files obj/makefile
      and CompilationInstructions. Read them real carefully, because
      they are likely to answer questions that you may have.


1. Put obj directory of this distribution on your path.


2. Type "lt infile.t" to start Tiny.


3. Then use regular Tiny commands to view dependences.




How to dump dependences to the file
-----------------------------------


Type "lt -Routfile.t infile.t" and the list of dependences for
program infile.t will appear in file outfile.t.
Direction/distance vectors, exact/inexact flags
and dependence relations will be present in file outfile.t.
With this flag screen dialogue is not started at all,
so -Rfilename mode is Tiny batch mode.




How to dump dependence relations to file
----------------------------------------


Type "lt -b infile.t" and dependence relations for file infile.t will
appear in file rel.out. The difference from -R dump is the more readable
dependence relation format. -R option is used for regression testing, so
its output is intended to be more "machine readable" than "human
readable". The screen with standard Tiny dialogue will appear, if you
want batch mode and nicely printed relations in rel.out, type "lt -bR_.out
infile.t"




How to see the debugging output
-------------------------------


Type "lt -M infile.t" and debugging output of the algorithm
will appear in file trace.out.




How to run regression tests
---------------------------


Go to directory rt and type:
setenv TINY_TEST_FLAGS oa8
prt dataflow


Regression tests will be run.


"a8" specifies the number of dependence testing algorithm to use.
Lazy algorithm has number 8, Omega-3/4 algorithm is started by default.
If Tiny is started with name lt, then the lazy algorithm is used.




More intrinsics
---------------


Combinations of the above flags work and can be used.


lt is a symbolic link to t. If tiny is started as lt,
lazy dependence analysis algorithm is used.
By default, Omega-3/4 algorithm is used.




Computing lexicographical maximum of parametrized tuple set
-----------------------------------------------------------


This is about Tiny-unrelated interface to RelMax1 algorithm
that computes lexicographical maximum of a set of tuples
specified by a number of affine constraints (free variables
may be involved). Use statement "maximize var1, var2, ..., varN"
to specify what statements to maximize.
To compile Omega driver, type "pmake omega" in obj directory.


Example: input file pipmax.ip:


protect M,N,K
maximize i,j
0 <= i <= M
0 <= j <= N
2i + j = K


Output of the command "omega pipmax.ip":


Initial problem is :


variables = (M, N, K), i, j
K = 2i+j
0 <= i
i <= M
0 <= j
j <= N


Lexicographical maximum of the problem is:
solution 1:
i = M; 2M+j = K; 2M <= K <= 2M+N; 0 <= M
solution 2:
2i+j = K; 2i <= K <= 2i+1, N+2i; 0 <= i <= M




If I have a problem
-------------------


If this is a problem with the lazy algorithm, write to
Vadim Maslov <vadik@cs.umd.edu>. If you are sure that
this is problem with default algorithm or with Tiny
in general, then write to omega@cs.umd.edu.




What works and what doesn't
---------------------------


Nothing is guaranteed to work, as there are bugs in this software.
However, dependence analysis algorithms are more likely to work
than anything else.


============== special note end ===============




This release consists of three components:


          * The Omega test: A system for performing symbolic
manipulations of conjunctions of linear constraints
over integer variables. In particular, the operations
supported include:
* Checking if integer solutions exist


* Eliminating an existential quantifier. For example,
we can transform
{ Exists b s.t. 0 <= a <= 5; b < a <= 5b}
to
{ 2 <= a <= 5}


* Checking to see if one set of constraints implies
another. For example, we can check to see if:


{0 <= x <= 3; -3 <= 2y <= 3} => {0 <= x+y, x-y <= 3}


The interface to the Omega test is described
in the file doc/omega_interface.tex


          * The Omega test dependence analyzer: A system built on top
of the Omega test to analyze array data dependences. This
system builds the appropriate problems and makes the appropriate
queries of the Omega test to analyze array-based data dependences
in programs. The analyzer computes data difference/direction
vectors, recognizes reduction dependences, analyzes array kills
(which enables array expansion and array privatization),
and determines when assertions can be used to eliminate dependences.


We have attempted to define an interface that allows other users
to make use of the Omega test dependence analyzer. This interface
is described in include/lang-interf.generic and Lang-Interf3.1
(keep in touch if you plan to use this interface; we are continuing
to refine it).


          * Extended tiny. We have extended Michael Wolfe's tiny tool. The
major extensions are:


* Improved user interface (scrolling, dependence browsing
windows)


* Capabilities that improve the accuracy of data dependence
analysis (induction variable recognition, forward
substitution).


* Features that demonstrate the additional information we
collect (scalar/array expansion and privatization,
interactive dependence zapping)


* An semi-automatic procedure for converting FORTRAN programs
into tiny


* A prototype implementation of a unified framework
for reordering transformations. The framework
unifies loop interchange, skewing, distribution,
fusion, reversal, statement reordering, and some
cases of access normalization, loop alignment, loop
peeling and index set splitting.


The Omega test is implemented on top of the December 1990 version of
Michael Wolfe's tiny program, as well as in a stand-alone test driver.
The Omega test computes exact data dependence information, including checks
for array kills. The Omega test data dependence analyzer is substantially
more accurate than dependence analyzers in many existing research
and commercial systems.


Tiny is a research implementation of an interactive program
restructuring tool. Tiny computes data dependence relations
and interactively performs many restructuring transformations, such
as loop interchanging, distribution, skewing, ... . Michael Wolfe
has put his tiny tool into the public domain, which allowed
us to build on top of his software. We are very grateful for Michael's
contributions.


This implementation is a research prototype and has not been subjected
to rigorous testing. In other words:


THERE ARE BUGS IN THIS SOFTWARE


We don't know of any at the moment (other that the ones listed
under KNOWN BUGS/LIMITATIONS below), but we are sure that other,
undiscovered bugs remain in the software. This software has been
put into the public domain as a public service on an "as-is"
basis, without warranty or liability.


Since this version incorporates a large number of major new features,
there will almost certain be bug fixes that will be shortly released as
version 3.2.2.


If you register with us as someone who has a copy of the Omega test,
we will send you update notices. Send email to omega@cs.umd.edu to
be added to the list of registered users.


We are committed to continued distribution and support of the Omega
test for other researchers, and a number of research groups are already
incorporating the Omega test into their compilers and programming
environments. We welcome any additional researchers. Please stay
in contact with us if you plan to make serious us of the Omega test so
that we can provide you with updates and get feedback from your use.




The implementation of the Omega test and extensions to tiny have
been done by a number of people at the University of Maryland:
Udayan Borkar
Wayne Kelly
Evan Rosser
Vadim Maslov
William Pugh
Jerry Sobieski
Dave Wonnacott


This software is public domain, and no legal restrictions of any
kind whatsoever are placed on uses of it). You may do whatever you want
with it, and no guarantees of any kind are made about its performance or
lack of errors. You can copy it, use it, incorporate it or even sell it.
We request that any research or products that make use of this software
acknowledge that use and that you keep us informed of your use.


Please send mail to omega@cs.umd.edu if you wish to be added to a mailing
list for people interesting in using this software. We will notify
people on the mail list of bug fixes and new releases.


Also send mail to omega@cs.umd.edu if you have any trouble installing
the software, bug reports or questions.


Our work on this software has been supported by NSF grants CCR-8908900 and
CCR-9157384 and by a Packard Fellowship, as well as being based on
Michael Wolfe's original implementation of tiny.




FILES
-----


The following tar files can be ftp-ed from ftp.cs.umd.edu (128.8.128.8)
from the directory pub/omega:




  * README This file
  * WOLFE_README The readme file that originally accompanied Michael
                                            Wolfe's distribution of tiny
  * src.tar.Z Source for the omega test, our enhanced version of tiny,
                                            and f2t, a FORTRAN to tiny converter
  * sparc_demo.tar.Z Sun Sparc executable versions of the programs that can be
made from the src files, demo files, and documentation of
of how to use our extended version of tiny.
  * dec3100_demo.tar.Z Decstations 3100 executable versions of the programs
                                            that can be made from the src files. demo files,
                                            and documentation of how to use our extended version
                                            of tiny.
  * demo.tar.Z Test files for demos
  * test.tar.Z Regression test files
  * doc.tar.Z Documentation
  * techReports A directory containing postscript and dvi copies of
relevant tech reports.


Together, these tar files constitute the entire tiny system, with the
following directories:


  * include header files (from src.tar.Z)
  * src source code (from src.tar.Z)
  * obj makefile (from src.tar.Z), generated files (from sparc_bin.tar)
  * doc documentation for tiny and for other drivers for the omega test
  * demo sample files documented to show features of the Omega test and
extended tiny
  * f2t A FORTRAN to tiny converter based on f2c (from src.tar.Z)
  * rt regression test sample files and expected results (from test.tar.Z)
  * misc shell scripts used for regression testing (rt.tar and src.tar)


The executable programs are:


  * "t" the tiny environment, upgraded to use the omega test and
test for refinement, killing, and covering of dependences


  * "f2t" A FORTRAN to tiny converter based on f2c
--

Return to the comp.compilers page.
Search the comp.compilers archives again.