Odd-Even Communication


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.


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.


  • Dependencies between items form a bipartite graph.


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


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.


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