Zur Kurzanzeige

Scalable Algorithms for Parallel Tree-based Adaptive Mesh Refinement with General Element Types

dc.contributor.advisorBurstedde, Carsten
dc.contributor.authorHolke, Johannes
dc.date.accessioned2020-04-25T12:54:04Z
dc.date.available2020-04-25T12:54:04Z
dc.date.issued12.12.2018
dc.identifier.urihttp://hdl.handle.net/20.500.11811/7661
dc.description.abstractIn this thesis, we develop, discuss and implement algorithms for scalable parallel tree-based adaptive mesh refinement (AMR) using space-filling curves (SFCs). We create an AMR software that works independently of the used element type, such as for example lines, triangles, tetrahedra, quadrilaterals, hexahedra, and prisms. For triangular and tetrahedral elements (simplices) with red-refinement (1:4 in 2D, 1:8 in 3D), we develop a new SFC, the tetrahedral Morton space-filling curve (TM-SFC). Its construction is similar to the Morton index for quadrilaterals/hexa- hedra, as it is also based on bitwise interleaving the coordinates of a certain vertex of the simplex, the anchor node. Additionally, we interleave with a new piece of information, the so called type.
For these simplices, we develop element local algorithms such as constructing the parent, children, or face-neighbors of a simplex, and show that most of them are constant-time operations independent of the refinement level. With SFC based partitioning it is possible that the mesh elements that are parti- tioned to one process do not form a face-connected domain. We prove the following upper bounds for the number of face-connected components of segments of the TM-SFC: With a maximum refine- ment level of L, the number of face-connected components is bounded by 2(L − 1) in 2D and 2L + 1 in 3D. Additionally, we perform a numerical investigation of the distribution of lengths of SFC segments.
Furthermore, we develop a new approach to partition and repartition a coarse (input) mesh among the processes. Compared to previous methods it optimizes for fine mesh load-balance and reduces the parallel communication of coarse mesh data. We discuss the coarse mesh repartitioning algorithm and demonstrate that our method repartitions a coarse mesh of 371e9 trees on 917,504 processes (405,000 trees per process) on the Juqueen supercomputer in 1.2 seconds.
We develop an AMR concept that works independently of the element type; achieving this independence by strictly distinguishing between functions that oper- ate on the whole mesh (high-level) and functions that locally operate on a single element or a small set of elements (low-level).
We discuss a new approach to generate and manage ghost elements that fits into our element-type independent approach. We define and describe the necessary low-level algorithms. Our main idea is the computation of tree-to-tree face-neighbors of an element via the explicit construction of the element's face as a lower dimensional element. In order to optimize the runtime of this method we enhance the algorithm with a top-down search method from Isaac, Burstedde, Wilcox, and Ghattas, and demonstrate how it speeds up the computation by factors of 10 to 20 achieving runtimes comparable to state-of-the art implementations with fixed element types.
With the ghost algorithm we build a straight-forward ripple version of the 2:1 balance algorithm. This is not an optimized version but it serves as a feasibility study for our element-type independent approach.
We implement all algorithms that we develop in this thesis in the new AMR library t8code.
Our modular approach allows us to reuse existing software, which we demonstrate by using the library p4est for quadrilateral and hexahedral elements. In a concurrent Bachelor's thesis by David Knapp (INS, Bonn) the necessary low-level algorithms for prisms were developed. With t8code we demonstrate that we can create, adapt, (re-)partition, and balance meshes, as well as create and manage a ghost layer. In various tests we show excellent strong and weak scaling behavior of our algorithms on up to 917,504 parallel processes on the Juqueen and Mira supercomputers using up to 858e9 mesh elements.
We conclude this thesis by demonstrating how an application can be coupled with the AMR routines. We implement a finite volume based advection solver using t8code and show applications with triangular, quadrilateral, tetrahedral, and hexahedral elements, as well as 2D and 3D hybrid meshes, the latter consisting of tetrahedra, hexahedra, and prisms.
Overall, we develop and demonstrate a new simplicial SFC and create a fast and scalable tree-based AMR software that offers a flexibility and generality that was previously not available.
dc.language.isoeng
dc.rightsIn Copyright
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/
dc.subjectNumerik
dc.subjectHochleistungsrechnen
dc.subjectNumerische Software
dc.subjectAdaptive Gitter
dc.subjectGitterverfeinerung
dc.subjectHigh-performance computing
dc.subjectNumerical Simulation
dc.subjectAdaptive mesh refinement
dc.subjectNumerical Software
dc.subject.ddc004 Informatik
dc.subject.ddc500 Naturwissenschaften
dc.subject.ddc510 Mathematik
dc.titleScalable Algorithms for Parallel Tree-based Adaptive Mesh Refinement with General Element Types
dc.typeDissertation oder Habilitation
dc.publisher.nameUniversitäts- und Landesbibliothek Bonn
dc.publisher.locationBonn
dc.rights.accessRightsopenAccess
dc.identifier.urnhttps://nbn-resolving.org/urn:nbn:de:hbz:5n-52410
ulbbn.pubtypeErstveröffentlichung
ulbbnediss.affiliation.nameRheinische Friedrich-Wilhelms-Universität Bonn
ulbbnediss.affiliation.locationBonn
ulbbnediss.thesis.levelDissertation
ulbbnediss.dissID5241
ulbbnediss.date.accepted2018-07-06
ulbbnediss.instituteMathematisch-Naturwissenschaftliche Fakultät : Fachgruppe Mathematik / Institut für Numerische Simulation (INS)
ulbbnediss.fakultaetMathematisch-Naturwissenschaftliche Fakultät
dc.contributor.coRefereeGriebel, Michael


Dateien zu dieser Ressource

Thumbnail

Das Dokument erscheint in:

Zur Kurzanzeige

Die folgenden Nutzungsbestimmungen sind mit dieser Ressource verbunden:

InCopyright