Recursive Algorithms for Distributed Forests of Octrees

Abstract

The forest-of-octrees approach to parallel adaptive mesh refinement and coarsening (AMR) has recently been demonstrated in the context of a number of large-scale PDE-based applications. Although linear octrees, which store only leaf octants, have an underlying tree structure by definition, it is not often exploited in previously published mesh-related algorithms. This is because the branches are not explicitly stored, and because the topological relationships in meshes, such as the adjacency between cells, introduce dependencies that do not respect the octree hierarchy. In this work we combine hierarchical and topological relationships between octree branches to design efficient recursive algorithms. We present three important algorithms with recursive implementations. The first is a parallel search for leaves matching any of a set of multiple search criteria. The second is a ghost layer construction algorithm that handles arbitrarily refined octrees that are not covered by previous algorithms, which require a 2:1 condition between neighboring leaves. The third is a universal mesh topology iterator. This iterator visits every cell in a domain partition, as well as every interface (face, edge and corner) between these cells. The iterator calculates the local topological information for every interface that it visits, taking into account the nonconforming interfaces that increase the complexity of describing the local topology. To demonstrate the utility of the topology iterator, we use it to compute the numbering and encoding of higher-order $C^0$ nodal basis functions. We analyze the complexity of the new recursive algorithms theoretically, and assess their performance, both in terms of single-processor efficiency and in terms of parallel scalability, demonstrating good weak and strong scaling up to 458k cores of the JUQUEEN supercomputer.

35 pages, 15 figures, 3 tables

References in corpus (1)

• A Parallel Mesh-Adaptive Framework for Hyperbolic Conservation Laws

Cited by in corpus (14)

• Flexible and scalable particle-in-cell methods for massively parallel computations
• A scalable parallel finite element framework for growing geometries. Application to metal additive manufacturing
• The aggregated unfitted finite element method on parallel tree-based adaptive meshes
• Enhancing speed and scalability of the ParFlow simulation code
• Fully Parallel Mesh I/O using PETSc DMPlex with an Application to Waveform Modeling
• Landau Collision Integral Solver with Adaptive Mesh Refinement on Emerging Architectures
• A tetrahedral space-filling curve for non-conforming adaptive meshes
• Enclave Tasking for Discontinuous Galerkin Methods on Dynamically Adaptive Meshes
• Coupling parallel adaptive mesh refinement with a nonoverlapping domain decomposition solver
• Magnetohydrodynamic shock refraction at an inclined density interface
• An Energy Stable Approach for Discretizing Hyperbolic Equations with Nonconforming Discontinuous Galerkin Methods
• A generic finite element framework on parallel tree-based adaptive meshes
• Exascale Landau collision operator in the Cuda programming model applied to thermal quench plasmas
• An Explicit Local Space-Time Adaptive Framework for Monodomain Models