GCD test

In compiler theory, a greatest common divisor test (GCD test) is the test used in study of loop optimization and loop dependence analysis to test the dependency between loop statements.

In compiler theory, a greatest common divisor test (GCD test) is the test used in study of loop optimization and loop dependence analysis to test the dependency between loop statements.

Theorem

A linear Diophantine equation a1*x1 + a2*x2 +... + an*xn = c has an integer solution x1, x2, ..., xn iff GCD(a1, a2, ..., an) divides c. E.g. 2*x1 -2*x2 = 1 GCD(2, -2) = 2, 2 cannot divide 1. So, there is no integer solution for the equation above. It is difficult to analyze array references in compile time to determine data dependency (whether they point to same address or not). A simple and sufficient test for the absence of a dependence is the greatest common divisor (GCD) test. It is based on the observation that if a loop carried dependency exists between X[a*i + b] and X[c*i + d] (where X is the array; a, b, c and d are integers, and i is the loop variable), then GCD (c, a) must divide (d – b). The assumption is that the loop must be normalized – written so that the loop index/variable starts at 1 and gets incremented by 1 in every iteration. For example, in the following loop, a=2, b=3, c=2, d=0 and GCD(a,c)=2 and (d-b) is -3. Since 2 does not divide -3, no dependence is possible. for (i=1; i

Process

Loop code in general: for (int i=0; i for (int i=0; i The GCD of (2, 4) is 2 and dividend is 1. As 2 can not divide 1 properly (leaving remainder zero), there is no dependency between s1 and s2 and various other loop transformation methods can be applied.

See also

Automatic parallelization Banerjee test Dependence analysis Loop dependence analysis

References

Advanced Compiler Design and Implementation by Steven S Muchnick

Text derived from https://en.wikipedia.org/w/index.php?oldid=1337867737 under CC BY-SA 4.0; modifications have been made.