An experimental evaluation of data dependence analysis techniques

• Published in: IEEE transactions on parallel and distributed systems 2004-03, Vol.15 (3), p.196-213
• Main Authors: Psarris, K., Kyriakopoulos, K.
• Format: Article
• Language: English
• Subjects: Accuracy; Algorithms; Approximation; Automatic testing; Benchmark testing; Benchmarks; Clubs; Compilers; Constraint optimization; Costs; Data analysis; Dependence; Efficiency; Equations; Handles; Libraries; Load management; Mathematical analysis; Optimization; Optimizing compilers; Parallel processing; Program processors; Studies; Transformations
• ISSN: 1045-9219; 1558-2183
• DOI: 10.1109/TPDS.2004.1264806

Optimizing compilers rely upon program analysis techniques to detect data dependences between program statements. Data dependence information captures the essential ordering constraints of the statements in a program that need to be preserved in order to produce valid optimized and parallel code. Data dependence testing is very important for automatic parallelization, vectorization, and any other code transformation. In this paper, we examine the impact of data dependence analysis in practice. A number of data dependence tests have been proposed in the literature. In each test, there are different trade offs between accuracy and efficiency. We present an experimental evaluation of several data dependence tests, including the Banerjee test, the I-Test, and the Omega test. We compare these tests in terms of data dependence accuracy, compilation efficiency, effectiveness in parallelization, and program execution performance. We analyze the reasons why a data dependence test can be inexact and we explain how the examined tests handle such cases. We run various experiments using the Perfect Club Benchmarks and the scientific library Lapack. We present the measured accuracy of each test and the reasons for any approximation. We compare these tests in term's of efficiency and we analyze the trade offs between accuracy and efficiency. We also determine the impact of each data dependence test on the total compilation time. Finally, we measure the number of loops parallelized by each test and we compare the execution performance of each benchmark on a multiprocessor. Our results indicate that the Omega test is more accurate, but also very inefficient in the cases where the other two tests are inaccurate. In general, the cost of the Omega test is high and uses a significant percentage of the total compilation time. Furthermore, the difference in accuracy of the Omega test over the Banerjee test and the l-Test does not improve parallelization and program execution performance.