Bernstein Conditions

by Evan Conrad, February 27, 2018

Bernstein conditions are a set of formal rules that will let you determine if two pieces of code can be run in parallel.

These rules are as follows:

  • The inputs into the first piece of code cannot be the same memory as the outputs of the second piece of code.
  • The inputs into the second piece of code cannot be the same memory as the outputs of the first piece.
  • The outputs of both programs cannot be the same memory.

In other words, the pieces of code cannot share a data dependency. If they did, then you would have to run one program before the other!

Expressed mathematically, we can view it as:

condition_1 = union(inputMemory_2, outputMemory_1) == null
condition_2 = union(inputMemory_1, outputMemory_2) == null
condition_3 = union(outputMemory_1, outputMemory_2) == null

Something wrong with this post? Edit it here.

Didn't understand something? Have a question? Ask it here.