In this section, we'll spend some time discussing a major factor relevant to successful code parallelization: dependency.
Definition: A DEPENDENCE exists between statements when the order of the statements' execution affects the results of the program. A DATA DEPENDENCE results from multiple use of the same location(s) in storage.
For example, if a group of parallel tasks post sends to one another before executing blocking receives, they all will likely (assuming no other problems in the code) obtain their expected data; if however, they all do blocking receives before their sends, then none of them will receive their data, as none of them will be able to get past the receive in order to send ... this demonstrates a dependence between the sends and receives.
The concepts of dependence in parallel processing are the same as those in vector processing; the consequences of certain dependencies, however, are different.
This has to do with how the two different forms of concurrency, parallelism and vectorization, view dependencies in multiple-loop situations, i.e., when you have one loop within another. Without going into a great deal of detail, let's leave it with the following:
- parallel concurrency prefers to have any loop-carried dependencies (see below) at the inner-most loop, because that means that the outer-most one can be used for parallelization, while...
- vectorized concurrency prefers just the opposite, so that there are no inconsistencies within each long string of vectors being operated on simultaneously.
Dependencies are acceptable within parallel tasks but not between parallel tasks. Unavoidable dependencies between tasks require synchronization.
Within a parallel task, things are being executed serially, and the rules concerning dependencies are well-understood; dependencies between parallel tasks are major sources of erroneous execution, due to the inability to guarantee a particular time sequence of execution. Therefore, whenever a dependency is discovered between parallel tasks, the safest way to handle it is to force a synchronization between the involved tasks so that you know exactly where each one is in its execution stream, and then allow them to go on into the dependent code.
