Li Li, Minyi Guo and Weng-Long Chang
Southern Taiwan University of Technology
and University of Aizu at Taiwan
and
University of Aizu in Japan
Contact Author: Minyi Guo
E-mail: minyi@u-aizu.ac.jp
In automatic parallelization and parallelizing compilers, achieving a good data dependence analysis is a critical issue in order to reduce the communication overhead and to exploit parallelism of applications as much as possible. It is essential to develop a new analysis technique for data dependence. This motivates us that we are not only to develop traditional dependence tests for parallelizing transformation but also to develop new techniques for multi-dimensional induction variables that frequently occur in nested loops.
there are integer-valued solutions for two-dimensional arrays with subscripts formed by induction variable.
An induction variable is a scalar integer variable, which is used in a loop to simulate do-variables: it is incremented or decremented by a constant in each iteration. Every induction variable can be replaced by a linear function of the loop's index-variables.
The proposed method can offer data dependence analysis for arrays with references formed by induction variable. Depending on the application domains, we suggest to applying the proposed method together with the front-end of a parallelizing compiler to provide data dependence analysis for arrays with references formed by induction variable.