Want to join our mediation workshop that helps you to study better?

The Eduladder is a community of students, teachers, and programmers just interested to make you pass any exams. So we help you to solve your academic and programming questions fast.
In eduladder you can Ask,Answer,Listen,Earn and Download Questions and Question papers.
Watch related videos of your favorite subject.
Connect with students from different parts of the world.
Apply or Post Jobs, Courses ,Internships and Volunteering opportunity. For FREE
See Our team
Wondering how we keep quality?
Got unsolved questions? Ask Questions

Software-Engineering-10IS51-unit-3-->View question


Asked On2017-05-14 21:45:11 by:pallaviaithaln

Taged users:


Likes:
Be first to like this question

Dislikes:
Be first to dislike this question
Talk about this  Like  Dislike
View all qusetions
Answers

A data dependency in computer science is a situation in which a program statement (instruction) refers to the data of a preceding statement. In compiler theory, the technique used to discover data dependencies among statements (or instructions) is called dependence analysis.

Flow dependency

A Flow dependency, also known as a data dependency or true dependency or read-after-write (RAW), occurs when an instruction depends on the result of a previous instruction:

1. A = 3
2. B = A
3. C = B

Instruction 3 is truly dependent on instruction 2, as the final value of C depends on the instruction updating B. Instruction 2 is truly dependent on instruction 1, as the final value of B depends on the instruction updating A. Since instruction 3 is truly dependent upon instruction 2 and instruction 2 is truly dependent on instruction 1, instruction 3 is also truly dependent on instruction 1. Instruction level parallelism is therefore not an option in this example. [1]

Anti-dependency

An anti-dependency, also known as write-after-read (WAR), occurs when an instruction requires a value that is later updated. In the following example, instruction 2 anti-depends on instruction 3 the ordering of these instructions cannot be changed, nor can they be executed in parallel (possibly changing the instruction ordering), as this would affect the final value of A.

1. B = 3
2. A = B + 1
3. B = 7

An anti-dependency is an example of a name dependency. That is, renaming of variables could remove the dependency, as in the next example:

1. B = 3
N. B2 = B
2. A = B2 + 1
3. B = 7

A new variable, B2, has been declared as a copy of B in a new instruction, instruction N. The anti-dependency between 2 and 3 has been removed, meaning that these instructions may now be executed in parallel. However, the modification has introduced a new dependency: instruction 2 is now truly dependent on instruction N, which is truly dependent upon instruction 1. As flow dependencies, these new dependencies are impossible to safely remove. [1]

Output dependency

An output dependency, also known as write-after-write (WAW), occurs when the ordering of instructions will affect the final output value of a variable. In the example below, there is an output dependency between instructions 3 and 1 changing the ordering of instructions in this example will change the final value of B, thus these instructions cannot be executed in parallel.

1. B = 3
2. A = B + 1
3. B = 7

As with anti-dependencies, output dependencies are name dependencies. That is, they may be removed through renaming of variables, as in the below modification of the above example:

1. B2 = 3
2. A = B2 + 1
3. B = 7

A commonly used naming convention for data dependencies is the following: Read-after-Write or RAW (flow dependency), Write-after-Write or WAW (output dependency), and Write-After-Read or WAR (anti-dependency). [1]

Control Dependency

An instruction is control dependent on a preceding instruction if the outcome of latter determines whether former should be executed or not. In the following example, instruction S2 is control dependent on instruction S1. However, S3 is not control dependent upon S1 because S3 is always executed irrespective of outcome of S1.

S1.         if (a == b)
S2.             a = a + b
S3.         b = a + b

Intuitively, there is control dependence between two statements S1 and S2 if

  • S1 could be possibly executed before S2
  • The outcome of S1 execution will determine whether S2 will be executed.

A typical example is that there is control dependence between if statement's condition part and the statements in the corresponding true/false bodies.

A formal definition of control dependence can be presented as follows:

A statement S2 is said to be control dependent on another statement S1 iff

  • there exists a path P from S1 to S2 such that every statement Si ≠ S1 within P will be followed by S2 in each possible path to the end of the program and
  • S1 will not necessarily be followed by S2, i.e. there is an execution path from S1 to the end of the program that does not go through S2.

Expressed with the help of (post-)dominance the two conditions are equivalent to

  • S2 post-dominates all Si
  • S2 does not post-dominate S1

Example 2: control independent:

for (i=0;i<n;i++)
{
a[i] = c[i];
if (a[i] < 0) a[i] = 1;
}

control dependent:

for (i=1;i<n;i++) 
{               
if (a[i-1] < 0) a[i] = 1;                                
}




There are three types of dependencies: data, name, and control.


Answerd on:2015-01-18 Answerd By:Anagha

Likes:
|scribed

Dislikes:
Be first to dislike this answer
Talk about this  Like  Dislike

You might like this video:Watch more here

Watch more videos from this user Here

Learn how to upload a video over here



Lets together make the web is a better place

We made eduladder by keeping the ideology of building a supermarket of all the educational material available under one roof. We are doing it with the help of individual contributors like you, interns and employees. So the resources you are looking for can be easily available and accessible also with the freedom of remix reuse and reshare our content under the terms of creative commons license with attribution required close.

You can also contribute to our vision of "Helping student to pass any exams" with these.
Answer a question: You can answer the questions not yet answered in eduladder.How to answer a question
Career: Work or do your internship with us.Work with us
Create a video: You can teach anything and everything each video should be less than five minutes should cover the idea less than five min.How to upload a video on eduladder