ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
The Omega test: a fast and practical integer programming algorithm for dependence analysis
Full text PdfPdf (1.11 MB)
Source Conference on High Performance Networking and Computing archive
Proceedings of the 1991 ACM/IEEE conference on Supercomputing table of contents
Albuquerque, New Mexico, United States
Pages: 4 - 13  
Year of Publication: 1991
ISBN:0-89791-459-7
Author
William Pugh  Univ. of Maryland, College Park, MD
Sponsors
IEEE : Institute of Electrical and Electronics Engineers
SIGARCH: ACM Special Interest Group on Computer Architecture
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 7,   Downloads (12 Months): 140,   Citation Count: 49
Additional Information:

references   cited by   index terms   collaborative colleagues   peer to peer  

Tools and Actions: Review this Article  
Save this Article to a Binder    Display Formats: BibTex  EndNote ACM Ref   
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/125826.125848
What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

AI91
Corinne Ancourt , François Irigoin, Scanning polyhedra with DO loops, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.39-50, April 21-24, 1991, Williamsburg, Virginia, United States
AK87
Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987  [doi>10.1145/29873.29875]
 
All83
John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
 
Ban88
Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
BC86
Michael Burke , Ron Cytron, Interprocedural dependence analysis and parallelization, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.162-175, June 25-27, 1986, Palo Alto, California, United States
BK89
V. Balasundaram , K. Kennedy, A technique for summarizing data access and its use in parallelism enhancing transformations, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.41-53, June 19-23, 1989, Portland, Oregon, United States
 
DE73
G.B. Dantzig and B.C. Eaves. Fourier-Motzkin elimination and its dual. Journal of Combinatorial Theory (A), 14:288-297, 1973.
GKT91
Gina Goff , Ken Kennedy , Chau-Wen Tseng, Practical dependence testing, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.15-29, June 24-28, 1991, Toronto, Ontario, Canada
 
HK90
Paul Havlak , Ken Kennedy, Experience with interprocedural analysis of array side effects, Proceedings of the 1990 conference on Supercomputing, p.952-961, October 1990, New York, New York, United States
 
HP90
M. Haghighat and C. Polychronopoulos. Symbolic dependence analysis for high performance parallelizing compilers. In Proceedings of the Third Workshop on Language8 and Compilers for Parallel Computing, August 1990.
IJT91
François Irigoin , Pierre Jouvelot , Rémi Triolet, Semantical interprocedural parallelization: an overview of the PIPS project, Proceedings of the 5th international conference on Supercomputing, p.244-251, June 17-21, 1991, Cologne, West Germany  [doi>10.1145/109025.109086]
 
KMC72
D. Kuck, Y. Muraoka, and S. Chen. On the number of operations simultaneously executable in FORTRAN- like programs and their resulting speedup. IEEE Transactions on Computers, 1972.
 
LC90
Lee-Chung Lu , Marina C. Chen, Subdomain dependence test for massive parallelism, Proceedings of the 1990 conference on Supercomputing, p.962-972, October 1990, New York, New York, United States
LT88
A. Lichnewsky , F. Thomasset, Introducing symbolic problem solving techniques in the dependence testing phases of a vectorizer, Proceedings of the 2nd international conference on Supercomputing, p.396-406, June 1988, St. Malo, France  [doi>10.1145/55364.55403]
 
LY90
Zhiyuan Li , Pen-Chung Yew, Some results on exact data dependence analysis, Selected papers of the second workshop on Languages and compilers for parallel computing, p.374-401, May 1990, Urbana, Illinois, United States
LYZ89
Zhiyuan Li , Pen-Chung Yew , Chuag-Qi Zhu, Data dependence analysis on multi-dimensional array references, Proceedings of the 3rd international conference on Supercomputing, p.215-224, June 05-09, 1989, Crete, Greece  [doi>10.1145/318789.318813]
MHL91
Dror E. Maydan , John L. Hennessy , Monica S. Lam, Efficient and exact data dependence analysis, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.1-14, June 24-28, 1991, Toronto, Ontario, Canada
 
