An Integrated Array Dependence Test Method Based on Banerjee-GCD and Banerjee-Bound Method
Ma Guo · Chinese Journal of Computers · 2002
Dependence test is the most important part in a parallelizing compiler. There are many results on it: some are precise but slow, some are fast but only make an estimation on the dependence directions. Designing a good dependence test algorithm needs sophisticated negotiating between speed and accuracy. Our dependence test method is based on the Banerjee GCD and Banerjee Bound methods. Considering the most common cases in the test suit, we design our dependence test method for the purpose of loop parallelization. We find out that not all the dependence direction contribute equally to loop parallelization. A test of a small portion of the whole set of dependence directions covers most loop inter iteration dependences. So we test these directions in order to reduce the time complexity of the algorithm. Furthermore, rather than issue a new mathematical model to solve the linear equations, we use the information we could get in GCD and Bound test to extend the original algorithm. The main idea is: GCD test can find out a set of possible dependence vectors, then Bound test could check each bits of the vector and eliminate some dependence directions, which in fact does not exist. Further more, we could exchange information between GCD and Bound test to get more efficiency from the original one. Using the dependence distance, loop bounds, etc. in both GCD and Bound test, we could exploit the maximum precision out of these two famous fast dependence testing methods while preserving the high speed performance of our method. As a matter of fact, we even try to extend the original GCD and Bound test method to make it support non linear equations. By integrating these two dependence test method into one single algorithm and make the maximum use of them, we could provide a fast and ambitious dependence test method for the purpose of program parallelization.