Static and dynamic evaluation of data dependence analysis techniques

Paul M. Petersen, David A. Padua

Research output: Contribution to journalReview articlepeer-review


Data dependence analysis techniques are the main component of today's strategies for automatic detection of parallelism. Parallelism detection strategies are being incorporated in commercial compilers with increasing frequency because of the widespread use of processors capable of exploiting instruction-level parallelism and the growing importance of multiprocessors. An assessment of the accuracy of data dependence tests is therefore of great importance for compiler writers and researchers. The tests evaluated in this study include the generalized greatest common divisor test, three variants of Banerjee's test, and the Omega test. Their effectiveness was measured with respect to the Perfect Benchmarks and the linear algebra libraries, EISPACK and LAPACK. Two methods were applied, one using only compile-time information for the analysis, and the second using information gathered during program execution. The results indicate that Banerjee's test is for all practical purposes as accurate as the more complex Omega test in detecting parallelism. However, the Omega test is quite effective in proving the existence of dependences, in contrast with Banerjee's test, which can only disprove, or break dependences. The capability of the Omega test of proving dependences could have a significant impact on several compiler algorithms not considered in this study.

Original languageEnglish (US)
Pages (from-to)1121-1132
Number of pages12
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number11
StatePublished - 1996


  • Automatic parallelization
  • Compiler optimizations
  • Dependence analysis
  • Evaluation of compiler techniques
  • Parallelism detection

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Static and dynamic evaluation of data dependence analysis techniques'. Together they form a unique fingerprint.

Cite this