A general data dependence analysis to nested loop using integer interval theory
Jing Zhou, Guosun Zeng · 2006
Many dependence tests have been proposed for loop parallelization in the case of arrays with linear subscripts, but little work has been done on the arrays with non-linear subscripts, which sometimes occur in parallel benchmarks and scientific and engineering applications. This paper focuses on array subscripts coupled integer power index variables. We attempt to use the integer interval theory to solve the above difficult dependence test problem. Some “interval solution ” rules for polynomial equations have been proposed in this paper. Furthermore, based on the proposed rules, we present a novel approach to loop de-pendence analysis, which is termed the Polynomial Vari-able Interval test or PVI-test, and also develop a related algorithm. Some case studies show that the PVI-test is effective and efficient. Compared to the VI test, the PVI-test makes significant improvement, and is therefore a more general scheme of dependence test. 1