A general algorithm for data dependence analysis

ABSTRACT

With the development of ever more sophisticated data flow analysis algorithms, traditional data dependence tests based on elementary loop information will not be sufficient in the future. In this paper, quite general algorithms are presented for solving integer linear programming problems. While the properly so called problem solution is performed by a standard algorithm (the dual all integer algorithm), preliminary problem reduction techniques not only serve as a powerful tool for preparing this latter step, but also are often sufficient for solving exactly the data dependence problem.

REFERENCES

• 1: Utpal Banerjee, Speedup of ordinary programs, 1979
• 2: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 3: BENNACEU~, H., AND PLATEAU, G. Sur le probl~me de satisfaction de contraintes. Rapport LIPN 89-6, Universite Paris Nord, Centre Scientifique et Polytechnique, D@artement de math6matiques et informatique, Juin 1989.
• 4: BERRY, M., CHEN, D., Koss, P., KUCK, D., AND LO, S. The PERFECT Club benchmarks: effective performance evaluation of supercomputers. CSRD Report 827, University of Illinois, Urbana-Champaign, May 1989,
• 5: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• 6: Patrick Cousot , Nicolas Halbwachs, Automatic discovery of linear restraints among variables of a program, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.84-96, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512770]
• 7: DANTZIG, G. Linear Programming and Extensions. Princeton University Press, Princeton, New-Jersey, 1963.
• 8: GAI%FINKEL, R. S., AND NEMHAUSt~R, G. N. Integer Programming. Wiley-Interscience, 1972.
• 9: GIBOULOT, M. C., LBBON, E. R., LOVER, M., POPOVITCH, g., SHAFII~, It., AND THOMASSET, F. Parallel execution of Fortran programs on the EWS workstation. In Comput, ng Methods in Applied Sciences and Enginvcr, ng (Philadelphia, /}an. 1990), t<. Glowinski and A. Lichnewsky, Eds., SIAM, pp. 413-423.
• 10: Gina Goff , Ken Kennedy , Chau-Wen Tseng, Practical dependence testing, ACM SIGPLAN Notices, v.26 n.6, p.15-29, June 1991
• 11: GRANGt~R, P. Static analysis of arithmetic congruences.
• 12: David Klappholz , Kleanthis Psarris , Xiangyun Kong, On the perfect accuracy of an approximate subscript analysis test, Proceedings of the 4th international conference on Supercomputing, p.201-212, June 11-15, 1990, Amsterdam, The Netherlands
• 13: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 14: X. Kong , D. Klappholz , K. Psarris, The I Test: An Improved Dependence Test for Automatic Parallelization and Vectorization, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.342-349, July 1991 [doi>10.1109/71.86109]
• 15: LBNSTRA, ~I. W. Integer programming with a fixed number of variables. Mathematics of Operatzons Research 8, 4 (1983), 538-548.
• 16: 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]
• 17: Dror E. Maydan , John L. Hennessy , Monica S. Lam, Efficient and exact data dependence analysis, ACM SIGPLAN Notices, v.26 n.6, p.1-14, June 1991
• 18: MINOUX, M. Programmat,on mathdmat'tque, th~or, e et algor, thmes, tomes 1 et 2. Dunod, 1983.
• 19: George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
• 20: SALKIN, t-I. M., AND MATHUI%, K. Foundat,ons of Integer Programming. North-Holland, 1989.
• 21: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 22: SIMONNARD, B. Programmation lindaire. Dunod, Paris, 1962.
• 23: SOGNO, J.-C. Analysis of standard and new algorithms for the integer constraint satisfaction problem. Rapport de recherche, INRIA, 1992. to appear.
• 24: 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]
• 25: Mark N. Wegman , Frank Kenneth Zadeck, Constant propagation with conditional branches, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.291-299, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318659]
• 26: Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, 1982

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

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

General Terms:
Algorithms