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.