Odd-Even Communication

Problem

Operations on data cannot be done entirely independently, but data can be partitioned into two subsets such that all operations on a subset can run in parallel.

Context

Solvers for partial differential equations can often be modified to follow this pattern. For example, for a 2D grid with only nearest-neighbor communication, it may be possible to treat the grid as a checkerboard, and alternate between updating red squares and black squares.

Another context is staggered grid ("leap frog") Finite Difference Time Domain (FDTD. solvers, which naturally fit the pattern. The code examples/parallel_for/seismic/ uses such a solver.

Forces

  • Dependencies between items form a bipartite graph.

Solution

Alternate between updating one subset and then the other subset. Apply the elementwise pattern to each subset.

Example

The example in examples/parallel_for/seismic demonstrates the principle. In it, two physical fields velocity and stress each depend upon each other, and so cannot all be updated simultaneously. However, the velocity calculations can be done independently as long as the stress values remain fixed, and vice-versa. So the code alternates updates of the velocity and stress fields. Each update is done using tbb::parallel_for.

References

Eun-Gyu Kim and Mark Snir, "Odd-Even Communication Group", http://www.cs.uiuc.edu/homes/snir/PPP/patterns/oddeven.pdf

Para obtener información más completa sobre las optimizaciones del compilador, consulte nuestro Aviso de optimización.