Question Answer

Bernstein’s Conditions for Parallelism

For two tasks (or statements) S1 and S2 to execute in parallel, their data sets must not conflict. Let I1, O1 be the input and output sets of S1, and I2, O2 be the input and output sets of S2. Bernstein’s conditions require all three of the following to be true:

• No flow dependence (S2 must not read what S1 writes): O1 ∩ I2 = ∅
• No anti-dependence (S2 must not overwrite what S1 will read): O2 ∩ I1 = ∅
• No output dependence (they must not write the same data): O1 ∩ O2 = ∅

Given S1: (I1, O1) and S2: (I2, O2)
Parallel execution is safe if:
1) O1 ∩ I2 = ∅
2) O2 ∩ I1 = ∅
3) O1 ∩ O2 = ∅

If all three conditions hold, S1 and S2 are data-independent and can run in parallel.