Array abstractions using semantic analysis of trapezoid congruences

ABSTRACT

With the growing use of vector supercomputers, efficient and accurate data structure analyses are needed. What we propose in this paper is to use the quite general framework of Cousot's abstract interpretation for the particular analysis of multi-dimensional array indexes. While such indexes are integer tuples, a relational integer analysis is first required. This analysis results of a combination of existing ones that are interval and congruence based. Two orthogonal problems are directly concerned with the results of such an analysis, that are the parallelization/vectorization with the dependence analysis and the data locality problem used for array storage management. After introducing the analysis algorithm, this paper describes on a complete example how to use it in order to optimize array storage.

REFERENCES

• Ban88: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• BK89: V. Balasundaram , K. Kennedy, A technique for summarizing data access and its use in parallelism enhancing transformations, ACM SIGPLAN Notices, v.24 n.7, p.41-53, July 1989
• CC77: 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]
• CC79: Patrick Cousot , Radhia Cousot, Systematic design of program analysis frameworks, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.269-282, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567778]
• CH78: 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]
• Cou78: P. Cousot. Mgthodes itgratives de construction et d'approximation de points fixes d'opdrateurs monotones sur un treillis, analyse sdmantique de programmes. Th~se d'$tat, Mar. 1978. Universit$ scientifique et m~dicale de Grenoble.
• Deu92: A. Deutsch. A storeless model of aliasing and its abstraction using finite representation of rightregular equivalence relations. In International Conference on Computing Languages, 1992.
• GJG87: D. Gannon , W. Jalby , K. Gallivan, Strategies for cache and local memory management by global program transformation, Proceedings of the 1st International Conference on Supercomputing, p.229-254, March 1988, Athens, Greece
• Gra91a: P. Granger. Analyses sdmantiques de congruence. PhD thesis, Ecole Polytechnique, Palaiseau, July 1991.
• Gra91b: Philippe Granger, Static analysis of linear congruence equalities among variables of a program, Proceedings of the international joint conference on theory and practice of software development on Colloquium on trees in algebra and programming (CAAP '91): vol 1, p.169-192, April 1991, Brighton, United Kingdom
• GS90: T. Gross , P. Steenkiste, Structured dataflow analysis for arrays and its use in an optimizing complier, Software—Practice & Experience, v.20 n.2, p.133-155, February 1990 [doi>10.1002/spe.4380200203]
• 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
• IJT90: F. Irigoin, P. Jouvelot, and R. Triolet. Ow;rview of the pips project. In International Workshop on Compiler for Parallel Computers, pages 199-212, 1990.
• Kar76: M. Karr. Afllne relationships among variables of a program. Acta Informatica, 6:133-151, 1976.
• Mas91a: F. M~sdupuy. Using abstract interpretati.on to analyse multi-dimensional array subscripts. Research Report LIX/RR/91/07, Ecole Polytechnique, 91128 PaJ~iseau, France, 1991.
• Mas91b: F. Ma~dupuy. Using abstract interpretation to detect array data dependencies. In International Symposium on Supercomputing, Fukuoka, pages 19-27. Kyushu University press, 1991.
• Mas92: F. Mazdupuy. Semantic analysis of rational interval congruences. Research Report LIX/- RR/92/05, Ecole Polytechnique, 91128 Palaiseau, 1992.
• O.44: Ore O. Galois connections. Transactions Amer. Math. Soc., 55:493-515, 1944.
• 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]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Array and vector processors

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

General Terms:
Algorithms, Performance