A massively-parallel, unstructured overset method for mesh connectivity

Wyatt James Horne, Krishnan Mahesh

Research output: Contribution to journalArticle

Abstract

We present a method that dynamically and efficiently performs connectivity calculations between many (O(105)) moving, unstructured overset meshes in parallel. In order to connect overset meshes, elements exterior to the solution domain must be removed from the simulation. In regions with many overlapping meshes, elements must be selectively removed to reduce redundancy while maintaining a solution over the entire domain. Around masked regions interpolation partner pairing is required between meshes to provide boundary conditions. For general unstructured meshes, these steps involve challenging computational geometry calculations which must be efficient and automatic. For many moving meshes each step must be massively parallelized and scalable to large numbers of computational cores. To establish communication patterns a parallelized master/slave algorithm is used which minimizes global communication and storage. To remove elements a parallel ‘Forest Fire’ flood-fill algorithm is used to set a masking variable. For interpolation partner pairing, and other necessary searches, k-dimensional tree data structures (k-d trees) are extensively used. Often in a calculation, the connectivity between overset meshes remains largely the same between time steps. The temporal coherence of the various objects in the connectivity calculation is directly used to only update necessary information with time, resulting in substantial cost savings. Details of the different algorithms are presented. Resulting connectivity and timings are shown for complex geometries. Parallel scaling is demonstrated for 100,000 spherical particles within a channel up to 492,000 processors.

LanguageEnglish (US)
Pages585-596
Number of pages12
JournalJournal of Computational Physics
Volume376
DOIs
StatePublished - Jan 1 2019

Fingerprint

mesh
Interpolation
Computational geometry
Communication
interpolation
computational geometry
Redundancy
Data structures
communication
Fires
forest fires
Boundary conditions
data structures
redundancy
masking
Geometry
central processing units
Costs
time measurement
boundary conditions

Keywords

  • Connectivity
  • Dynamic
  • O(hundred thousand) meshes
  • Overset
  • Parallel
  • Unstructured

Cite this

A massively-parallel, unstructured overset method for mesh connectivity. / Horne, Wyatt James; Mahesh, Krishnan.

In: Journal of Computational Physics, Vol. 376, 01.01.2019, p. 585-596.

Research output: Contribution to journalArticle

@article{550a29d6e1684910aa80eb2167aae957,
title = "A massively-parallel, unstructured overset method for mesh connectivity",
abstract = "We present a method that dynamically and efficiently performs connectivity calculations between many (O(105)) moving, unstructured overset meshes in parallel. In order to connect overset meshes, elements exterior to the solution domain must be removed from the simulation. In regions with many overlapping meshes, elements must be selectively removed to reduce redundancy while maintaining a solution over the entire domain. Around masked regions interpolation partner pairing is required between meshes to provide boundary conditions. For general unstructured meshes, these steps involve challenging computational geometry calculations which must be efficient and automatic. For many moving meshes each step must be massively parallelized and scalable to large numbers of computational cores. To establish communication patterns a parallelized master/slave algorithm is used which minimizes global communication and storage. To remove elements a parallel ‘Forest Fire’ flood-fill algorithm is used to set a masking variable. For interpolation partner pairing, and other necessary searches, k-dimensional tree data structures (k-d trees) are extensively used. Often in a calculation, the connectivity between overset meshes remains largely the same between time steps. The temporal coherence of the various objects in the connectivity calculation is directly used to only update necessary information with time, resulting in substantial cost savings. Details of the different algorithms are presented. Resulting connectivity and timings are shown for complex geometries. Parallel scaling is demonstrated for 100,000 spherical particles within a channel up to 492,000 processors.",
keywords = "Connectivity, Dynamic, O(hundred thousand) meshes, Overset, Parallel, Unstructured",
author = "Horne, {Wyatt James} and Krishnan Mahesh",
year = "2019",
month = "1",
day = "1",
doi = "10.1016/j.jcp.2018.09.053",
language = "English (US)",
volume = "376",
pages = "585--596",
journal = "Journal of Computational Physics",
issn = "0021-9991",
publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - A massively-parallel, unstructured overset method for mesh connectivity

AU - Horne, Wyatt James

AU - Mahesh, Krishnan

PY - 2019/1/1

Y1 - 2019/1/1

N2 - We present a method that dynamically and efficiently performs connectivity calculations between many (O(105)) moving, unstructured overset meshes in parallel. In order to connect overset meshes, elements exterior to the solution domain must be removed from the simulation. In regions with many overlapping meshes, elements must be selectively removed to reduce redundancy while maintaining a solution over the entire domain. Around masked regions interpolation partner pairing is required between meshes to provide boundary conditions. For general unstructured meshes, these steps involve challenging computational geometry calculations which must be efficient and automatic. For many moving meshes each step must be massively parallelized and scalable to large numbers of computational cores. To establish communication patterns a parallelized master/slave algorithm is used which minimizes global communication and storage. To remove elements a parallel ‘Forest Fire’ flood-fill algorithm is used to set a masking variable. For interpolation partner pairing, and other necessary searches, k-dimensional tree data structures (k-d trees) are extensively used. Often in a calculation, the connectivity between overset meshes remains largely the same between time steps. The temporal coherence of the various objects in the connectivity calculation is directly used to only update necessary information with time, resulting in substantial cost savings. Details of the different algorithms are presented. Resulting connectivity and timings are shown for complex geometries. Parallel scaling is demonstrated for 100,000 spherical particles within a channel up to 492,000 processors.

AB - We present a method that dynamically and efficiently performs connectivity calculations between many (O(105)) moving, unstructured overset meshes in parallel. In order to connect overset meshes, elements exterior to the solution domain must be removed from the simulation. In regions with many overlapping meshes, elements must be selectively removed to reduce redundancy while maintaining a solution over the entire domain. Around masked regions interpolation partner pairing is required between meshes to provide boundary conditions. For general unstructured meshes, these steps involve challenging computational geometry calculations which must be efficient and automatic. For many moving meshes each step must be massively parallelized and scalable to large numbers of computational cores. To establish communication patterns a parallelized master/slave algorithm is used which minimizes global communication and storage. To remove elements a parallel ‘Forest Fire’ flood-fill algorithm is used to set a masking variable. For interpolation partner pairing, and other necessary searches, k-dimensional tree data structures (k-d trees) are extensively used. Often in a calculation, the connectivity between overset meshes remains largely the same between time steps. The temporal coherence of the various objects in the connectivity calculation is directly used to only update necessary information with time, resulting in substantial cost savings. Details of the different algorithms are presented. Resulting connectivity and timings are shown for complex geometries. Parallel scaling is demonstrated for 100,000 spherical particles within a channel up to 492,000 processors.

KW - Connectivity

KW - Dynamic

KW - O(hundred thousand) meshes

KW - Overset

KW - Parallel

KW - Unstructured

UR - http://www.scopus.com/inward/record.url?scp=85054598342&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85054598342&partnerID=8YFLogxK

U2 - 10.1016/j.jcp.2018.09.053

DO - 10.1016/j.jcp.2018.09.053

M3 - Article

VL - 376

SP - 585

EP - 596

JO - Journal of Computational Physics

T2 - Journal of Computational Physics

JF - Journal of Computational Physics

SN - 0021-9991

ER -