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