An Efficient Data Dependence Analysis for Parallelizing Compilers

Zhiyuan Li, Pen Chung Yew, Chuan Qi Zhu

Research output: Contribution to journalArticlepeer-review

83 Scopus citations

Abstract

An efficient and precise data dependence analysis is the key to the success of a parallelizing compiler because it is required in almost all phases of the parallelism detection and enhancement in such compilers. However, existing test algorithms are quite weak in analyzing multidimensional array references, which are usually where the parallelism is in most programs. There are basically two approaches in dependence testing. The first approach is based on numerical methods. This approach tests array references dimension by dimension, thus it may lose accuracy when references have coupled subscripts. The second approach is based on checking the consistency of a set of inequalities. It tests multiple dimensions simultaneously, and hence can greatly enhance the accuracy. However, this approach is very time consuming. In this paper, a new algorithm, called the δ test, is presented for an efficient and accurate data dependence analysis of multidimensional array references. It extends the numerical methods to allow all dimensions of array references to be tested simultaneously. Hence, it combines the efficiency and the accuracy of the both approaches. This algorithm has been implemented in Parafrase [22], a Fortran program parallelization restructurer developed at the University of Illinois at Urbana-Champaign. Some experimental results are also presented to show its effectiveness.

Original languageEnglish (US)
Pages (from-to)26-34
Number of pages9
JournalIEEE Transactions on Parallel and Distributed Systems
Volume1
Issue number1
DOIs
StatePublished - Jan 1990

Keywords

  • Array subscripts
  • compilers
  • convex set
  • data dependence analysis
  • hyperplanes
  • linear (in)equalities
  • loop bounds
  • program parallelization

Fingerprint

Dive into the research topics of 'An Efficient Data Dependence Analysis for Parallelizing Compilers'. Together they form a unique fingerprint.

Cite this