Skip to main content
Erschienen in:

18.06.2024 | Original Article

Generic volume transfer for distributed mesh dynamic repartitioning

verfasst von: Guillaume Damiand, Fabrice Jaillet, Vincent Vidal

Erschienen in: Engineering with Computers | Ausgabe 6/2024

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Efficient and distributed adaptive mesh construction and editing pose several challenges, including selecting the appropriate distributed data structure, choosing strategies for distributing computational load, and managing inter-processor communication. Distributed Combinatorial Maps permit the representation and editing of distributed 3D meshes. This paper addresses computation load and expands communication aspects through volume transfer operation and repartitioning strategies. This work is the first one defining such transfer for cells of any topology. We demonstrate the benefits of our method by presenting a parallel adaptive hexahedral subdivision operation, involving fully generic volumes, in a process including a conversion to conformal mesh and surface fitting. Our experiments compare different strategies using multithreading and MPI implementations to highlight the benefits of volume transfer. Special attention has been paid to generic aspects and adaptability of the framework.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
Our software will be publicly available upon acceptance of this paper.
 
Literatur
1.
Zurück zum Zitat Alauzet F, Li X, Seol Es, Shephard MS (2006) Parallel anisotropic 3D mesh adaptation by mesh modification. Eng Comput 21(3):247–258CrossRef Alauzet F, Li X, Seol Es, Shephard MS (2006) Parallel anisotropic 3D mesh adaptation by mesh modification. Eng Comput 21(3):247–258CrossRef
2.
Zurück zum Zitat Amdahl GM (1967) Validity of the single processor approach to achieving large scale computing capabilities. AFIPS ’67 (Spring). ACM. pp 483–485 Amdahl GM (1967) Validity of the single processor approach to achieving large scale computing capabilities. AFIPS ’67 (Spring). ACM. pp 483–485
3.
Zurück zum Zitat Bangerth W, Burstedde C, Heister T, Kronbichler M (2012) Algorithms and data structures for massively parallel generic adaptive finite element codes. ACM Trans Math Softw 38(2):1–28MathSciNetCrossRef Bangerth W, Burstedde C, Heister T, Kronbichler M (2012) Algorithms and data structures for massively parallel generic adaptive finite element codes. ACM Trans Math Softw 38(2):1–28MathSciNetCrossRef
4.
Zurück zum Zitat Burstedde C, Ghattas O, Gurnis M, Stadler G, Tan E, Tu T, Wilcox LC, Zhong S (2008) Scalable Adaptive mantle convection simulation on petascale supercomputers. IEEE Burstedde C, Ghattas O, Gurnis M, Stadler G, Tan E, Tu T, Wilcox LC, Zhong S (2008) Scalable Adaptive mantle convection simulation on petascale supercomputers. IEEE
5.
Zurück zum Zitat Carsten B, Omar G, Michael G, Tobin I, Georg S, Tim W, Lucas CW (2010) Extreme-scale amr Carsten B, Omar G, Michael G, Tobin I, Georg S, Tim W, Lucas CW (2010) Extreme-scale amr
6.
Zurück zum Zitat Burstedde C, Wilcox LC, Ghattas O (2011) P4est: Scalable algorithms for parallel adaptive mesh refinement on forests of octrees. SIAM J Sci Comput 33:1103–1133MathSciNetCrossRef Burstedde C, Wilcox LC, Ghattas O (2011) P4est: Scalable algorithms for parallel adaptive mesh refinement on forests of octrees. SIAM J Sci Comput 33:1103–1133MathSciNetCrossRef
7.
Zurück zum Zitat Cabiddu D, Attene M (2015) Large mesh simplification for distributed environments. Comput Graph 51(C):81–89CrossRef Cabiddu D, Attene M (2015) Large mesh simplification for distributed environments. Comput Graph 51(C):81–89CrossRef
8.
Zurück zum Zitat Campbell PM, Devine KD, Flaherty JE, Gervasio LG, Teresco JD (2003) Dynamic octree load balancing using space-filling curves. Technical report, Technical Report CS-03-01, Williams College Department of Computer Science Campbell PM, Devine KD, Flaherty JE, Gervasio LG, Teresco JD (2003) Dynamic octree load balancing using space-filling curves. Technical report, Technical Report CS-03-01, Williams College Department of Computer Science
10.
Zurück zum Zitat Damiand G, Gonzalez-Lorenzo A, Zara F, Dupont F (2018) Distributed combinatorial maps for parallel mesh processing. Algorithms 11(7):105MathSciNetCrossRef Damiand G, Gonzalez-Lorenzo A, Zara F, Dupont F (2018) Distributed combinatorial maps for parallel mesh processing. Algorithms 11(7):105MathSciNetCrossRef
11.
Zurück zum Zitat Dawes W, Harvey S, Fellows S, Eccles N, Jaeggi D, Kellar W (2009) A practical demonstration of scalable, parallel mesh generation Dawes W, Harvey S, Fellows S, Eccles N, Jaeggi D, Kellar W (2009) A practical demonstration of scalable, parallel mesh generation
12.
Zurück zum Zitat Damiand G, Lienhardt P (2014) Combinatorial maps: efficient data structures for computer graphics and image processing. A K Peters/CRC PressCrossRef Damiand G, Lienhardt P (2014) Combinatorial maps: efficient data structures for computer graphics and image processing. A K Peters/CRC PressCrossRef
13.
Zurück zum Zitat Damiand G, Nivoliers V (2022) Query-replace operations for topologically controlled 3d mesh editing. Comput Graph 106:187–199CrossRef Damiand G, Nivoliers V (2022) Query-replace operations for topologically controlled 3d mesh editing. Comput Graph 106:187–199CrossRef
14.
Zurück zum Zitat Diamond G, Smith CW, Shephard MS (2017) Dynamic load balancing of massively parallel unstructured meshes. In: Proceedings of the 8th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems, ScalA ’17, New York, NY, USA. Association for Computing Machinery Diamond G, Smith CW, Shephard MS (2017) Dynamic load balancing of massively parallel unstructured meshes. In: Proceedings of the 8th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems, ScalA ’17, New York, NY, USA. Association for Computing Machinery
15.
Zurück zum Zitat Filgueira R, Atkinson M, Nuñez A, Fernández J (2012) An adaptive, scalable, and portable technique for speeding up mpi-based applications. In: Euro-Par 2012 Parallel Processing. Springer, Berlin Heidelberg, pp 729–740 Filgueira R, Atkinson M, Nuñez A, Fernández J (2012) An adaptive, scalable, and portable technique for speeding up mpi-based applications. In: Euro-Par 2012 Parallel Processing. Springer, Berlin Heidelberg, pp 729–740
16.
Zurück zum Zitat Flaherty JE, Loy RM, Shephard MS, Szymanski BK, Teresco JD, Ziantz LH (1997) Adaptive local refinement with octree load-balancing for the parallel solution of three-dimensional conservation laws. J Parallel Distrib Comput 47(2):139–152CrossRef Flaherty JE, Loy RM, Shephard MS, Szymanski BK, Teresco JD, Ziantz LH (1997) Adaptive local refinement with octree load-balancing for the parallel solution of three-dimensional conservation laws. J Parallel Distrib Comput 47(2):139–152CrossRef
17.
Zurück zum Zitat Holke J, Burstedde C, Knapp D, Dreyer L, Elsweijer S, Ünlü V, Markert J, Lilikakis I, Böing N, Ponnusamy P et al (2023) t8code v. 1.0-modular adaptive mesh refinement in the exascale era. In: SIAM International Meshing Roundtable Workshop 2023 (SIAM IMR 2023), Amsterdam, Netherlands Holke J, Burstedde C, Knapp D, Dreyer L, Elsweijer S, Ünlü V, Markert J, Lilikakis I, Böing N, Ponnusamy P et al (2023) t8code v. 1.0-modular adaptive mesh refinement in the exascale era. In: SIAM International Meshing Roundtable Workshop 2023 (SIAM IMR 2023), Amsterdam, Netherlands
18.
Zurück zum Zitat Hendrickson B, Devine K (2000) Dynamic load balancing in computational mechanics. Comput Methods Appl Mech Eng 184(2–4):485–500CrossRef Hendrickson B, Devine K (2000) Dynamic load balancing in computational mechanics. Comput Methods Appl Mech Eng 184(2–4):485–500CrossRef
19.
Zurück zum Zitat Hendrickson B (2000) Load balancing fictions, falsehoods and fallacies. Appl Math Model 25(2):99–108CrossRef Hendrickson B (2000) Load balancing fictions, falsehoods and fallacies. Appl Math Model 25(2):99–108CrossRef
20.
Zurück zum Zitat Holke J, Knapp D, Burstedde C (2021) An optimized, parallel computation of the ghost layer for adaptive hybrid forest meshes. SIAM J Sci Comput 43(6):C359–C385MathSciNetCrossRef Holke J, Knapp D, Burstedde C (2021) An optimized, parallel computation of the ghost layer for adaptive hybrid forest meshes. SIAM J Sci Comput 43(6):C359–C385MathSciNetCrossRef
21.
Zurück zum Zitat Hasbestan JJ, Senocak I (2018) Binarized-octree generation for cartesian adaptive mesh refinement around immersed geometries. J Comput Phys 368(C):179–195MathSciNetCrossRef Hasbestan JJ, Senocak I (2018) Binarized-octree generation for cartesian adaptive mesh refinement around immersed geometries. J Comput Phys 368(C):179–195MathSciNetCrossRef
22.
Zurück zum Zitat Jaillet F, Lobos C (2022) Fast quadtree/octree adaptive meshing and re-meshing with linear mixed elements. Eng Comput 38(4):3399–3416CrossRef Jaillet F, Lobos C (2022) Fast quadtree/octree adaptive meshing and re-meshing with linear mixed elements. Eng Comput 38(4):3399–3416CrossRef
23.
Zurück zum Zitat Ji H, Lien FS, Yee E (2010) A new adaptive mesh refinement data structure with an application to detonation. J Comput Phys 229:8981–8993CrossRef Ji H, Lien FS, Yee E (2010) A new adaptive mesh refinement data structure with an application to detonation. J Comput Phys 229:8981–8993CrossRef
24.
Zurück zum Zitat Kale LV, Krishnan S (1993) Charm++ a portable concurrent object oriented system based on c++. In: Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, pp 91–108 Kale LV, Krishnan S (1993) Charm++ a portable concurrent object oriented system based on c++. In: Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, pp 91–108
25.
Zurück zum Zitat Luitjens J, Berzins M (2010) Improving the performance of uintah: A large-scale adaptive meshing computational framework. In: Int. Symp. on Parallel & Distributed Processing (IPDPS). IEEE. pp 1–10 Luitjens J, Berzins M (2010) Improving the performance of uintah: A large-scale adaptive meshing computational framework. In: Int. Symp. on Parallel & Distributed Processing (IPDPS). IEEE. pp 1–10
26.
Zurück zum Zitat Lawlor OS, Chakravorty S, Wilmarth TL, Choudhury N, Dooley I, Zheng G, Kalé LV (2006) Parfum: a parallel framework for unstructured meshes for scalable dynamic physics applications. Eng Comput 22:215–235CrossRef Lawlor OS, Chakravorty S, Wilmarth TL, Choudhury N, Dooley I, Zheng G, Kalé LV (2006) Parfum: a parallel framework for unstructured meshes for scalable dynamic physics applications. Eng Comput 22:215–235CrossRef
27.
Zurück zum Zitat Lienhardt P (1994) N-dimensional generalized combinatorial maps and cellular quasi-manifolds. Int J Comput Geom Appl 4(3):275–324MathSciNetCrossRef Lienhardt P (1994) N-dimensional generalized combinatorial maps and cellular quasi-manifolds. Int J Comput Geom Appl 4(3):275–324MathSciNetCrossRef
28.
Zurück zum Zitat Langer A, Lifflander J, Miller P, Pan K-C, Kale LV, Ricker P (2012) Scalable algorithms for distributed-memory adaptive mesh refinement. In: 24th Int. Symp. on Computer Architecture and High Performance Computing. IEEE. pp 100–107 Langer A, Lifflander J, Miller P, Pan K-C, Kale LV, Ricker P (2012) Scalable algorithms for distributed-memory adaptive mesh refinement. In: 24th Int. Symp. on Computer Architecture and High Performance Computing. IEEE. pp 100–107
29.
Zurück zum Zitat Loseille A, Menier V, Alauzet F (2015) Parallel generation of large-size adapted meshes. Procedia Eng 124:57–69CrossRef Loseille A, Menier V, Alauzet F (2015) Parallel generation of large-size adapted meshes. Procedia Eng 124:57–69CrossRef
30.
Zurück zum Zitat Livesu M, Pitzalis L, Cherchi G (2021) Optimal dual schemes for adaptive grid based hexmeshing. ACM Trans Graph 41(2):1–4CrossRef Livesu M, Pitzalis L, Cherchi G (2021) Optimal dual schemes for adaptive grid based hexmeshing. ACM Trans Graph 41(2):1–4CrossRef
31.
Zurück zum Zitat Marot C, Pellerin J, Remacle J-F (2019) One machine, one minute, three billion tetrahedra. Int J Numer Methods Eng 117(9):967–990MathSciNetCrossRef Marot C, Pellerin J, Remacle J-F (2019) One machine, one minute, three billion tetrahedra. Int J Numer Methods Eng 117(9):967–990MathSciNetCrossRef
32.
Zurück zum Zitat Nguyen TT, Dahl VA, Bærentzen JA (2017) Cache-mesh, a dynamics data structure for performance optimization. Procedia Eng 203:193–205CrossRef Nguyen TT, Dahl VA, Bærentzen JA (2017) Cache-mesh, a dynamics data structure for performance optimization. Procedia Eng 203:193–205CrossRef
33.
Zurück zum Zitat Pietroni N, Campen M, Sheffer A, Cherchi G, Bommes D, Gao X, Scateni R, Ledoux F, Remacle J, Livesu M (2022) Hex-mesh generation and processing: a survey. ACM Trans Graph 42(2):1–44CrossRef Pietroni N, Campen M, Sheffer A, Cherchi G, Bommes D, Gao X, Scateni R, Ledoux F, Remacle J, Livesu M (2022) Hex-mesh generation and processing: a survey. ACM Trans Graph 42(2):1–44CrossRef
34.
Zurück zum Zitat Sampath RS, Biros G (2010) A parallel geometric multigrid method for finite elements on octree meshes. SIAM J Sci Comput 32:1361–1392MathSciNetCrossRef Sampath RS, Biros G (2010) A parallel geometric multigrid method for finite elements on octree meshes. SIAM J Sci Comput 32:1361–1392MathSciNetCrossRef
35.
Zurück zum Zitat Seegyoung Seol E, Shephard Mark S (2006) Efficient distributed mesh data structure for parallel automated adaptive analysis. Eng Comput 22:197–213CrossRef Seegyoung Seol E, Shephard Mark S (2006) Efficient distributed mesh data structure for parallel automated adaptive analysis. Eng Comput 22:197–213CrossRef
36.
Zurück zum Zitat Tang J, Cui P, Li B, Zhang Y, Si H (2020) Parallel hybrid mesh adaptation by refinement and coarsening. Graph Models 111:101084CrossRef Tang J, Cui P, Li B, Zhang Y, Si H (2020) Parallel hybrid mesh adaptation by refinement and coarsening. Graph Models 111:101084CrossRef
37.
Zurück zum Zitat Weiler K (1985) Edge-based data structures for solid modelling in curved-surface environments. Comput Graph Appl 5(1):21–40CrossRef Weiler K (1985) Edge-based data structures for solid modelling in curved-surface environments. Comput Graph Appl 5(1):21–40CrossRef
Metadaten
Titel
Generic volume transfer for distributed mesh dynamic repartitioning
verfasst von
Guillaume Damiand
Fabrice Jaillet
Vincent Vidal
Publikationsdatum
18.06.2024
Verlag
Springer London
Erschienen in
Engineering with Computers / Ausgabe 6/2024
Print ISSN: 0177-0667
Elektronische ISSN: 1435-5663
DOI
https://doi.org/10.1007/s00366-024-02008-9