Editing Parallel computing (section)

===Dependencies===
Understanding [[data dependency|data dependencies]] is fundamental in implementing [[parallel algorithm]]s. No program can run more quickly than the longest chain of dependent calculations (known as the [[Critical path method|critical path]]), since calculations that depend upon prior calculations in the chain must be executed in order. However, most algorithms do not consist of just a long chain of dependent calculations; there are usually opportunities to execute independent calculations in parallel.

Let ''P''<sub>''i''</sub> and ''P''<sub>''j''</sub> be two program segments. Bernstein's conditions<ref>{{cite journal|last=Bernstein|first=Arthur J.|title=Analysis of Programs for Parallel Processing|journal=IEEE Transactions on Electronic Computers|date=1 October 1966|volume=EC-15|issue=5|pages=757–763|doi=10.1109/PGEC.1966.264565}}</ref> describe when the two are independent and can be executed in parallel. For ''P''<sub>''i''</sub>, let ''I''<sub>''i''</sub> be all of the input variables and ''O''<sub>''i''</sub> the output variables, and likewise for ''P''<sub>''j''</sub>. ''P''<sub>''i''</sub> and ''P''<sub>''j''</sub> are independent if they satisfy
: <math>I_j \cap O_i = \varnothing,</math>
: <math>I_i \cap O_j = \varnothing,</math>
: <math>O_i \cap O_j = \varnothing.</math>

Violation of the first condition introduces a flow dependency, corresponding to the first segment producing a result used by the second segment. The second condition represents an anti-dependency, when the second segment produces a variable needed by the first segment. The third and final condition represents an output dependency: when two segments write to the same location, the result comes from the logically last executed segment.<ref>{{cite book|last=Roosta|first=Seyed H.|title=Parallel processing and parallel algorithms : theory and computation|year=2000|publisher=Springer|location=New York, NY [u.a.]|isbn=978-0-387-98716-3|page=114}}</ref>

Consider the following functions, which demonstrate several kinds of dependencies:

 1: function Dep(a, b)
 2: c := a * b
 3: d := 3 * c
 4: end function

In this example, instruction 3 cannot be executed before (or even in parallel with) instruction 2, because instruction 3 uses a result from instruction 2. It violates condition 1, and thus introduces a flow dependency.

 1: function NoDep(a, b)
 2: c := a * b
 3: d := 3 * b
 4: e := a + b
 5: end function

In this example, there are no dependencies between the instructions, so they can all be run in parallel.

Bernstein's conditions do not allow memory to be shared between different processes. For that, some means of enforcing an ordering between accesses is necessary, such as [[Semaphore (programming)|semaphores]], [[Barrier (computer science)|barriers]] or some other [[Synchronization (computer science)|synchronization method]].