Bernstein conditions for detection of parallelism, Computer Engineering

Bernstein Conditions for Detection of Parallelism

For implementation of instructions or block of instructions in parallel, it should be guaranteed that the instructions are independent of each other. These instructions can be / control dependent / data dependent resource dependent on each other.  We are considering only data dependency between the statements for taking decisions of parallel implementation. A.J. Bernstein has implicated the work of data dependency and resultant some conditions based on which we can settle on the parallelism of processes or instructions.

Bernstein conditions are rely on the subsequent two sets of variables:

i)  The input set or Read set RI that consists of memory locations examine by the statement of instruction I1.

ii)  The output set or Write set WI  that consists of memory locations printed into by instruction I1.

The sets WI and RI are not disjoint as the similar locations are used for writing and reading by SI.

The following are Bernstein Parallelism conditions which are determine to conclude whether the statements are parallel or not:

1) Position in R1 from which S1 reads and the Position W2  onto which S2 writes must be commonly exclusive. It  means S1does'nt read from any memory location onto which S2 writes. It can be indicated as:

                                                                     1510_Bernstein Conditions for Detection of Parallelism.png

 

2) Likewise, locations in R2 from which S1 writes and the locations W1 onto which S2 reads must be commonly exclusive.It means S2  does not read from some memory location onto which S1 writes. It can be indicate as:

                                                                       138_Bernstein Conditions for Detection of Parallelism 1.png

3) The memory locations W1 and W2 onto which S1 and S2 write, should not be examine by S1 and S2. It means R1 and R2 should be free of W1 and W2.  It can be indicated as :

                                                                      661_Bernstein Conditions for Detection of Parallelism 2.png

To demonstrate the operation of Bernstein's conditions, let consider the following instructions of sequential program:

I1 : x = (a + b) / (a * b)

I2 : y = (b + c) * d

I3 : z = x2 + (a * e)

Now, the read set and write set of I1, I2 and I3 are as given:

R1 = {a,b}                W1 = {x}

R2 = {b,c,d}             W2 = {y}

R3 = {x,a,e}             W3 = {z}

 

Now let us search out whether I1 and I2 are parallel or not

 

 

314_Bernstein Conditions for Detection of Parallelism 3.png

                                                        418_Bernstein Conditions for Detection of Parallelism 4.png

Posted Date: 3/1/2013 7:31:45 AM | Location : United States







Related Discussions:- Bernstein conditions for detection of parallelism, Assignment Help, Ask Question on Bernstein conditions for detection of parallelism, Get Answer, Expert's Help, Bernstein conditions for detection of parallelism Discussions

Write discussion on Bernstein conditions for detection of parallelism
Your posts are moderated
Related Questions
These days, they're pretty much obsolete; they're definitely system-particular. They had to do with 16-bit programming under MS-DOS and perhaps some early on versions of Windows. I

I got a graduate level database assignment which is due at Dec 8, 11:59p.m. Can you finish it on time in high quality?

What do you mean by e-brokerage? E-brokerage is an investment house which permits you to buy and sell stocks and acquire investment information through its Web site. E-comme

Prove the following Boolean identities using the laws of Boolean algebra: ABC + AB ‾C + ABC ‾ = A(B + C) Ans. ABC+AB'C+ABC'=A(B + C) LHS AC(B+B')+AB(C+C') OR  AC+AB OR  A(B

Q. Number used as operand data type? Numbers: All machine languages comprise numeric data types. Numeric data generally use one of the three representations: o Floating po

A circuit can be designed to perform manydifferent functions e.g.a circuit has 3 inputs A, B and C and 3 outputs:Output X is logic level 1 (or 'high') if one or moreinputs are at l

Q. Write a program to implement NOR, NAND, XOR and XNOR gates using and without using bit wise operator. Also perform necessary checking. The user has option to give n numbe

Define variants of Turing Machine?  Variants are  Non deterministic turing machine.  Mutlitape turing  machine.  Enumerators

Analysis describes about the logical and statistical analysis needed for an efficient output. This involves writing of code and performing calculations, but most part of these lang

What is CMP instruction Comparison instruction (CMP) is a subtraction that changes only the flag bits; destination operand never changes. A comparison is useful for checking th