GCD test

In compiler theory of computer science, A GCD Test is the test used in study of loop optimization and loop dependence analysis to test the dependency between loop statements.

Whenever a sequential loop like for loop is made to be parallel so that it can be executed on more than one processors like in case of grid computing or cluster computing then certain dependencies are checked to know whether this loop can be parallelized or not: for instance, testing the flow (true) dependence of a statement. According to this test, by comparing the indices of two arrays present in two or more statements, it can be calculated whether it is legal to parallelize the loop or not.

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

Process

Loop code in general:

for (int i=0;i<n;i++) 
{
 s1   a[x*i+k] = b[i]; 
 s2   c[i] = a[y*i+m];                
}

If GCD(x,y) divides (m-k) then there may exist some dependency in the loop statement s1 and s2. If GCD(x,y) does not divisible by (m-k) then both statements are independent and can be executed at parrellel.Similarly this test is conducted for all statements present in a given loop. An example source code in C would appear as:

for(int i=0;i<100;i++)
{
 s1 a[2*i]=b[i];
 s2 c[i]=a[4*i+1];
}

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 varoous other loop transformation methods can be applied.

References

• Advanced Compiler Design and Implementation by Steven S Muchnick