Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
In compiler theory, loop dependence analysis is the task of determining whether statements within a loop body form a dependence, with respect to array access and modification, induction, reduction and private variables, simplification of loop-independent code and management of conditional branches...
In computer science a for loop is a programming language statement which allows code to be repeatedly executed. A for loop is classified as an iteration statement....
is made to be parallel so that it can be executed on more than one processor like in case of grid computing
Grid computing
Grid computing is a term referring to the combination of computer resources from multiple administrative domains to reach a common goal. The grid can be thought of as a distributed system with non-interactive workloads that involve a large number of files...
Cluster Computing: the Journal of Networks, Software Tools and Applications is a journal for parallel processing, distributed computing systems, and computer communication networks....
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
Statement (programming)
In computer programming a statement can be thought of as the smallest standalone element of an imperative programming language. A program written in such a language is formed by a sequence of one or more statements. A statement will have internal components .Many languages In computer programming...
, 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.
Dependency Analysis
It is difficult to analyze array references in compile time to determine data dependency (whether they point to same address or not). A simple and sufficient test for the absence of a dependence is the greatest common divisor (GCD) test. It is based on the observation that if a loop carried dependency exists between X[a*i + b] and X[c*i + d] (where X is the array; a, b, c and d are integers, and i is the loop variable), then GCD (c, a) must divide (d – b). The assumption is that the loop must be normalized
Normalized loop
In computer science, a normalized loop , is a loop which the loop variable starts at 0 and get incremented by one at every iteration until the exit condition is met...
– written so that the loop index/variable starts at 1 and gets incremented by 1 in every iteration. For example, in the following loop, a=2, b=3, c=2, d=0 and GCD(a,c)=2 and (d-b) is -3. Since 2 does not divide -3, no dependence is possible.
To 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 parallel. Similarly this test is conducted for all statements present in a given loop.
A concrete example source code in C would appear as:
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.
Automatic parallelization, also auto parallelization, autoparallelization, or parallelization, the last one of which implies automation when used in context, refers to converting sequential code into multi-threaded or vectorized code in order to utilize multiple processors simultaneously in a...
In compiler theory, the Banerjee test is a dependence test. The Banerjee test assumes that all loop indices are independent, however in reality, this is often not true. Banergee will always report a dependency if it exists, but it may also produce false positives .- References :* Randy Allen and...
In compiler theory, dependence analysis produces execution-order constraints between statements/instructions. Broadly speaking, a statement S2 depends on S1 if S1 must be executed before S2...
In compiler theory, loop dependence analysis is the task of determining whether statements within a loop body form a dependence, with respect to array access and modification, induction, reduction and private variables, simplification of loop-independent code and management of conditional branches...
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
