Dependence testing on loops with bounds which are functions of outer loop indices


Suzana Stojković




Parallelizing compilers are compilers which translate sequential programs into parallel ones. Program loops are the most frequent sources of parallelism in sequential programs. Because of that, parallelizing compilers first must detect loops which can be run in parallel. Different iterations of the same loop can execute in parallel if they process different data. Parallel loops can be identified by detecting data dependencies across the loop body. For data dependence testing a few algorithms were developed. In this paper GCD test and Banerjee's test are presented. These algorithms are applicable when bounds of loop indices are constant. This paper shows how Banerjee's test can be exploited ivhen the inner loop bounds are functions of outer loops indices. We, first, must compute minimums of the lower and maximums of the upper loop bounds. We solved this problem when the loop bounds are linear functions. We shoiu that this minimums and maximums are dependent on the data dependence direction vector. We have also modified Banerjee's test, slightly.