1.. _Odd-Even_Communication:
2
3Odd-Even Communication
4======================
5
6
7.. container:: section
8
9
10   .. rubric:: Problem
11      :class: sectiontitle
12
13   Operations on data cannot be done entirely independently, but data
14   can be partitioned into two subsets such that all operations on a
15   subset can run in parallel.
16
17
18.. container:: section
19
20
21   .. rubric:: Context
22      :class: sectiontitle
23
24   Solvers for partial differential equations can often be modified to
25   follow this pattern. For example, for a 2D grid with only
26   nearest-neighbor communication, it may be possible to treat the grid
27   as a checkerboard, and alternate between updating red squares and
28   black squares.
29
30
31   Another context is staggered grid ("leap frog") Finite Difference
32   Time Domain (FDTD solvers, which naturally fit the pattern.
33
34
35.. container:: section
36
37
38   .. rubric:: Forces
39      :class: sectiontitle
40
41   -  Dependencies between items form a bipartite graph.
42
43
44.. container:: section
45
46
47   .. rubric:: Solution
48      :class: sectiontitle
49
50   Alternate between updating one subset and then the other subset.
51   Apply the elementwise pattern to each subset.
52
53.. container:: section
54
55
56   .. rubric:: References
57      :class: sectiontitle
58
59   Eun-Gyu Kim and Mark Snir, "Odd-Even Communication Group",
60   http://snir.cs.illinois.edu/patterns/oddeven.pdf
61
62