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 R_I which consists of memory locations read by statement of instruction I₁.

ii) The Write set or output set W_I which consists of memory locations written into by instruction I₁.

The sets W_I and R_I are not disjoint as the similar locations are used for reading and writing by S_I.

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

1)  Locations in R₁ from which S₁ reads and locations W₂ on which S₂ writes should be mutually exclusive. Which means S₁ doesn't read from any memory location on which S₂ writes. It can be indicated as

  R1 ∩ W2= ?

2)  In the same way, locations in R₂ from that S₂ reads and the locations W₁ on that S₁ writes should be mutually exclusive. Which means S₂ doesn't read from any memory location onto that S₁ writes. It can be designated as: 

R2 ∩ W1= ?

3)  The memory locations W₁ and W_2, on that S₁ and S₂ write must not be read by S₁ and S₂. Which means R₁ and R₂ must be independent of W₁ and W₂.  It can be indicated as:

W1 ∩ W2= ?

To demonstrate the operation of Bernstein's conditions, think about subsequent instructions of sequential program:

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

I₂: y = (b + c) * d

I₃: z = x² + (a * e)

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

R₁ = {a, b}        W₁ = {x}

R₂ = {b, c, d}    W₂ = {y}

R₃ = {x, a, e}    W₃ = {z}

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

            R₁ ∩ W₂ = ?

            R₂ ∩ W₁ = ?

            W₁ ∩ W₂ = ?

Which means I₁ and I₂ are independent of each other.

Similarly for I₁ || I₃,

R₁ ∩ W₃= ?

R₃ ∩ W₁ ≠ ?

W₁ ∩ W₃= ?

Therefore I₁ and I₃ aren't independent of each other.

For I₂ || I₃,

R₂ ∩ W₃= ?

            R₃ ∩ W₂= ?

W₃ ∩ W₂= ?

Therefore, I₂ and I₃ are independent of one another. So I₁ and I₂, I₂ and I₃ are parallelizable however I₁ and I₃ are not.