How does DOACROSS differ from DOALL?

DOALL assumes iterations can execute independently; DOACROSS preserves dependencies while overlapping eligible work.

Does it always improve performance?

No. Limited independent work and synchronization overhead may prevent a useful speedup.

Can incorrect dependency declarations change results?

Yes. Missing dependencies can allow reads or writes in an invalid order, while incorrect waits can prevent progress.

AI Glossary / Data science and analytics / Advanced

DOACROSS parallelism

Definition

DOACROSS parallelism executes work from different loop iterations concurrently while preserving required dependencies between those iterations. It is useful when a loop contains some work that can overlap but cannot be treated as fully independent. Synchronization ensures that an iteration consumes a required result only after the producing iteration has made it available. The attainable speed depends on the dependency structure and the cost of coordination.

What it means

A loop repeats a computation for different indices. In a fully independent loop, iterations can often run in almost any order. A loop-carried dependency means one iteration needs information produced by another. That does not necessarily force every operation in every iteration to run sequentially. DOACROSS techniques expose the independent portions while respecting the ordering of dependent portions. The term describes a parallelism pattern; particular programming systems provide their own ways to express it.

How it works

The programmer or compiler identifies which iteration produces each required value and where another iteration needs it. Work that does not depend on that value may proceed concurrently. At a dependency boundary, the consumer waits until the producer has completed the necessary operation and signaled availability. OpenMP documentation describes doacross loop nests and source/sink synchronization for cross-iteration dependencies. Correctness requires accurate dependence information, suitable memory synchronization, and valid handling of boundaries. Incorrect waits can cause deadlock, and missing waits can cause data races or wrong results.

Three practical examples

Numerical computation: a grid update can proceed along wavefronts when each cell requires selected neighboring results.
Data-processing loop: independent per-record preparation overlaps while an ordered recurrence combines the prepared values.
Simulation kernel: iterations perform independent calculations before a dependency-constrained state update, provided the algorithm's exact dependencies are preserved.

Think of it this way

Think of several people preparing ingredients in parallel while one ordered assembly step requires the previous stage's result. Preparation can overlap even though the final sequence cannot be arbitrarily rearranged. The analogy captures partial concurrency. Software dependencies can be more complex than a single assembly line, and coordination itself consumes resources and must be correct.

Worked example

Suppose four iterations each have an independent preparation step taking 8 time units and a dependent update taking 2 units. Each update needs the result of the previous update, but every preparation can begin immediately and uses only its own input. Sequential execution takes 4 times (8 + 2) = 40 units.
In an idealized schedule with four workers, all preparation steps run from time 0 to time 8. The updates then run in order from 8 to 10, 10 to 12, 12 to 14, and 14 to 16. Total time is 16 units, giving an ideal speedup of 40/16 = 2.5. This assumes no synchronization cost, no resource contention, and exactly the stated dependencies. If each preparation also needed the previous update, that overlap would disappear. The example shows why the dependency graph, not merely the number of processor cores, determines the available parallelism.

Illustrative case study

In a fictional engineering application, a developer tries to speed up a simulation by marking a loop as parallel. Results vary between runs because neighboring iterations read values before the required updates finish. The team maps the dependencies, compares with the sequential reference, and redesigns the schedule to allow only valid overlap. It tests small cases with known outputs before measuring runtime on representative workloads. If synchronization costs exceed the benefit, the team keeps the simpler implementation or changes the algorithm. This is an illustrative development process, not a benchmark claim.

Common misconceptions and mistakes

DOACROSS does not mean that dependent computations can ignore ordering. A lock around the entire loop body may restore correctness while eliminating most useful concurrency. More threads can increase overhead without shortening the critical dependency chain. A loop that appears independent may still share hidden state, library resources, or output buffers. Conversely, an algorithm may admit a different formulation with more parallelism, but that requires separate reasoning. The generic technique should also be distinguished from historical compiler directives carrying a similar name.

Business use

For businesses running scientific, engineering, or data-processing workloads, the value is potentially lower execution time for suitable kernels. Establish the required result semantics before optimizing. Measure end-to-end performance, including synchronization, data movement, and memory bandwidth. Validate behavior across boundary cases and representative input sizes. OpenMP syntax and compiler support vary by version, so implementation should follow the actual supported specification. A conceptual glossary example cannot replace performance measurements or a correctness review of production code.

Check your understanding

In the worked example, what happens if each preparation step needs the preceding update?

Answer: The assumed simultaneous preparation is no longer valid. The schedule must respect that additional dependency, potentially restoring the sequential chain and removing the predicted speedup.

Related terms

Synchronization
Critical path
Loop-carried dependency
data race
wavefront parallelism
DOALL
OpenMP
task dependency
speedup

Learn next

Draw a dependency graph for a small loop before writing parallel code. Separate operations that can overlap from those on the critical path. Then study synchronization and memory visibility in the chosen programming system, followed by profiling and validation against a trusted sequential result.

Sources

OpenMP, loop terminology: https://www.openmp.org/spec-html/5.0/openmpsu3.html . OpenMP, ordered construct: https://www.openmp.org/spec-html/5.0/openmpsu97.html . Intel, ordered and doacross directive documentation: https://www.intel.com/content/www/us/en/docs/fortran-compiler/developer-guide-reference/2025-1/ordered.html . Primary specification and compiler documentation excerpts were consulted. Versioned sources support concepts, not a claim about every current compiler. Timing examples are idealized and original; editorial review remains pending.

Previous: DMAIC Next: Document-at-a-time