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 compiler theroy to test the dependency between loop statements. If two statements are indexing to same array using same index variable,then this test can be conducted to test wheather there is any dependency between the statement.
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 it can be said that there may be some dependency in the loop statement s1 and s2. 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