DocumentCode :
288991
Title :
Classical dependence analysis techniques: sufficiently accurate in practice
Author :
Psarris, Kleanthis ; Pande, Santosh
Author_Institution :
Div. of Comput. Sci., Texas Univ., San Antonio, TX, USA
Volume :
2
fYear :
1995
fDate :
3-6 Jan 1995
Firstpage :
123
Abstract :
Data 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 automatic vectorization/parallelization of loops. These tests are approximate in the sense that they are necessary but not sufficient conditions for data dependence. In an earlier work (Proc. 6th ACM Int. Conf. Supercomputing, Washington, DC, USA, July 1992), we extended the Banerjee-Wolfe test and a combination of the GCD and Banerjee-Wolfe tests with a set of conditions to derive exact data dependence information. In this paper, we perform an empirical study on the Perfect benchmarks to demonstrate the effectiveness and practical importance of our conditions. We show that the Banerjee-Wolfe test extended with our conditions becomes an exact test for data dependence in actual practice
Keywords :
data analysis; parallelising compilers; program control structures; program diagnostics; program testing; Banerjee-Wolfe test; GCD test; Perfect benchmarks; accuracy; automatic loop parallelization; automatic vectorization; data dependence analysis; exact test; greatest common divisor; parallelizing compilers; statement data dependence; sufficient conditions; Automatic testing; Benchmark testing; Computer science; Data analysis; Equations; Linear programming; NP-hard problem; Performance analysis; Program processors; Sufficient conditions;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
System Sciences, 1995. Proceedings of the Twenty-Eighth Hawaii International Conference on
Conference_Location :
Wailea, HI
Print_ISBN :
0-8186-6930-6
Type :
conf
DOI :
10.1109/HICSS.1995.375470
Filename :
375470
Link To Document :
بازگشت