Mur71
Yoichi Muraoka, Parallelism exposure and exploitation in programs, 1971
Pug91
William Pugh, Uniform techniques for loop optimization, Proceedings of the 5th international conference on Supercomputing, p.341-352, June 17-21, 1991, Cologne, West Germany  [doi>10.1145/109025.109108]
Sho81
Robert Shostak, Deciding Linear Inequalities by Computing Loop Residues, Journal of the ACM (JACM), v.28 n.4, p.769-779, Oct. 1981  [doi>10.1145/322276.322288]
 
Tri85
R. Triolet. Interprocedural analysis for program restructuring with Parafrase. CSRD Rpt. 538, Dept. of Computer Science, University of Illinois at Urbana- Champaign, December 1985.
Wal88
D. R. Wallace, Dependence of multi-dimensional array references, Proceedings of the 2nd international conference on Supercomputing, p.418-428, June 1988, St. Malo, France  [doi>10.1145/55364.55405]
 
Wol82
Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, 1982
 
Wol89
Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990
 
Wol91
Michael Wolfe. The tiny loop restructuring research tool. In Proc of 1991 International Conference on Parallel Processing, 1991.
 
WT90
Michael Wolfe and Chau-Wen Tseng. The power test for data dependence. Technical Report CS/E 90-015, Oregon Graduate Institute, August 1990.

CITED BY  49
Paul M. Petersen , David A. Padua, Static and dynamic evaluation of data dependence analysis, Proceedings of the 7th international conference on Supercomputing, p.107-116, July 19-23, 1993, Tokyo, Japan
 
Yang Bo , Zheng Fengzhou , Wang Dingxing , Zheng Weimin, Interactive and symbolic data dependence analysis based on ranges of expressions, Journal of Computer Science and Technology, v.17 n.2, p.160-171, March 2002
Peiyi Tang, Exact side effects for interprocedural dependence analysis, Proceedings of the 7th international conference on Supercomputing, p.137-146, July 19-23, 1993, Tokyo, Japan
S. Sharma , C.-H. Huang , P. Sadayappan, On data dependence analysis for compiling programs on distributed-memory machines (extended abstract), ACM SIGPLAN Notices, v.28 n.1, p.13-16, Jan. 1993
 
Jaspal Subhlok , Ken Kennedy, Integer Programming for Array Subscript Analysis, IEEE Transactions on Parallel and Distributed Systems, v.6 n.6, p.662-668, June 1995
 
Miroslav Cupák , Francky Catthoor , Hugo J. De Man, Efficient System-Level Functional Verification Methodology for Multimedia Applications, IEEE Design & Test, v.20 n.2, p.56-64, March 2003
 
Q. Hu , A. Vandecappelle , P. G. Kjeldsberg , F. Catthoor , M. Palkovic, Fast memory footprint estimation based on maximal dependency vector calculation, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
Vivek Sarkar , Radhika Thekkath, A general framework for iteration-reordering loop transformations, ACM SIGPLAN Notices, v.27 n.7, p.175-187, July 1992
 
W. F. J. Verhaegh , P. E. R. Lippens , E. H. L. Aarts , J. L. van Meerbergen, Multidimensional periodic scheduling: a solution approach, Proceedings of the 1997 European conference on Design and Test, p.468, March 17-20, 1997
Oliver Bringmann , Wolfgang Rosenstiel , Axel Siebenborn, Conflict analysis in multiprocess synthesis for optimized system integration, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 19-21, 2005, Jersey City, NJ, USA
William Pugh , David Wonnacott, Eliminating false data dependences using the Omega test, ACM SIGPLAN Notices, v.27 n.7, p.140-151, July 1992
Peter Vanbroekhoven , Gerda Janssens , Maurice Bruynooghe , Henk Corporaal , Francky Catthoor, Advanced copy propagation for arrays, ACM SIGPLAN Notices, v.38 n.7, July 2003
 
Miroslav Cupák , Francky Catthoor , Hugo J. De Man, Efficient System-Level Functional Verification Methodology for Multimedia Applications, IEEE Design & Test, v.20 n.2, p.56-64, March 2003
Peng Wu , Paul Feautrier , David Padua , Zehra Sura, Instance-wise points-to analysis for loop-based dependence testing, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA
 
