奇偶通信#
問題
データに対する操作は完全に独立して実行することはできませんが、データを 2 つのサブセットに分割することで、サブセットに対するすべての操作を並列に実行できます。
コンテキスト
偏微分方程式のソルバーは、多くの場合、このパターンに従うように変更できます。例えば、近傍通信のみを行う 2D グリッドの場合、グリッドをチェッカーボードとして扱い、赤いマスと黒いマスを交互に更新することができます。
もう 1 つのコンテキストは段差グリッド (「リープフロッグ」) 有限差分時間領域法 (FDTD) ソルバーが、このパターンに自然に適合します。
強制
項目間の依存関係は二部グラフを形成します。
解決方法
1 つのサブセットを更新してから、他のサブセットを交互に更新します。各サブセットに要素ごとのパターンを適用します。
参考資料
Eun-Gyu Kim and Mark Snir, “Odd-Even Communication Group”, http://snir.cs.illinois.edu/patterns/oddeven.pdf