The dependence analysis: basic tests for data dependence

V. A. Evstigneev ; R. N. Arapbaev ; R. A. Osmonov

Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 10 (2007) no. 3, pp. 247-265.

Résumé

In this paper, a comparative review of tests for data dependence applied in parallelized compilers is presented. Comparisons of advantages and disadvantages of such tests using both examples and estimated characteristics of individual criteria are given. A comparative table of all considered tests is presented.

Bibliographie

[1] Evstigneev V. A., “Analiz zavisimostei: sostoyanie problemy”, Sistemnaya informatika / In-t sistem informatiki SO RAN, Vyp. 7, Nauka, Novosibirsk, 2000, 112–173, (Sb. nauch. tr.)

[2] Banerjee U., Data dependence in ordinary programs, Technical Rep. 76-837, Univ. III, Urbana, 1976

[3] Banerjee U., “An introduction to a formal theory of dependence analysis”, The J. of Supercomputing, 2 (1988), 133–149 | DOI

[4] Banerjee U., Dependence Analysis, Kluwer Academic Publishers, Boston, Mass., 1997 | Zbl

[5] Kong X., Klappholz D., and Pssaris K., “The I Test: An Improved Dependence Test for Automatic Parallelization and Vectorization”, IEEE Transactions on Parallel and Distributed Systems, 2:3 (1991), 342–349 | DOI

[6] Li Z., Yew P.-C., Zhu C.-Q., “An efficient data dependence analysis for parallelzing compilers”, IEEE Transaction on Parallel and Distributed Systems, 1:1 (1990), 26–34, (January) | DOI

[7] Goff G., Kennedy K., and Tseng C., “Practical Dependence Testing”, Proc. of the ACM SIGPLAN 91 Conf. on Programming Language Design and Implementation (June), 1991, 15–29

[8] Wolfe M., and Tseng C., “The Power Test for Data Dependence”, IEEE Transactions on Parallel and Distributed Systems, 3:5 (1992), 591–601, (September) | DOI

[9] Pugh W., “The Omega test: a fast and practical integer programming algorithm for dependence analysis”, Communications of the ACM, 35:8 (1992), 102–114, (August) | DOI

[10] Pugh W., and Speismean T., On Fast Array Data Dependence Tests (January), Univ. of Maryland, College Park, Maryland, 1999

[11] Huang T.-C., and Yang C.-M., “Data dependence analysis for array references”, J. of Systems and Software, 52 (2000), 55–65 | DOI

[12] Maydan D., Hennessy J., and Lam M., “Efficient and Exact Data Dependence Analysis”, Proc. of the SIGPLAN Conf. on Programming Language Design and Implementation (June 1991), 1991, 1–14

[13] Shen Z., Li Z., Yew P.-C., “An empirical study of Fortran programs for parallelizing compilers”, IEEE Transactions on Parallel and Distributed Systems, 1:3 (1992), 356–364 | DOI

[14] Eisenbeis C., Sogno J.-C., “A general algorithm for data dependence analysis”, Proc. of the Sixth ACM International Conference on Supercomputing (July 1992), Washington, DC, 1992, 292–302

[15] Dantzig G., Eaves B., “Fourier–Motzkin Elimination and its Dual”, J. of Combinatorial Theory. A, 14 (1973), 288–297 | DOI | MR | Zbl

[16] Wallace D. R., “Dependence of multi-dimensional array references”, Proc. of International Conf. Supercomputing (Saint-Malo, France, July 1988), 1988, 418–428

[17] Shostak R., “Deciding linear inequalities by computing loop residues”, ACM J., 28:4 (1981), 769–779, (October) | DOI | MR | Zbl

[18] Psarris K., “On exact data dependence analysis”, Proc. of the Sixth ACM International Conference on Supercomputing (July 1992), Washington, DC, 1992, 303–312

[19] Psarris K., Klappholz D., Kong X., “On the accuracy of the Banerjee test, shared memory multiprocessors (special issue)”, J. Parallel Distrib. Comput., 12:2 (1991), 152–157 | DOI | MR | Zbl

[20] Psarris K., “Program analysis techniques for transforming programs for parallel execution”, Parallel Computing, 28 (2002), 455–469 | DOI | Zbl

[21] Chang W.-L., Chu C.-P., and Wu J., “The generalized Lambda test”, Proc. of the First Merged Symposium on IPPS/SPDP (March 1998), Orlando, FL, 1998, 181–186

[22] Chang W.-L., Chu C.-P., “The infinity Lambda test: A multi-dimensional version of Banerjee infinity test”, Parallel Computing, 26 (2000), 1275–1295 | DOI | Zbl

[23] Psarris K., Kong X., Klappholz D., “The direction vector I test”, IEEE Transactions on Parallel and Distributed Systems, 4:11 (1993), 1280–1290 | DOI

[24] Chang W.-L., Chu C.-P., Wu J., “A multi-dimensional version of the I test”, Parallel Computing, 27 (2001), 1783–1799 | DOI | Zbl

[25] Chang W.-L., Chu C.-P., Wu J., “A precise dependence analysis for multi-dimensional arrays under specific dependence direction”, J. of Systems and Software, 63 (2002), 99–112 | DOI

[26] Huang T.-C., and Yang C.-M., “Data dependence analysis with direction vector for array references”, Computers and Electrical Engineering, 27 (2001), 375–393 | DOI | Zbl

[27] Arapbaev R. N., Osmonov R. A., “Novyi algoritm analiza zavisimostei po dannym v mnogomernykh massivakh”, Tez. dokl. VI Vserossiiskaya konf. molodykh uchenykh po matematicheskomu modelirovaniyu i informatsionnym tekhnologiyam, Kemerovo, 2005, 57

[28] Drozdov A. Yu., Kornev R. M., Bokhanko A. S., “Indeksnyi analiz zavisimostei po dannym”, Informatsionnye tekhnologii i vychislitelnye sistemy, 3 (2004), 27–37

[29] Yang C.-T., Tseng S.-S., and Shih W.-C., “The K Test: an Exact and Efficient Knowledge-based Data Dependence Testing Method for Parallelizing Compilers”, Proc. Natl. Sci. Counc. ROC(A), 24:5 (2000), 362–372

[30] Logacheva S. A., “Analiz zavisimostei po dannym na baze algoritma Shostaka”, Podderzhka supervychislenii i internet-orientirovannye tekhnologii, Novosibirsk, 2001, 31–43 | Zbl