Oliver Bringmann , Wolfgang Rosenstiel , Dirk Reichardt, Synchronization detection for multi-process hierarchical synthesis, Proceedings of the 11th international symposium on System synthesis, p.105-110, December 02-04, 1998, Hsinchu, Taiwan, China
Wen-mei Hwu , Shane Ryoo , Sain-Zee Ueng , John H. Kelm , Isaac Gelado , Sam S. Stone , Robert E. Kidd , Sara S. Baghsorkhi , Aqeel A. Mahesri , Stephanie C. Tsao , Nacho Navarro , Steve S. Lumetta , Matthew I. Frank , Sanjay J. Patel, Implicitly parallel programming models for thousand-core microprocessors, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California
Armando Solar-Lezama , Gilad Arnold , Liviu Tancau , Rastislav Bodik , Vijay Saraswat , Sanjit Seshia, Sketching stencils, ACM SIGPLAN Notices, v.42 n.6, June 2007
 
Oliver Bringmann , Wolfgang Rosenstiel, Resource sharing in hierarchical synthesis, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.318-325, November 09-13, 1997, San Jose, California, United States
Silvius Rus , Lawrence Rauchwerger , Jay Hoeflinger, Hybrid analysis: static & dynamic memory reference analysis, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA
H. Samsom , F. Franssen , F. Catthoor , H. De Man, System level verification of video and image processing specifications, Proceedings of the 8th international symposium on System synthesis, p.144-149, September 13-15, 1995, Cannes, France
Dror E. Maydan , Saman P. Amarasinghe , Monica S. Lam, Array-data flow analysis and its use in array privatization, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.2-15, March 1993, Charleston, South Carolina, United States
 
Silvius Rus , Lawrence Rauchwerger , Jay Hoeflinger, Hybrid analysis: static & dynamic memory reference analysis, International Journal of Parallel Programming, v.31 n.4, p.251-283, August 2003
Kent Wilken , Jack Liu , Mark Heffernan, Optimal instruction scheduling using integer programming, ACM SIGPLAN Notices, v.35 n.5, p.121-133, May 2000
David Bernstein , Doron Cohen , Dror E. Maydan, Dynamic memory disambiguation for array references, Proceedings of the 27th annual international symposium on Microarchitecture, p.105-111, November 30-December 02, 1994, San Jose, California, United States
Peter Vanbroekhoven , Gerda Janssens , Maurice Bruynooghe , Francky Catthoor, A practical dynamic single assignment transformation, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.12 n.4, p.40-es, September 2007
Rachid Seghir , Vincent Loechner, Memory optimization by counting points in integer transformations of parametric polytopes, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea
Yichen Xie , Andy Chou , Dawson Engler, ARCHER: using symbolic, path-sensitive analysis to detect memory access errors, ACM SIGSOFT Software Engineering Notes, v.28 n.5, September 2003
 
Benny Thörnberg , Qubo Hu , Martin Palkovic , Mattias O'Nils , Per Gunnar Kjeldsberg, Polyhedral space generation and memory estimation from interface and memory models of real-time video systems, Journal of Systems and Software, v.79 n.2, p.231-245, February 2006
 
