• 2021.4
  • 09/27/2021
  • Public Content
Contents

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

Product and Performance Information

1

Performance varies by use, configuration and other factors. Learn more at www.Intel.com/PerformanceIndex.