GCD test
It is proposed that this article be deleted because of the following concern:
If you can address this concern by improving, copyediting, sourcing, renaming, or merging the page, please edit this page and do so. You may remove this message if you improve the article or otherwise object to deletion for any reason. Although not required, you are encouraged to explain why you object to the deletion, either in your edit summary or on the talk page. If this template is removed, do not replace it. This message has remained in place for seven days, so the article may be deleted without further notice. Find sources: "GCD test" – news · newspapers · books · scholar · JSTOR Nominator: Please consider notifying the author/project: {{subst:proposed deletion notify|GCD test|concern=possibly notable, but unclear: no context given.}} ~~~~Timestamp: 20070516124724 12:47, 16 May 2007 (UTC) Administrators: delete |
A GCD Test is the test used in study of loop optimizations loop optimization to test the dependency between loop statements. Whenever a sequential loop like for loop is made to be paralle so that it can be executed on more than one machine like in case of grid computing or cluster computing then certain dependencies are checked to know whether this loop can be parallalized or not.One of which is to test flow dependence of statement.According to this test by comapring the indexes of two array presenmt in two or more statements it can be calculated that whether it is legal to split the loop or not.
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 parrelley.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