.. _Odd-Even_Communication:
Odd-Even Communication
======================
.. container:: section
.. rubric:: Problem
:class: sectiontitle
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.
.. container:: section
.. rubric:: Context
:class: sectiontitle
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.
.. container:: section
.. rubric:: Forces
:class: sectiontitle
- Dependencies between items form a bipartite graph.
.. container:: section
.. rubric:: Solution
:class: sectiontitle
Alternate between updating one subset and then the other subset.
Apply the elementwise pattern to each subset.
.. container:: section
.. rubric:: References
:class: sectiontitle
Eun-Gyu Kim and Mark Snir, "Odd-Even Communication Group",
http://snir.cs.illinois.edu/patterns/oddeven.pdf
Generated by dwww version 1.15 on Thu Jun 20 17:23:03 CEST 2024.