Zhiyuan Li
Pen-Chung Yew
ABSTRACT
An efficient and precise data dependence analysis is the key to the success of a parallelizing compiler because it is required in almost all phases of the parallelism detection and enhancement in such compilers. However, existing test algorithms are quite weak in analyzing multi-dimensional array references, which are usually where the parallelism is in most programs.
In this paper, a new algorithm, called λ-test, is presented for an efficient and accurate data dependence analysis on multi-dimensional array references. It achieves high efficiency and high accuracy at the same time, which is in general not allowed in previous algorithms. This algorithm has been implemented in Parafrase [Wolf82]. Some experimental results are also presented to show its effectiveness.
- Alle83.J.R. Alien, "Dependence Analysis for Subscripted Variables And its Application to Program Transformations," Ph.D. Thesis, Department of Mathematical Sciences, Rice University, Houston, TX, April 1983. Google Scholar
Digital Library
- Bane88.U. Banerjee, Dependence Analysis for $upercomputing, Kluwer Academic Publishers, Norwell, Mass., 1988. Google ScholarDigital Library
- CoHa78.P. Cousot, N. Halbwacks, "Automatic Discovery of Linear Restraints among Variables of a Program," Conf. Record of the 5-th Annual A CM Syrup. on Principle of Program Languages, 1978. Google ScholarDigital Library
- KKPL81.D. Kuck, R. Kuhn, D. Padua, B. Leasure and M. Wolfe, "Dependence Graphs and Compiler Organizations," Proc. of the 8th A CM Syrup. on Principles of Programming Languages (POPL), Williamsburgh, VA, pp. 207-218, Jan. 1981. Google ScholarDigital Library
- Kuhn80.R. Kuhn, "Optlmlzatlon And Interconnection Complexity for' Parallel Processors, Single-Stage Networks, And Decision Trees," Ph.D. Thesis, Department of Computer Science, University of Illinois at Urbana-Champalgn, Rpt. No. UIUCDCS-R-80-1009, Feb. 1980. Google ScholarDigital Library
- Li89.Z. Li, "Intraprocedural and Interprocedural Data Dependence Analysis for Parallel Computing," Ph.D. Dissertation in preparation, Dept. of Computer Science, University of Illinois at Urbana- Champaign, 1989. Google ScholarDigital Library
- LiTh88.A. Lichnewsky and F. Thomasset, "Introducing Symbolic Problem Solving Techniques in the Dependence Testing Phase of a Vectorizer," Proc. of 1988 Int'l Conf. on Supercomputing, St. Mato, France, July 1988. Google ScholarDigital Library
- ShLY89."An Empirical Study on Array Subscripts and Data Dependences," To appear in Proe. of 1989 Int' Conf. on Parallel Processing.Google Scholar
- Shos81.R. Shostak, "Deciding Linear Inequalities by Computing Loop Residues," ACM Journal vol. 28(4), pp. 769-779 (Oct 1981). Google ScholarDigital Library
- Smit76.B.J. Smith, et al., Matrix Eigensystem Routines - Eispack Guide, Springer- Verlag, Heidelberg, 1976.Google Scholar
- Trio85.R. Triolet, "Interprocedural Analysis for Program Restructuring with Parafrase," CSRD Rpt. No. 538, University of Illinois at Urbana-Champaign, Dec. 1985.Google Scholar
- TrIF86.R. Triolet, F. Irigoin, P. Feautrier, "Direct Parallelization of CALL Statements," Proceedings of the ACM SIG- PLAN '86 Symp. on Compiler Construction, SIGPLAN Notices, Vol. 21, No. 6, June 1986. Google ScholarDigital Library
- Wall88.D.R. Wallace, "Dependence of Multi- Dimensional Array References," Proc. of 1988 Int'l Conf. on Supercomputing, St. Malo, France, July 1988. Google ScholarDigital Library
- Wolf82.M.J. Wolfe, "Optimizing Supercompilers for Supercomputers," Ph.D. thesis, Univ. of Illinois at Urbana-Champaign, DCS Report No. U1LICDCS-R-82-1105, Oct. 1982. Google ScholarDigital Library
Index Terms
- Data dependence analysis on multi-dimensional array references
Recommendations
Constraint-based array dependence analysis
Traditional array dependence analysis, which detects potential memory aliasing of array references is a key analysis technique for automatic parallelization. Recent studies of benchmark codes indicate that limitations of analysis cause many compilers ...
Expressing cross-loop dependencies through hyperplane data dependence analysis
Supercomputing '94: Proceedings of the 1994 ACM/IEEE conference on SupercomputingTraditional dependence analysis techniques usually attempt to recognize the existence of dependencies between iterations of a loop and, in some cases, characterize these dependencies by finding direction vectors or distance vectors. In this paper, a ...
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 ...
Comments