ASSIGNMENT DATA DEPENDENCY ANALYSIS

Subjective Questions

Q1. Explain data dependency analysis and its primary sources.
Ans. Some programs code segments cannot be run in parallel due to dependency where the results of execution of some part of the code affects the execution of some other part. For example, the average of a set of numbers is required for the computation of the standard deviation of the set. Data dependency analysis deals with the study of the nature of such dependencies.
Automatic detection of parallism in the existence code requires the need for compilers that can identify what can be done in parallel and what cannot be. This is not an easy task. There are a numbers of factors affecting this task, including the choice of language used.
Some are hard dependencies which cannot be circumvented at all. For example, if a routine outputs the contents of an array in order, it has to be executed sequentially. Without destroying the order, it is difficult to envisage a parallelization. In some other cases, the code may appear to require a sequential order, but suitable remodeling can convert the code to run in parallel. In the best case, find the code segments that are independent and hence can be directly scheduled for running in parallel.

Primary sources of dependencies:
Dependency among program segments arises from primarily three sources:
Control dependence.
Resource dependence.
Data dependence.
Control dependence:
This is imposed by the language construct like if then, case, etc. though the code segment corresponding to different branches are independent, there is no use of executing them I parallel because only one of the results should be visible , which depends on the conditions being tested.
Resource Dependence:
The need to share resources among instructions causes resource dependency. 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.


Q2. Explain various types of dependencies.
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 and USE are used to formalized the notion of dependence.

Types of dependence:

1. 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.
2. 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:
a. Reuse of variable names for convenience.
b. 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)! = { }
c. There is no threat to parallelism as a commonly accessed or used variable is present.
d. 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.


Q3.a How can we avoid various types of dependencies?
Ans. Flow dependence is real and it is unavoidable.

Avoiding Output dependence:
It can be avoided by suitable use of variable names. Consider the following statements, these have output dependence.
A= B+C;
A= C-D;
The dependence can be avoided by rewriting the statements
A1= B+C;
A= C-D;
Change all occurrences of A from the statement to the second statement to A1.
The expression can be combined as
A= B+C-D.

Avoiding Anti-Dependence:
It can also be avoided by suitable use of variable names. The following segment
A= B+C
B= 0
Has anti-dependence.
It can be avoided by rewriting
A= B+C
B1 =0
All occurrences of B below these statements must be changed to B1. However, such simple transformation is not always possible as in for loop statement.

Q3b. Explain “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.

Fill in the blanks/ multiple choice questions with answers

1. Dependence arise from the need to share resources among instructions is
.
2. Primary sources of dependency are

3. set is a set of variables modified by the statement.

4 set of a statement is the set of variables accessed by the statement.
True dependence also known as .
Identify the type of dependence
S1: A= B+C;
S2: D= 2*A;
a) Anti-dependence b) Flow/ true dependence
c) Output dependence d) Input dependence
Anti- dependence arises when which of the following set of intersection is non-empty
a) DEF(S1) and USE(S2) b) DEF(S2) and USE(S1)
b) DEF(S1) and DEF(S2) d) USE(S1) and USE(S2)
Anti - dependence is the opposite of
a) Input dependence b) Flow/ true dependence
c) Output dependence d) none of these
9. Which of the following is the most common type of dependence and most difficult
to avoid?
a) Anti-dependence b) Flow/ true dependence
c) Output dependence d) Input dependence
10. dependence is real and unavoidable.
11. How can we avoid this dependence?
A= B+C
A= C-D and also identify the type of dependence also.


Answers
1. Resource dependence
2. Control, data and resource
3. DEF
4. USE
5. Flow dependence
6. b)
7. b)
8. b)
9. b)
10. Flow dependence
11. Output dependence and can be avoided by rewriting as
A1= B+C A= C-D
Or
A= B+C-D

Content Credit : RUPINDER KAHLON