Explain bernstein conditions for detection of parallelism, Computer Engineering

Assignment Help:

Bernstein Conditions for Detection of Parallelism

For execution of a number of instructions or a block of instructions in parallel, it must be made certain that instructions are independent of one another. These instructions may be control dependent / resource dependent / data dependent on one another. Here we think about just data dependency among the statements for taking decisions of parallel execution. A.J. Bernstein has elucidated the work of data dependency and derived a number of conditions based on that we can decide the parallelism of processes or instructions.

Bernstein conditions are derived from the subsequent two sets of variables:

i)  The Read set or we can say input set RI which consists of memory locations read by statement of instruction I1.

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

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

The following are 'Bernstein Parallelism conditions' that are used to conclude whether statements are parallel or not:

1)  Locations in R1 from which S1 reads and locations W2 on which S2 writes should be mutually exclusive. Which means S1 doesn't read from any memory location on which S2 writes. It can be indicated as

  R1 ∩ W2= ?

2)  In the same way, locations in R2 from that S2 reads and the locations W1 on that S1 writes should be mutually exclusive. Which means S2 doesn't read from any memory location onto that S1 writes. It can be designated as: 

R2 ∩ W1= ?

3)  The memory locations W1 and W2, on that S1 and S2 write must not be read by S1 and S2. Which means R1 and R2 must be independent of W1 and W2.  It can be indicated as:

W1 ∩ W2= ?

To demonstrate the operation of Bernstein's conditions, think about subsequent 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 follows:

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

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

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

Now let's find out whether I1 and I2 are parallel or not

            R1 ∩ W2 = ?

            R2 ∩ W1 = ?

            W1 ∩ W2 = ?

Which means I1 and I2 are independent of each other.

Similarly for I1 || I3,

R1 ∩ W3= ?

R3 ∩ W1 ≠ ?

W1 ∩ W3= ?

Therefore I1 and I3 aren't independent of each other.

For I2 || I3,


R2 ∩ W3= ?

            R3 ∩ W2= ?

W3 ∩ W2= ?

Therefore, I2 and I3 are independent of one another. So I1 and I2, I2 and I3 are parallelizable however I1 and I3 are not.


Related Discussions:- Explain bernstein conditions for detection of parallelism

Object orientation and uml, In this task you are supposed to create three U...

In this task you are supposed to create three UML diagrams. The conditions are given by the scenario in the document Theatre Case (on Blackboard). A theatre manager has ordered a s

Set up this problem as an lp problem, The Laser Computer Printer Company de...

The Laser Computer Printer Company decides monthly what to produce during the subsequent month. They produce three types of printers, the Laser Rocket, the Alpha Laser, and the La

C programming, #write a program to find the area under the curve y=f(x) bet...

#write a program to find the area under the curve y=f(x) between x =a and x=b integrate the area between a and b by c programming

Avoiding local minima, Avoiding Local Minima: However the error rate o...

Avoiding Local Minima: However the error rate of multi-layered networks over a training set could be calculated as the number of mis-classified examples. So always keep in rem

Difference between perl and mod_perl, Perl is a language and MOD_PERL is a ...

Perl is a language and MOD_PERL is a module of Apache used to increase the performance of the application.

How branching takes place in instruction pipeline, How branching takes plac...

How branching takes place in Instruction pipeline. Explain with suitable examples

Calculate period of congestion in a particular exchange, In a particular ex...

In a particular exchange during busy hour 1200 calls were offered to a group of trunks, during this time 6 calls were lost. The average call duration being 3 minutes Calculate

Decimal equivalent of hex number 1A53, What is the decimal equivalent of he...

What is the decimal equivalent of hex number 1A53 ? Ans. 6739 is the decimal equivalent of Hex Number 1A53. From Hex Number to Decimal Number conversion is shown below: 1

A digital signature, A digital signature is   encrypting information

A digital signature is   encrypting information

3 sets of input data, Prepare at least 3 sets of input data (Test data) alo...

Prepare at least 3 sets of input data (Test data) along with expected output for testing your program.

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd