A. Lichnewsky
ABSTRACT
The purpose of a vectorizer is to perform program restructuring in order to exhibit the most efficiently exploitable forms of vector loops. This is guided by a suitable form of semantic analysis, Dependence Testing, which must be precise in order to fully exploit the architecture. Most studies reduce this phase to the application of a series of explicitly computable arithmetic criteria. In many cases, this will fail if the criteria cannot be computed numerically, and contain symbols which cannot be evaluated. This also makes the use of other information pertaining to these symbols difficult. It is shown here that it is possible to extract symbolic equations from some of the classical criteria, merge them with other symbolic knowledge about the program, and use the global system to decide the non-existence of a dependence. In the context of the VATIL vectorizer [17, 16], it is also shown possible to control the computation cost, and obtain a good overall efficiency.
- 1.A. V. Aho, R. Sethi & J. D. Ullman, "Compilers: Principles, Techniques and Tools", Addison Wesley, 1986. Google Scholar
Digital Library
- 2.R. Allen, ~Dependenee analysis for subscripted variables and its application to program transformations", Ph.D Dissertation, Dept. of Mathematical Sciences, Rice University, Houston, Texas, April 1983. Google ScholarDigital Library
- 3.U. Basterjee, "Speed-up of ordinary programs", Phd. Thesis, Rep. 79-089, Dept. of Computer Seienee~ University of Illinois at Urbana-Champaign, October 1079. Google ScholarDigital Library
- 4.U.Banerjee, "Data Dependence in Ordinary Programs~, Rep 76-8S7, Dept. of Computer Science, University of Illinois at Urbana-Charnpaign, November 1976.Google Scholar
- 5.W.W.Bledsoe, ".4 new Method/or proving certain Presburger formulas~, 4th Int. Joint Conf. Artif. Intell., Tbilissi, September 1975, pp. 15-21.Google Scholar
- 6.M. Burke, R. Cytron, "Interproce.dural Dependence Analysis and Parallelization', Proc. Compiler Construction Conf., 1986. Google ScholarDigital Library
- 7.J. Chailloux, "LeLisp, Version 15.~: le manuel de rdfdrence", INRIA, 1986.Google Scholar
- 8.P.Cou~ot, "Semantie Foundation of Program Analysis", in S.S. Muchnick & N. D. Jones eds., "Program Flow Analysis", Prentice Hall, 1981.Google Scholar
- 9.P. Feautrier, A. Dumay, N. Tawbi, "PAF: Un Paralldliseur A utomatique pour Fortran", Rep. MASI, No 185, Universitd Paris 7, 1987.Google Scholar
- 10.D.D. Gajski, J.K. Peir, "Toward computer aided programming for multiprocensors", in M. Cosnard & al. ed., "Parallel Algorithms & Architectures~, North Hol|and~ 1986. Google ScholarDigital Library
- 11.M. R. Garey, D. S. Johnson, "Computers and Intractability~, Freeman and Co, New York, 1979. Google ScholarDigital Library
- 12.K. Kennedy, ~ Automatic translation of fortran programs to vector form~, Rice U. Tech. Rep. 4 76"0~9-4 , 1980.Google Scholar
- 13.D.J. Kuck, R.H. Kuhn, B. Leazure, M. Wolfe, "The structure of an advanced retcrgetable veetorizer~, in Kai Hwang ed., ~Tutorial on Supercomputers: Design and Applications", IEEE Press , pp. 163-178, 1984.Google Scholar
- 14.D. Gannon & W. Jalby, "Strategies/or Cache and Local Memory Management by Global Program Transformation", Journal of Parallel and Distributed Computing, Special Issue, To appear. Google ScholarDigital Library
- 15.P. Jouvelot, aParallglisation Semantique ", Rep. MASI, No 174, Universitd Paris 7, 1986.Google Scholar
- 16.A. Lichnewsky, M. Loyer, "Un Module Vectoriel Flottant cur SPSZ Pourquoi f', Bulletin de Liaison de la Recherche en Informatique et en A utomatique, no 112, 1987.Google Scholar
- 17.A. Lichnewsky, F. Thomasset, "Techniques de base sur l'exploitation au. tomatique du paralliliame dana Is8 programmes", Rapport de Recherche IN- RIA, nO. 460, Dec. 1985.Google Scholar
- 18.d. Moses, "Algebraic Simplification: A Guide for the Perplexed", Comm. A CM, Vol 14 No 8, August 1971. Google ScholarDigital Library
- 19.M.O. e bi , aDeeidable Theories", in Barwise J. ed., "Handbook of Mathematical Logic", North-Holland, 1977.Google Scholar
- 20.R.E. Shostak, ~Deciding Linear Inequalities by Computing Loop Residues", JA CM, Vo128, nO 4, October 1981, pp, 769- 779. Google ScholarDigital Library
- 21.R.E. Shostak, "On the Sup-Inf Method for Proving Preaburger formulas", JA CM, Vol 24, nO 4, October 1977, pp. 529-543. Google ScholarDigital Library
- 22.R.J. Triolet, Ulnterprocedural Analysis Based Program restructuring ", in M. Cosnard & al. ed., "Parallel Algorithms & Architectures", North Holland, 1986. Google ScholarDigital Library
- 23.M.J. Wolfe , "Techniques /or improving the inherent parallelism in programs~, rep. UIUCDCS-R-78-9~9, 1978.Google Scholar
- 24.A. Yasuhara, "Recursive Function Theory and Logic'~, Academic Press, 1977.Google Scholar
Index Terms
- Introducing symbolic problem solving techniques in the dependence testing phases of a vectorizer
Recommendations
Nonlinear and Symbolic Data Dependence Testing
One of the most crucial qualities of an optimizing compiler is its ability to detect when different data references access the same storage location. Such references are said to be data-dependent and they impose constraints on the amount of program ...
Classical dependence analysis techniques: sufficiently accurate in practice
HICSS '95: Proceedings of the 28th Hawaii International Conference on System SciencesData dependence analysis is the foundation of any parallelizing compiler. The GCD (greatest common divisor) test and the Banerjee-Wolfe test (U. Banerjee 1988, M. Wolfe 1989) are the two tests traditionally used to determine statement data dependence in ...
An empirical evaluation of chains of recurrences for array dependence testing
PACT '06: Proceedings of the 15th international conference on Parallel architectures and compilation techniquesCode restructuring compilers rely heavily on program analysis techniques to automatically detect data dependences between program statements. Dependences between statement instances in the iteration space of a loop nest impose ordering constraints that ...
Comments