Design of Communication Patterns for Forest-of-Octrees AMR Codes

We will discuss symmetric and non-symmetric communication patterns that arise in forest-of-octrees parallel adaptive mesh refinement (AMR). Here, symmetry means that each receiver is also a sender to the sending process, and that both messages may overlap using asynchronous calls. One algorithm that is naturally symmetric is the generation of one layer of ghost elements in order to inform applications about parallel neighbors. We will review the historic development of such a ghost algorithm up to the most recent, optimized incarnation. One algorithm that can be made symmetric by less obvious means is the identification of senders and receivers in partitioning a coarse mesh of trees. When the forest connectivity is distributed in parallel, in addition to the elements that are distributed by design, any given tree may be partially owned by multiple processes. On repartitioning the elements, the ghost trees must be updated in an m:n communication. We propose an optimal scheme that sends as few messages and as little data as possible