Decomposition of stencil update formula into atomic stages
This work provides a formal method for optimizing stencil decompositions in parallel PDE solvers, which is a domain-specific problem.
The paper addresses the decomposition of complex stencil update formulas into atomic stages that access only immediate neighbors, formulating it as an optimization problem equivalent to the dual of a minimum-cost network flow problem, enabling efficient computation of optimized decompositions.
In parallel solution of partial differential equations, a complex stencil update formula that accesses multiple layers of neighboring grid points sometimes must be decomposed into atomic stages, ones that access only immediately neighboring grid points. This paper shows that this requirement can be formulated as constraints of an optimization problem, which is equivalent to the dual of a minimum-cost network flow problem. An optimized decomposition of a single stencil on one set of grid points can thereby be computed efficiently.