Assignment DATA DEPENDENCY ANALYSIS

Certain code segments, like a=b+c; a=c+d; can not be run in parallel because:
a) Lack of hardware.
b) Show Dependency/ Unpredictable results.
c) Lack of knowledge.
d) Ease to run sequentially.
Which of the following does not show dependency?
e) a=b+c; d=a*a;
f) a=b+c; b=a*a;
g) a=b+c; a=c+d;
h) a=b+c; e=x-y;
What is the source of Dependency in a program segment?
i) Control.
j) Data.
k) Resource.
l) All of the above.
The set of statements used to formalize the notion of dependency are_________ and _________.
Which of the following shows a real dependence?
m) Output dependence.
n) Input dependence.
o) Flow dependence.
p) Anti- dependence.
If intersection of DEF (S2) & USE (S1) is not an empty set, then it satisfies which dependency?
q) True dependence.
r) Output dependence.
s) Anti- dependence.
t) Input dependence.
__________ dependence & __________ dependence exist in imperative programming.
If S1 & S2 are dependent and S2 & S3 are dependent, then it implies that S1 & S3 are also dependent.
u) True.
v) False.
________ are a direct source of Parallelism.
Equations requiring integer solutions are called ______________.
X [ k+1 ] = X [k] + A [k ] shows which type of dependence?
w) Output dependence.
x) Flow dependence.
y) Anti- dependence.
z) None of the above.

A test used to check loop dependence is ___________.
Diophantine equations can be solved using a mathematical solution strategy?
aa) True.
bb) False.
While computing dependency in loops, we consider arrays as:
cc) Variable.
dd) Subscript.
ee) Both (a) & (b).
ff) None of the above.
Loop dependence may analyze:
gg) If different statements in loop body can be executed in parallel.
hh) If different iterations of a loop can be executed in parallel.
ii) Both (a) & (b).
jj) None of the above.
If a test solution states that there is no solution of an equation, then it implies there is no dependence & vice versa.
kk) True.
ll) False.
The relation DEF (S1) intersection USE (S2) != { } implies:
mm) Output dependence.
nn) True dependence.
oo) Input dependence.
pp) Anti- dependence.
Code segments can be parallelized without any threat in:
qq) Flow dependence.
rr) Output dependence.
ss) Input dependence.
tt) Anti- dependence.
Using suitable variable names in simple statements, we can avoid:
uu) Flow & Output dependence.
vv) Anti & Output dependence.
ww) Flow & Anti dependence.
xx) None of the above.


ANSWERS TO OBJECTIVE QUESTIONS

(b)
(d)
(d)
DEF, USE
(c)
(c)
Output, Anti- dependence.
(b)
Loops
Diophantine
(b)
GCD/Banerjee
(b)
(b)
(c)
(a)
(b)
(b)
(b)


SUBJECTIVE QUESTIONS

1. (A) Define DEF & USE set of statements with examples.
Ans: DEF & USE set of statements are used to identify the type of dependency that exists in a given code of segment.
DEF: It is a set of variables modified by the statement.
USE: It is a set of variables accessed/used by the statement.
Example: let there be a statement, A=5.2
By definition, DEF(A)={A}
& USE (A)={ } (as no variable is used by statement)
let another statement be: A=B+C-2.4
By definition, DEF(A)={A}
& USE(A)={B,C}
DEF & USE are used to formalize the notion of dependence

1. (B) Illustrate with an example: “Dependence is not Transitive”.
Ans: Dependence relation is not transitive. By this we mean, if there are 3 sets of statements S1, S2 & S3, then if S1 & S2 are dependent and S2 & S3 are dependent then it does not imply that S1 & S3 are also dependent.
Let us prove it with an example.
Let S1: A=B+C;
S2: A=C-D;
S3: D=0;
DEF & USE sets of S1, S2 & S3 are:
DEF (S1) = {A} USE (S1) = {B, C}
(1)
DEF (S2) = {A} USE (S2) = {C, D} (2)
DEF (S3) = {D} USE (S3) = { } (3)

Now we know that, Output Dependence arises if:
DEF (S1) intersection DEF (S2)! = { } (A)
From (1) & (2),
DEF (S1) intersection DEF (S2) = {A}
Therefore, Output dependence exists between S1 & S2

Also, Anti- Dependence arises if:
DEF (S2) intersection Use (S1)! = { } (B)
From (2) & (3),
DEF (S3) intersection USE (S2) = {D}
Therefore, Anti-dependence exists between S2 & S3

Now, Flow dependence arises if:
DEF (S1) intersection USE (S2)! = { } (C)
But from (1) & (3)
None of the conditions ((A), (B), (C)) holds true
Therefore, there is no dependence between S1 & S3
Hence dependence is not transitive.

2. (A) what are the various sources of Dependence? Explain with examples.
Ans: Dependency among program segments arises primarily from three sources:
CONTROL DEPENDENCE: It is imposed by the language constructs such as if-then, case etc. even if the segments corresponding to different execution branches are independent, there is no use of executing them in parallel because result of only one of those segments needs to be visible based on the condition being tested.
RESOURCE DEPENDENCE: It arises from the need to share resources among instructions. E.g. if 2 instructions require the use of a floating point processor and only one such floating point unit is available in CPU, then these 2 instructions can not be executed in parallel.
DATA DEPENDENCE: It is the most important source of dependency. It arises when 2 segments of code accesses or updates the common piece of data. E.g. consider 2 statements:
A=A+1;
B=A+1;
Let initial value be A=0, B=0
Result of sequential execution will be A=1, B=2
Result of parallel execution would depend on the order in which
statements would be executed & therefore, will be different every time. This is because statement 2 is referring to a variable being used by statement 1.

