Banerjee-GCD与Banerjee-Bound联合数组相关性测试

An Integrated Array Dependence Test Method Based on Banerjee-GCD and Banerjee-Bound Method

以 Banerjee- GCD方法和 Banerjee- Bound方法为基础 ,充分考虑了两者的测试结果之间的相互影响以及程序并行化对相关性测试的要求 ,从而提出了一个在统一的框架下利用 Banerjee- GCD方法与 Banerjee- Bound方法对不同的相关向量进行测试的联合数组相关性测试方法 .该方法在保持执行时间效率的前提下提高了测试的精确性和结果的有效性 。

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.