Visible to Intel only — GUID: GUID-94999E8E-AE82-4BD9-AAFC-478525902CBE
Visible to Intel only — GUID: GUID-94999E8E-AE82-4BD9-AAFC-478525902CBE
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.
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.
References
Eun-Gyu Kim and Mark Snir, “Odd-Even Communication Group”, http://snir.cs.illinois.edu/patterns/oddeven.pdf