home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / parallel / 2738 < prev    next >
Encoding:
Text File  |  1992-12-14  |  9.5 KB  |  223 lines
  1. Newsgroups: comp.parallel
  2. Path: sparky!uunet!gatech!hubcap!fpst
  3. From: pugh@cs.umd.edu (Bill Pugh)
  4. Subject: Release of v 3.0.0 of Omega test / Extended Tiny
  5. Message-ID: <1992Dec14.133703.18747@hubcap.clemson.edu>
  6. Sender: news@MIMSY.CS.UMD.EDU
  7. Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
  8. Date: 12 Dec 92 20:58:33 GMT
  9. Approved: parallel@hubcap.clemson.edu
  10. Lines: 211
  11.  
  12.  
  13.  
  14. Version 3.0.0 of our implementation of the Omega test is now
  15. available for anonymous ftp from ftp.cs.umd.edu:pub/omega.
  16. The Omega test is implemented in an extended version of
  17. Michael Wolfe's tiny tool, a research/educational tool
  18. for examining array data dependence algorithms and 
  19. program transformations for scientific computations.
  20.  
  21. New features include:
  22.  
  23.     Array & scalar expansion and privatization
  24.  
  25.     Reduction dependences
  26.  
  27.     Induction variable recognition
  28.  
  29.     Scalar forward substitution
  30.  
  31.     Storage classes
  32.  
  33.     A prototype partial implementation of a unified framework
  34.     for reordering transformations. This framework reorders
  35.     reordering transformations such as loop interchange, loop
  36.     skewing, loop distribution, loop fusion and statement reordering.
  37.     This framework can be used to optimize code fragments for 
  38.     parallelism and/or locality.
  39.  
  40.     A FORTRAN to tiny translator (f2t) based on f2c
  41.  
  42.  
  43. Features from version 2.1:
  44.  
  45.     Exact dependence analysis algorithms. 
  46.  
  47.     Array kill analysis (determining when intermediate writes kill
  48.     a dependence). Array kill analysis is required in order to
  49.     perform array privatization or expansion.
  50.  
  51.     Analysis of when "interesting" assertions can eliminate a dependence
  52.     (a dependence is uninteresting if it is false only when the loop that
  53.     carries the dependence executes less than 2 iterations).
  54.  
  55. This code is freely available for research or commercial use. The
  56. extended version of tiny can be used as a educational or research tool.
  57. Several research groups are incorporating the Omega test dependence analyzer
  58. into their compilers/programming environments, include groups at University
  59. of Illinois, Urbana-Champaign and at Georgia Tech. Anyone interested in
  60. doing this is strongly urged to stay in contact with us (at omega@cs.umd.edu) as
  61. we are continuing to update and improve the interface that allows external
  62. users to hook into our data dependence analyze.
  63.  
  64.  
  65. This release consists of three components:
  66.  
  67.      *    The Omega test: A system for performing symbolic
  68.     manipulations of conjunctions of linear constraints
  69.     over integer variables. In particular, the operations
  70.     supported include:
  71.         * Checking if integer solutions exist
  72.  
  73.         * Eliminating an existential quantifier. For example,
  74.           we can transform 
  75.             { Exists b s.t. 0 <= a <= 5; b < a <= 5b}
  76.           to
  77.             { 2 <= a <= 5}
  78.  
  79.         * Checking to see if one set of constraints implies
  80.           another. For example, we can check to see if:
  81.         
  82.                    {0 <= x <= 3; -3 <= 2y <= 3} => {0 <= x+y, x-y <= 3}  
  83.  
  84.         The interface to the Omega test is described
  85.         in the file doc/omega_interface.tex
  86.  
  87.      *    The Omega test dependence analyzer: A system built on top
  88.     of the Omega test to analyze array data dependences. This
  89.     system builds the appropriate problems and makes the appropriate
  90.     queries of the Omega test to analyze array-based data dependences
  91.     in programs. The analyzer computes data difference/direction
  92.     vectors, recognizes reduction dependences, analyzes array kills
  93.     (which enables array expansion and array privatization), 
  94.     and determines when assertions can be used to eliminate dependences.
  95.  
  96.     We have attempted to define an interface that allows other users
  97.         to make use of the Omega test dependence analyzer. This interface
  98.         is described in include/lang-interf.generic and Lang-Interf3.0 
  99.         (keep in touch if you plan to use this interface; we are continuing 
  100.         to refine it).
  101.  
  102.      *  Extended tiny. We have extended Michael Wolfe's tiny tool. The
  103.     major extensions are:
  104.     
  105.         * Improved user interface (scrolling, dependence browsing
  106.           windows)
  107.  
  108.         * Capabilities that improve the accuracy of data dependence
  109.           analysis (induction variable recognition, forward
  110.           substitution).
  111.  
  112.         * Features that demonstrate the additional information we
  113.           collect (scalar/array expansion and privatization,
  114.           interactive dependence zapping)
  115.  
  116.         * An semi-automatic procedure for converting FORTRAN programs
  117.           into tiny
  118.  
  119.         * A prototype implementation of a unified framework
  120.           for reordering transformations. The framework 
  121.           unifies loop interchange, skewing, distribution,
  122.           fusion, reversal, statement reordering, and some
  123.           cases of access normalization, loop alignment, loop
  124.           peeling and index set splitting.
  125.  
  126.  
  127. Also available are copies of several recent technical reports:
  128.  
  129.     William Pugh & David Wonnacott, Eliminating False Data Dependences using 
  130.     the Omega Test, Tech. Report CS-TR-2993, Dept. of Computer Science,
  131.     Univ. of Maryland, College Park (An earlier version of this paper
  132.     appeared at the ACM SIGPLAN PLDI'92 conference).
  133.  
  134.                 Abstract
  135.       Array data dependence analysis methods currently in use generate 
  136.       false dependences that can prevent useful program transformations. 
  137.       These false dependences arise because the questions asked are
  138.       conservative approximations to the questions we really should be 
  139.       asking.  Unfortunately, the questions we really should be asking
  140.       go beyond integer programming and require decision procedures for 
  141.       a subclass of Presburger formulas.  In this paper, we describe how 
  142.       to extend the Omega test so that it can answer these queries and 
  143.       allow us to eliminate these false data dependences. We have 
  144.       implemented the techniques described here and believe they are 
  145.       suitable for use in production compilers.
  146.  
  147.  
  148.     William Pugh, The Definition of Dependence Distance, Tech. 
  149.     Report CS-TR-2992, Dept. of Computer Science, Univ. of 
  150.     Maryland, College Park
  151.  
  152.                 Abstract
  153.       Data dependence distance is widely used to characterize data 
  154.       dependences in advanced optimizing compilers.  The standard 
  155.       definition of dependence distance assumes that loops are normalized 
  156.       (have constant lower bounds and a step of 1); there is not a 
  157.       commonly accepted definition for unnormalized loops.
  158.       
  159.       There are a number of subtleties involved in the definition of 
  160.       dependence distance for unnormalized loops.  In particular, a number 
  161.       of compilers and programming environments seem to be implicitly using
  162.       a definition that can result in non-integral dependence distances.
  163.       Since non-integral distances were not anticipated, the compilers 
  164.       decide that such dependences do not exist. This results in the 
  165.       compiler failing to recognize the existence of a dependence that 
  166.       actually exists, which allows the compiler to make illegal program 
  167.       transformations. This error existed in Parafrase-2, Parascope, and 
  168.       the KAP compiler (this error has been reported and may be corrected 
  169.       in these systems by now).
  170.      
  171.  
  172.     William Pugh and Dave Wonnacott, Static Analysis of Upper Bounds 
  173.         on Parallelism, Tech Report CS-TR-2994, Dept. of Computer 
  174.     Science, Univ. of Maryland, College Park
  175.  
  176.                 Abstract
  177.       Substantial parallelism exists in all of the Perfect Benchmarks 
  178.       codes, although existing automatic techniques are able to find it
  179.       in only a few cases.  Exposing much of this parallelism required a 
  180.       careful, manual examination of all the dependences which appeared to 
  181.       prevent parallelism, and the development and manual application of 
  182.       new program transformations that have not yet been automated.
  183.  
  184.       We describe methods for statically analyzing the program to
  185.       determine which code segments must either be run sequentially or
  186.       rewritten using a new algorithm, and which might contain parallelism
  187.       that automatic techniques are unable to expose. We can also provide
  188.       some feedback about the kinds of additional, possibly manual, 
  189.       analysis or transformations that may be required to expose the 
  190.       parallelism.
  191.  
  192.       In order to determine upper bounds on parallelism, we describe
  193.       methods for computing exact data dependence information, incorporating
  194.       information about array kills and conditional dependences.  In cases 
  195.       involving non-linear references, our information is inexact but we 
  196.       calculate upper and lower bounds on the true dependences.  Since 
  197.       we do not have to compute this more exact information for every array 
  198.       reference pair in a program, but those for which an apparent 
  199.       dependence threatens our ability to run part of the program in 
  200.       parallel, the increased cost of performing this analysis should not 
  201.       be prohibitive.
  202.  
  203.  
  204.     Wayne Kelly and William Pugh, Generating Schedules and Code within a
  205.         Unified Reordering Transformation Framework, Tech
  206.     Report CS-TR-2995, Dept. of Computer Science, Univ. of 
  207.     Maryland, College Park
  208.  
  209.                 Abstract
  210.       We discuss using schedules as a framework for unifying reordering 
  211.       transformations such as loop interchange, loop skewing, loop 
  212.       distribution and loop alignment. This framework subsumes unimodular 
  213.       loop transformations. We describe algorithms to align schedules
  214.       and to produce the transformed code.
  215.  
  216.       This framework is capable of handling more complex schedules than we 
  217.       currently generate, such as schedules that describe loop blocking and 
  218.       interleaving. We are able to check the validity of these schedules 
  219.       and produce appropriate transformed code.
  220.  
  221.  
  222.  
  223.