Recursive algorithms for distributed forests of octrees
Wilcox, Lucas C.
MetadataShow full item record
The forest-of-octrees approach to parallel adaptive mesh re nement and coarsening (AMR) has recently been demonstrated in the context of a number of large-scale PDE-based applications. E cient reference software has been made freely available to the public both in the form of the standalone p4est library and more indirectly by the general-purpose nite element library deal.II, which has been equipped with a p4est backend. Although linear octrees, which store only leaf octants, have an underlying tree structure by de nition, it is not fully 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 octants to design e cient recursive algorithms that operate on distributed forests of octrees. We present three important algorithms with recursive implementations. The rst is a parallel search for leaves matching any of a set of multiple search criteria, such as leaves that contain points or intersect polytopes. The second is a ghost layer construction algorithm that handles arbitrarily re ned 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 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 C0 nodal basis functions used for nite elements. We analyze the complexity of the new recursive algorithms theoretically, and assess their performance, both in terms of single-processor e ciency and in terms of parallel scalability, demonstrating good weak and strong scaling up to 458k cores of the JUQUEEN supercomputer.
RightsThis publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Showing items related by title, author, creator and subject.
Ponenti, Albert M. (Monterey, California. Naval Postgraduate School, 2008-03);National leaders, federal legislation, and the Department of Homeland Security all endorse the adoption of a risk management framework as an application for homeland security decision makers. Risk Management Frameworks ...
Negelspach, Greg L. (Monterey, California. Naval Postgraduate School, 1994-09);Optimal scheduling of parallel programs onto multiprocessor computers is an exponentially hard problem. Because of this, most scheduling algorithms in use today rely on heuristics to determine the best balance of computation ...
Lutz, Kevin D. (Monterey, CA; Naval Postgraduate School, 2021-03);Political leaders, military leaders, and the general public gather information from images and video to make decisions. Media can be spread instantaneously throughout the world at low cost and anonymously using social ...