The Accuracy of the Non-continuous I Test for One- Dimensional Arrays with References Created by Induction Variables
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
One-dimensional arrays with subscripts formed by induction variables inreal programs appear quite frequently. For most famous data dependence testingmethods, checking if integer-valued solutions exist for one-dimensional arrays withreferences created by induction variable is very difficult. The I test, which is a refinedcombination of the GCD and Banerjee tests, is an efficient and precise data dependencetesting technique to compute if integer-valued solutions exist for one-dimensionalarrays with constant bounds and single increments. In this paper, the non-continuous Itest, which is an extension of the I test, is proposed to figure out whether there areinteger-valued solutions for one-dimensional arrays with constant bounds and non-singularincrements or not. Experiments with the benchmarks that have been cited fromLivermore and Vector Loop, reveal that there are definitive results for 67 pairs of onedimensionalarrays that were tested.
Abstract
One-dimensional arrays with subscripts formed by induction variables inreal programs appear quite frequently. For most famous data dependence testingmethods, checking if integer-valued solutions exist for one-dimensional arrays withreferences created by induction variable is very difficult. The I test, which is a refinedcombination of the GCD and Banerjee tests, is an efficient and precise data dependencetesting technique to compute if integer-valued solutions exist for one-dimensionalarrays with constant bounds and single increments. In this paper, the non-continuous Itest, which is an extension of the I test, is proposed to figure out whether there areinteger-valued solutions for one-dimensional arrays with constant bounds and non-singularincrements or not. Experiments with the benchmarks that have been cited fromLivermore and Vector Loop, reveal that there are definitive results for 67 pairs of onedimensionalarrays that were tested.
참고문헌 (35)
- Z. Shen, "An empirical study of Fortran programs for parallelizing compilers", IEEE Transactions on Parallel and Distributed Systems, 1(3), pp.356~364 (1990)
- C. I. Jaramillo, "Source level debugging techniques and tools for optimized code", 박사, pp.2000
- U. Banerjee, "Dependence Analysis for Supercomputing" (1988), Kluwer Academic Publishers
- Z. Li, "An efficient data dependence analysis for parallelizing compilers", IEEE Transactions on Parallel and Distributed Systems, 1(1), pp.26~34 (1990)
- R. Eigenmann, "On the automatic parallelization of the Perfect Benchmarks(R)", IEEE Transactions on Parallel and Distributed Systems, 9(1), pp.5~23 (1988)
- W. Blume, "Nonlinear and symbolic data dependence testing", IEEE Transactions on Parallel and Distributed Systems, 9(12), pp.1180~1194 (1998)
- J. P. Hoeflinger, "Interprocedural parallelization using memory classification analysis", 박사, pp.1998
- J. Dongarra, "Parallel Loops : a test suite for parallelizing compilers : description and example results", Parallel Computing, 17(10), pp.1247~1255 (1991)
- K. Psarris, "On the accuracy of the Banerjee test", Journal of Parallel and Distributed Computing, 12(2), pp.152~157 (1991)
- W. Pugh, "A practical algorithm for exact array dependence analysis", Communications of the ACM, 35(8), pp.102~114 (1992)
- M. Wolfe, "The power test for data dependence", IEEE Transactions on Parallel and Distributed Systems, 3(5), pp.591~601 (1992)
- W. J. Vaughan, "A residuals management model of the iron and steel industry: a linear programming approach", 박사, pp.1975
- R. Triolet, "Direct parallelization of call statements", Proceedings of the SIGPLAN Symposium on Compiler Construction, pp.176~185 (1986)
- X. Kong, "The I test : an improved dependence test for automatic parallelization and vectorization", IEEE Transactions on Parallel and Distributed Systems, 2(3), pp.342~349 (1991)
- P. M. Petersen, "Evaluation of programs and parallelizing compilers using dynamic analysis techniques", 박사, pp.1993
- U. Banerjee, "Loop Transformations for Restructuring Compilers: The Foundations" (1993), Kluwer Academic Publishers
- U. Banerjee, "Dependence Analysis" (1997), Kluwer Academic Publishers
- Y. Paek, "Compiling for distributed memory multiprocessors based on access region analysis", 박사, pp.1997
- K. Psarris, "The direction vector I test", IEEE Transactions on Parallel and Distributed Systems, 4(11), pp.1280~1290 (1993)
- K. Psarris, "Data dependence testing in practice", Proceedings of the International Conference on Parallel Architectures and Compilation Techniques, pp.264~273 (1999)
- D. Niedzielski, "An analytical comparison of the I-test and Omega test", Proceedings of the 12th International Workshop on Languages and Compilers for Parallel Computing (LCPC1999), pp.251~270 (1999)
- B. T. Smith, "Matrix Eigensystem Routines-EISPACK Guide" (1976), Springer
- D. E. Knuth, "The Art of Computer Programming, Volume 2: Seminumerical Algorithms" (1981), Addison-Wesley
- W. L. Chang, "The extension of the I test", Parallel Computing, 24(14), pp.2101~2127 (1998)
- W. L. Chang, "The generalized lambda test : a multi-dimensional version of Banerjee's algorithm", International Journal of Parallel and Distributed Systems and Networks, 2(2), pp.69~78 (1999)
- T. C. Huang, "Data dependence analysis for array references", Journal of Systems and Software, 52(1), pp.55~65 (2000)
- W. L. Chang, "The non-continuous I test: an improved dependence test for reducing complexity of source level debugging for parallel compilers", Proceedings of the 3rd International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT2002), pp.455~462 (2002)
- W. L. Chang, "The generalized direction vector I test", Parallel Computing, 27(8), pp.1117~1144 (2001)
- W. L. Chang, "A multi-dimensional version of the I test", Parallel Computing, 27(13), pp.1783~1799 (2001)
- J. Hoeflinger, "A comparative analysis of dependence testing mechanisms", Proceedings of the 13th International Workshop on Languages and Compilers for Parallel Computing (LCPC2000), pp.289~303 (2001)
- W. L. Chang, "A multi-dimensional direction vector I test", Journal of System and Software
- D. Levine, "A comparative study of automatic vectorizing compilers", Parallel Computing, 17(10), pp.1223~1244 (1991)
- W. Blume, "Performance analysis pf parallelizing compilers on the Perfect Benchmarks programs", IEEE Transactions on Parallel and Distributed Systems, 3(6), pp.643~656 (1992)
- P. M. Petersen, "Static and dynamic evaluation of data dependence analysis techniques", IEEE Transactions on Parallel and Distributed Systems, 7(11), pp.1121~1132 (1996)
- K. Psarris, "An experimental evaluation of data dependence analysis techniques", IEEE Transactions on Parallel and Distributed Systems, 15(3), pp.196~213 (2004)