2. (B) explain different types of dependencies with examples. Which one
of these is unavoidable?
Ans: To explain the different types of dependencies, let us consider a pair of Statements S1 & S2. There is a dependence across S1 & S2 if there is some
common element in the DEF & USE sets of these statements.
The 4 types of dependencies are:

TRUE/FLOW DEPENDENCE: it arises when
DEF (S1) intersection USE (S2)! = { }
· It is the most common & most difficult to avoid.
· It arises because a value computed by S1 is used in S2 for some processing.
· When a program is solved in a sequence of steps then intermediate or partial results are computed for further use.
Example: Let S1: A=B+C
S2: D=2*A
DEF (S1) = {A}
USE (S2) = {A}
According to definition,
DEF (S1) intersection USE (S2) = {A}
Therefore, Flow dependence arises in these statements.

ANTI-DEPENDENCE: It arises when
DEF (S2) intersection USE (S1)! = { }
· It is opposite of flow dependence.
· It arises when we reuse variable names.
· A variable whose value is used in S1 is redefined in S2.
· It is to be ensured that the old value of variable is used in S1.
· If we execute S1 & S2 in parallel, it might be possible that S2 gets executed first, which results in a new value being used in S1.
Example: Let S1: A=B+C; B is used in S1 & is redefined in S2
S2: B=0;
USE (S1) = {B, C}
DEF (S2) = {B}
And DEF (S2) intersection USE (S1) = {B}
Therefore, Anti-dependence arises.

OUTPUT DEPENDENCE: It arises when
DEF (S1) intersection DEF (S2)! = { }
It arises because of 2 reasons:
· Reuse of variable names for convenience.
· Incremental computation of a variable.
Example: Let S1: A=B+C;
S2: A=A-D;
DEF (S1) = {A}
DEF (S2) = {A}
And DEF (S1) intersection DEF (S2) = {A}
Therefore, Output dependence arises.

INPUT DEPENDENCE: It arises when
USE (S1) intersection USE (S2)! = { }
· There is no threat to parallelism as a commonly accessed or used variable is present.
· Since accessing a value by a process does not change its value, therefore, any number of processes accessing the value simultaneously is acceptable.
Example: Let S1: A=B+C; No harm in executing S1 & S2 in parallel
S2: D=B+5;
USE (S1) = {B, C}
USE (S2) = {B}
And USE (S1) intersection USE (S2) = {B}
Among all 4 types of dependencies, FLOW Dependence is real & is unavoidable because it is inherent in the style of computation. It is bound to occur even irrespective of the programming paradigm being used.


Can different iterations of a loop be done in parallel? Explain with an example.
Ans: “Can different iterations of a loop be done in parallel” is same as saying, “Can Processor A work on a statement 1&2 for i=1 while Processor B works on the same set of statements for i=2.”
There is every possibility that second iteration ( i=2 ) may get completed before first ( i=1 ). Will this create any difficulty in executing these iterations in parallel?
Let us analyze this situation by using DEF & USE sets and looking at their intersections.
Let us consider an example:
Do I
A [I] = A [I-1] +1
This loop can be unfolded & written as:
A [1] = A [0] +1
A [2] = A [1] +1
A [3] = A [2] +1 & so on…
Let us consider two separate iterations with I = i & I= j
Assume i
Loop corresponding to these iterations would be:
A [i] = A [i-1] + 1
A [j] = A [j-1] + 1
If there is no dependency between these 2 statements, then these iterations are independent & can be executed in parallel.
To check the dependency, let us compute DEF & USE sets
DEF i : A [i] USE i : A [i-1]
DEF j : A [j] USE j : A [j-1]
These sets contain subscripts & not variables.

There is a Flow dependence in loop if DEF I & USE j can have a common element. i.e. when i=j-1
Equation i=j-1 has infinite solutions.
Hence dependency arises & loop iterations can not be parallelized as it is.
Determining dependency in this manner is a difficult task as all equations need not be trivial.


Define Diophantine equations. Give a method of solving Diophantine equations with example.
Ans: Diophantine equations are those which require an integer solution.
· There is no direct mathematical solution strategy for solving such equations.
· Different techniques have to be tried depending on the type of the equation.
· 2 popular tests to check dependencies are GCD and Banerjee test.
· If test results indicate there is no solution to the equation then there is no dependency.

Solving Diophantine equations:
General form of an equation is:
E AiXi = C Xi—integers
Only if GCD ( A1,A2,…,An) divides C , then equation has a solution in the integer domain.
If this above condition is true & loop constraints are satisfied by the solution, then there is dependence.

Diophantine equations for 2-variables
General form of equation is
Ax + By = C (1)
Let g = GCD (A, B)
If g divides C, then we can write g as:
g = Au + Bv
Solutions of (1) are given by:
Xt = uC/g + Bt/g , Yt = vC/g –At/g (I)

Example:
Let S1: A [2i-1] = …
S2: … = A [4i-7]
There will be Flow dependence between Xth & Yth iteration if L.H.S of S1 & R.H.S of S2 refer to same array element
i.e. 2x-1 = 4y-7
4y-2x = 6



Comparing it with Ax + By = C, we get
A=4, B=-2, C=6
g = GCD (4, 2) = 2
Since g divides C (2 divides 6)
Therefore equation has a solution.
Writing g = Au + Bv
i.e. 2=4*-1 + (-2)*-3
u=-1, v=-3 (1 set of values, other solutions are also possible)
using (I)
solution is:
Xt = -3-t
Yt = -9-2t
The constraint equation is 4y-2x = 6
Multiple solutions of x & y satisfy the solution.
x = 17, y = 10----referring to array element A [33]
x = 19, y = 11----referring to array element A [37]