GCD test
This article may meet Wikipedia's criteria for speedy deletion as a very short article lacking sufficient context to identify the subject of the article. See CSD A1.
If this article does not meet the criteria for speedy deletion, or you intend to fix it, please remove this notice, but do not remove this notice from pages that you have created yourself. If you created this page and you disagree with the given reason for deletion, you can click the button below and leave a message explaining why you believe it should not be deleted. You can also visit the talk page to check if you have received a response to your message. Note that this article may be deleted at any time if it unquestionably meets the speedy deletion criteria, or if an explanation posted to the talk page is found to be insufficient.
Note to administrators: this article has content on its talk page which should be checked before deletion. Administrators: check links, talk, history (last), and logs before deletion. Consider checking Google.This page was last edited by Guycalledryan (contribs | logs) at 06:44, 16 May 2007 (UTC) (18 years ago) |
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