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 I_{1}.
ii) The output set or Write set WI that consists of memory locations printed into by instruction I_{1}.
The sets W_{I }and R_{I }are not disjoint as the similar locations are used for writing and reading by S_{I}.
The following are Bernstein Parallelism conditions which are determine to conclude whether the statements are parallel or not:
1) Position in R_{1 }from which S_{1 }reads and the Position W_{2} onto which S_{2 }writes must be commonly exclusive. It means S_{1}does'nt read from any memory location onto which S_{2} writes. It can be indicated as:
2) Likewise, locations in R_{2} from which S_{1} writes and the locations W_{1} onto which S_{2} reads must be commonly exclusive.It means S_{2} does not read from some memory location onto which S_{1} writes. It can be indicate as:
3) The memory locations W_{1} and W_{2} onto which S_{1} and S_{2} write, should not be examine by S_{1} and S_{2}. It means R_{1} and R_{2} should be free of W_{1} and W_{2}. It can be indicated as :
To demonstrate the operation of Bernstein's conditions, let consider the following instructions of sequential program:
I_{1 }: x = (a + b) / (a * b)
I_{2} : y = (b + c) * d
I_{3} : z = x2 + (a * e)
Now, the read set and write set of I1, I2 and I3 are as given:
R_{1} = {a,b} W1 = {x}
R_{2} = {b,c,d} W2 = {y}
R_{3} = {x,a,e} W3 = {z}
Now let us search out whether I_{1 }and I_{2 }are parallel or not