GCD test

GCD test

In compiler theory of computer science, A Greatest common divisor 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.

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.

Process

Loop code in general: for (int i=0;iTo decide if there is loop carried dependence (two array references access the same memory location and one of them is a write operation) between a [x*i+k] and a [y*i+m] , one usually need to solve the equation

x*i1 +k = y*i2+m (Or x*i1 -y*i2 = m -k)

Where 0<=i1, i2 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 divide (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.

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

ee also

* Automatic parallelization
* Dependence analysis
* Loop dependence analysis

References

*Advanced Compiler Design and Implementation by Steven S Muchnick


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • AKS primality test — The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality proving algorithm created and published by three Indian Institute of Technology Kanpur computer scientists, Manindra… …   Wikipedia

  • Primality test — A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating… …   Wikipedia

  • Miller–Rabin primality test — The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay–Strassen primality test. Its original version …   Wikipedia

  • Fermat primality test — The Fermat primality test is a probabilistic test to determine if a number is probably prime. ConceptFermat s little theorem states that if p is prime and 1 le a < p, then :a^{p 1} equiv 1 pmod{p}If we want to test if p is prime, then we can pick …   Wikipedia

  • Loop dependence analysis — In compiler theory, loop dependence analysis is the task of determining whether statements within a loop body form a dependence, almost always with respect to array access and modification. For a normalized loop: for i1 from l1 to u1 do for i2… …   Wikipedia

  • JavaScript syntax — This article is part of the JavaScript series. JavaScript JavaScript syntax JavaScript topics This box: view · …   Wikipedia

  • Coppersmith's Attack — describes a class of attacks on the public key cryptosystem RSA based on Coppersmith s theorem (see below). The public key in the RSA system is a tuple of integers (N,e), where N is the product of two primes p and q. The secret key is given by an …   Wikipedia

  • Fibonacci number — A tiling with squares whose sides are successive Fibonacci numbers in length …   Wikipedia

  • Fermat number — In mathematics, a Fermat number, named after Pierre de Fermat who first studied them, is a positive integer of the form:F {n} = 2^{2^{ overset{n} {} + 1where n is a nonnegative integer. The first nine Fermat numbers are OEIS|id=A000215:As of|2008 …   Wikipedia

  • Kloosterman sum — In mathematics, a Kloosterman sum is a particular kind of exponential sum. Let a , b , m be natural numbers. Then :K(a,b;m)=sum {0leq xleq m 1, gcd(x,m)=1 } e^{2pi i (ax+bx^*)/m},Here x* is the inverse of x modulo m . They are named for the Dutch …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”