A parallel computation can be represented as a dependency graph whose nodes are pieces of work and whose directed edges state which results must exist before other work can begin.

Because a valid precedence relation cannot require an action to precede itself, the dependency graph is a directed acyclic graph (DAG).

Consider

$$a=(b+c)(d+e).$$

Let task $T_1$ compute $b+c$, task $T_2$ compute $d+e$, and task $T_3$ multiply the two results. The graph has edges

$$T_1\to T_3,\qquad T_2\to T_3.$$

There is no edge between $T_1$ and $T_2$, so either may run first or they may run simultaneously. $T_3$ cannot begin until both are complete.

This separates semantic dependencies from an arbitrary sequential implementation. A sequential program might execute $T_1$ and then $T_2$, but that order is not required by the computation.

Parallelization begins by identifying which ordering constraints are genuine. Removing a required dependency causes incorrect results; adding unnecessary dependencies serializes work that could have overlapped.