Enric Musoll , Jordi Cortadella, Register-Transfer Level Transformations for Low-Power Data-Paths, Integrated Computer-Aided Engineering, v.5 n.4, p.315-332, December 1998
Silvius Rus , Maikel Pennings , Lawrence Rauchwerger, Sensitivity analysis for automatic parallelization on multi-cores, Proceedings of the 21st annual international conference on Supercomputing, June 17-21, 2007, Seattle, Washington
Vijay S. Menon , Neal Glew , Brian R. Murphy , Andrew McCreight , Tatiana Shpeisman , Ali-Reza Adl-Tabatabai , Leaf Petersen, A verifiable SSA program representation for aggressive compiler optimization, ACM SIGPLAN Notices, v.41 n.1, p.397-408, January 2006
Vadim Maslov, Delinearization: an efficient way to break multiloop dependence equations, ACM SIGPLAN Notices, v.27 n.7, p.152-161, July 1992
Thomas Reps , Susan Horwitz , Mooly Sagiv , Genevieve Rosay, Speeding up slicing, ACM SIGSOFT Software Engineering Notes, v.19 n.5, p.11-20, Dec. 1994
J. Birch , R.A. van Engelen , K.A. Gallivan , Y. Shou, An empirical evaluation of chains of recurrences for array dependence testing, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA
Thomas Reps , Genevieve Rosay, Precise interprocedural chopping, ACM SIGSOFT Software Engineering Notes, v.20 n.4, p.41-52, Oct. 1995
John Ruttenberg , G. R. Gao , A. Stoutchinin , W. Lichtenstein, Software pipelining showdown: optimal vs. heuristic methods in a production compiler, ACM SIGPLAN Notices, v.31 n.5, p.1-11, May 1996
 
Franco Barbanera , Michele Bugliesi , Mariangiola Dezani-Ciancaglini , Vladimiro Sassone, Space-aware ambients and processes, Theoretical Computer Science, v.373 n.1-2, p.41-69, March, 2007
 
Mahmut Kandemir , Seung Woo Son , Mustafa Karakoy, Improving I/O performance of applications through compiler-directed code restructuring, Proceedings of the 6th USENIX Conference on File and Storage Technologies, p.1-16, February 26-29, 2008, San Jose, California
Kazutaka Morita , Akimasa Morihata , Kiminori Matsuzaki , Zhenjiang Hu , Masato Takeichi, Automatic inversion generates divide-and-conquer parallel programs, ACM SIGPLAN Notices, v.42 n.6, June 2007
Junjie Gu , Zhiyuan Li , Gyungho Lee, Symbolic array dataflow analysis for array privatization and program parallelization, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.47-es, December 04-08, 1995, San Diego, California, United States
Nicolas Vasilache , Cedric Bastoul , Albert Cohen , Sylvain Girbal, Violated dependence analysis, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia
Zhichen Xu , Barton P. Miller , Thomas Reps, Safety checking of machine code, ACM SIGPLAN Notices, v.35 n.5, p.70-82, May 2000
Xavier Vera , Nerina Bermudo , Josep Llosa , Antonio González, A fast and accurate framework to analyze and optimize cache memory behavior, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.2, p.263-300, March 2004
Silvius Rus , Lawrence Rauchwerger , Jay Hoeflinger, Hybrid analysis: static & dynamic memory reference analysis, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA
Robert A. van Engelen , J. Birch , Y. Shou , B. Walsh , Kyle A. Gallivan, A unified framework for nonlinear dependence testing and symbolic analysis, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France
 
Sylvain Girbal , Nicolas Vasilache , Cédric Bastoul , Albert Cohen , David Parello , Marc Sigler , Olivier Temam, Semi-automatic composition of loop transformations for deep parallelism and memory hierarchies, International Journal of Parallel Programming, v.34 n.3, p.261-317, June 2006
Ken Kennedy , Ulrich Kremer, Automatic data layout for distributed-memory machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.4, p.869-916, July 1998
Radu Rugina , Martin C. Rinard, Symbolic bounds analysis of pointers, array indices, and accessed memory regions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.2, p.185-235, March 2005
Reinhard Wilhelm , Jakob Engblom , Andreas Ermedahl , Niklas Holsti , Stephan Thesing , David Whalley , Guillem Bernat , Christian Ferdinand , Reinhold Heckmann , Tulika Mitra , Frank Mueller , Isabelle Puaut , Peter Puschner , Jan Staschulat , Per Stenström, The worst-case execution-time problem—overview of methods and survey of tools, ACM Transactions on Embedded Computing Systems (TECS), v.7 n.3, p.1-53, April 2008

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques

          Nouns: Omega

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Single-instruction-stream, multiple-data-stream processors (SIMD)
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming


General Terms:
Algorithms, Theory

Collaborative Colleagues:
William Pugh: colleagues

Peer to Peer - Readers of this Article have also read:

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2008 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player