Transcription
HOSCARPaMPA :Parallel MeshPartitioning and AdaptationFrançois Pellegrini & Cédric Lachat & Cécile DobrzynskiSeptemper 3, 2013
State of the artContentsState of the artCommon needs of solvers regarding meshesWhat is PaMPAExample: Laplacian equation using P1 finite element methodSome resultsWork in progressUpcoming featuresHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 2
State of the artParallel remeshersContentsState of the artParallel remeshersLoad balancingExisting toolsHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 3
State of the artParallel remeshersContextIDistributed meshesISubdomain decompositionIData exchanges between subdomainsHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 4
State of the artParallel remeshersParallel mesh adaptation algorithmsIParallel mesh generation (N. Chrisochoides 2005 [3])IIIIDelaunay triangulationFrontal methodRefinement by subdivisions (B. G. Larwood 2003 [7])Communication between subdomains:IIData migrationMatching algorithmsHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 5
State of the artParallel remeshersProblems induced by parallelismIHigh complexity to parallelize remeshmethodsIIToo much communication onboundariesBoundaries not remeshed:IP0P1P2P3Local remeshingHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 6
State of the artParallel remeshersSequential algorithmsIMethods:IIMoving nodes and remeshing locally (O. Hassan 2006 [6])Coarse-grain parallel remeshing through multiple successivesequential remeshings (U. Tremel 2006 [8]):IIIIIFinding zones to remesh according to error estimator (T.Coupez 2000 [4])Identifying zones to remesh in parallelRemeshing zones in sequentialsubdomain load balancingMain benefits:IIScalability of algorithmsRe-use of sequential codesHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 7
State of the artLoad balancingContentsState of the artParallel remeshersLoad balancingExisting toolsHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 8
State of the artLoad balancingGeneric dynamic load balancingIGeneral purpose (re)partitioning:IIIIJostleZoltan (K. Devine 2000 [5])LB Migrate (R. Chaube 2007 [2])Require a lot of extra codingHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 9
State of the artLoad balancingSpecialized dynamic load balancing softwaresILibraries:IIDRAMA (A. Basermann 2000 [1])Pros and cons:IIMainly interfaced with solversData structures based on meshesHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 10
State of the artExisting toolsContentsState of the artParallel remeshersLoad balancingExisting toolsHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 11
State of the artExisting toolsExisting tools for handling unstructured d:IArcaneHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 12
Common needs of solvers regarding meshesContentsState of the artCommon needs of solvers regarding meshesWhat is PaMPAExample: Laplacian equation using P1 finite element methodSome resultsWork in progressUpcoming featuresHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 13
Common needs of solvers regarding meshesCommon needs of solvers regarding meshesIIHandling of mesh structuresDistribution of meshes across the processors of a parallelarchitectureIIIData exchange across neighboring entitiesIteration on mesh entitiesIIIIIEntities of any kind: e.g. elements, faces, edges, nodes, . . .Entity sub-classes: e.g. regular or boundary faces, . . .Inner or frontier entities with respect to neighboring processorsMaximization of cache effects thanks to proper data reorderingDynamic modification of mesh structureIIHandling of load balanceDynamic redistributionAdaptive remeshingHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 14
What is PaMPAContentsState of the artCommon needs of solvers regarding meshesWhat is PaMPAExample: Laplacian equation using P1 finite element methodSome resultsWork in progressUpcoming featuresHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 15
What is PaMPAWhat is PaMPAIIIPaMPA: “Parallel Mesh Partitioning and Adaptation”Middleware library managing the parallel repartitioning andremeshing of unstructured meshes modeled as interconnectedvaluated entitiesThe user can focus on his/her “core business”:IISolverSequential remesherICoupling with MMG3D provided for tetrahedraPhysics, solverRemeshing and redistributionPaMPAPT-ScotchSeq. Qual.MeasurementSequentialremesherMMG3DHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 16
What is el mesh entityMay bear some data (volume,pressure, etc.)InternalBoundaryPaMPA Mesh:IIIIIVertexRelationEntitySub-entityEnriched graphHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 17
What is PaMPADefinitionsIMay bear some data oundaryPaMPA Mesh:IIIIIVertexRelationEntitySub-entityEnriched graphHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 17
What is PaMPADefinitionsMay bear some data (flux, MPA Mesh:IIIIIVertexRelationEntitySub-entityEnriched graphHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 17
What is PaMPADefinitionsRegular mesh PA Mesh:IIIIIVertexRelationEntitySub-entityEnriched graphHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 17
What is PaMPADefinitionsBoundary mesh PA Mesh:IIIIIVertexRelationEntitySub-entityEnriched graphHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 17
What is PaMPADefinitionsWhat all entities are in fact. . .IMesh:IIIElementNodeEdgeIIIInternalBoundaryPaMPA Mesh:IIIIIVertexRelationEntitySub-entityEnriched graphHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 17
What is PaMPADefinitionsISubset of edges between verticesbelonging to prescribed entity PA Mesh:IIIIIVertexRelationEntitySub-entityEnriched graphHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 17
What is PaMPADefinitionsISubset of vertices bearing the PaMPA Mesh:IIIIIVertexRelationEntitySub-entityEnriched graphHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 17
What is PaMPADefinitionsISubset of entity vertices that maybear additional specific A Mesh:IIIIIVertexRelationEntitySub-entityEnriched graphHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 17
What is PaMPADefinitionsIMesh:IIIElementNodeEdgeIIIWhole set of vertices and relationsEvery vertex belongs to one and onlyone entity (and sub-entity)InternalBoundaryPaMPA Mesh:IIIIIVertexRelationEntitySub-entityEnriched graphHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 17
What is PaMPAGlobal vueIAll vertices have a global unique numberbaseval1enttglbnbr3proccnttab3 4 3procvrttab1 4 8 1114386725910HOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 18
What is PaMPALocal vision of process 0IAll local and ghost vertices have a compact local indexIPer-entity ab3 3 11312vendloctabvertloctab 1 2 3 82edgeloctab41 1 1 2 3 4 2HOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 19
What is PaMPAFeatures of version 0.2IOverlap greater than 1IParallel I/OIParallel partitioningIParallel remeshing based on sequential remesherHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 20
What is PaMPAParallel g4ReintegratingRemeshingHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 21
Example: Laplacian equation using P1 finite element methodContentsState of the artCommon needs of solvers regarding meshesWhat is PaMPAExample: Laplacian equation using P1 finite element methodSome resultsWork in progressUpcoming featuresHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 22
Example: Laplacian equation using P1 finite element methodDefinitionISolving 2D Poisson equation:III u (x , y ) f (x , y )g (x , y ) u (x , y ) on theboundary ΓTest case:IIIf (x , y ) 2 cos (x ) cos (y )in the domain Ωg (x , y ) cos (x ) cos (y ) onthe boundary Γu (x , y ) cos (x ) cos (y )HOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 23
Example: Laplacian equation using P1 finite element methodMesh desBoundary edgesElementElementElementNode toto elementto nodeto boundary edgenodeOverlap of size 1Values:IIICoordinates and solution on nodesType on boundary edgesArea, volume on elementsHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 24
Example: Laplacian equation using P1 finite element methodAll steps! OnCALL!!!CALLCALLa l l processors :D i s t r i b u t e d M e s h ( ) ! B u i l d PaMPA d i s t r i b u t e d mesh :1 Read i n p a r a l l e l a c e n t r a l i z e d mesh2 C a l l PaMPA mesh p a r t i o n e r3 R e d i s t r i b u t e d i s t r i b u t e meshElementVolume ( )InitializeMatrixCSR ()! S o l u t i o n computation! CALLCALLCALLCALLI n i t S o l ()FillMatrix ()SolveSystem ()WriteDistributedMeshAndSolFiles ()HOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 25
Example: Laplacian equation using P1 finite element methodFillMatrixRHS 0 .CALL P A M P A F d m e s h I t I n i t S t a r t (dm , ENTITY ELEM , PAMPAF VERT ANY , i t v r t , i e r r )CALL PAMPAF dmeshItInit (dm , ENTITY ELEM , ENTITY NODE , i t n g b , i e r r )DO WHILE ( PAMPAF itHasMore ( i t v r t ) )jt PAMPAF itCurEnttVertNum ( i t v r t )Volt VolEl ( j t )ngb 0CALL PAMPAF itStart ( i t n g b , j t , i e r r )DO WHILE ( PAMPAF itHasMore ( i t n g b ) )ngb ngb 1i s PAMPAF itCurEnttVertNum ( i t n g b )NuElemt ( ngb ) isC o o r E l e m t ( : , ngb ) Coor ( : , i s )PAMPAF itNext ( i t n g b )END DOCALL G r a d P h i ( C o o r E l e m t ( : , 1 ) , C o o r E l e m t ( : , 2 ) , C o o r E l e m t ( : , 3 ) , G r d P h i )DO i 1 , Nsmplxi s NuElemt ( i )DO j 1 , Nsmplxjs NuElemt ( j )J J a c V o l t Sum ( G r d P h i ( : , i ) G r d P h i ( : , j ) )CALL a s s e m b l y a d d C S R ( JJac , i s , j s )END DO ! l o o p on jRHS( i s ) RHS( i s ) V o l t SourceTerm ( Coor ( 1 , i s ) , Coor ( 2 , i s ) ) / NsmplxEND DO ! l o o p on iPAMPAF itNext ( i t v r t )END DOHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 26
Example: Laplacian equation using P1 finite element methodSolve system: Jacobi (1/2)UaPrec 0 .! Suppose A L D U, system to s o l v e : A x bCALL PAMPAF dmeshItInit (dm , ENTITY NODE , ENTITY NODE , i t n g b , i e r r )DO i r e l a x 1 , N r e l a xres 0.CALL P A M P A F d m e s h I t I n i t S t a r t (dm , ENTITY NODE , PAMPAF VERT BOUNDARY, i t v r t ,DO WHILE ( PAMPAF itHasMore ( i t v r t ) )i s PAMPAF itCurEnttVertNum ( i t v r t )CALL PAMPAF dmeshMatLineData (dm , ENTITY NODE , i s , I 1 , I 1 F i n , i e r r )CALL PAMPAF itStart ( i t n g b ,is ,ierr )res0 RHS( i s )! res0 bierr )iv i1DO WHILE ( PAMPAF itHasMore ( i t n g b ) )j s PAMPAF itCurEnttVertNum ( i t n g b )PAMPAF itNext ( i t n g b )r e s 0 r e s 0 MatCSR%V a l s ( i v ) UaPrec ( j s ) ! r e s 0 b ( L U) x ˆniv iv 1END DOUa ( i s ) r e s 0 / MatCSR%Diag ( i s )! x ˆn 1 ( b ( L U) x ˆn ) /DPAMPAF itNext ( i t v r t )END DOCALL PAMPAF dmeshHaloValueAsync (dm , ENTITY NODE , PAMPA TAG SOL , r e q ,HOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPAierr )Septemper 3, 2013- 27
Example: Laplacian equation using P1 finite element methodSolve system: Jacobi (2/2)CALL P A M P A F d m e s h I t I n i t S t a r t (dm , ENTITY NODE , PAMPAF VERT INTERNAL , i t v r t ,DO WHILE ( PAMPAF itHasMore ( i t v r t ) )i s PAMPAF itCurEnttVertNum ( i t v r t )CALL PAMPAF dmeshMatLineData (dm , ENTITY NODE , i s , I 1 , I 1 F i n , i e r r )CALL PAMPAF itStart ( i t n g b ,is ,ierr )res0 RHS( i s )! res0 bierr )iv i1DO WHILE ( PAMPAF itHasMore ( i t n g b ) )j s PAMPAF itCurEnttVertNum ( i t n g b )PAMPAF itNext ( i t n g b )r e s 0 r e s 0 MatCSR%V a l s ( i v ) UaPrec ( j s ) ! r e s 0 b ( L U) x ˆniv iv 1END DOUa ( i s ) r e s 0 / MatCSR%Diag ( i s )! x ˆn 1 ( b ( L U) x ˆn ) /DPAMPAF itNext ( i t v r t )END DOCALL PAMPAF dmeshHaloWait ( r e q ,ierr )UaPrec UaEND DO ! end l o o p on i r e l a xHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 28
Some resultsContentsState of the artCommon needs of solvers regarding meshesWhat is PaMPAExample: Laplacian equation using P1 finite element methodSome resultsWork in progressUpcoming featuresHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 29
Some resultsFirst results (1/2)Before remeshingNumber of elements 2 423 029Number of nodes1 071 626HOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 30
Some resultsFirst results (2/2)Processor frequency (GHz)Used memory (kb)Elapsed timeNumber of elementsSmallest edge lengthLargest edge lengthWorst element qualityElement quality between 1 and 2Edge length between 0.71 and 1.41MMG3don 1 processor2,4027 588 94017:15:12108 126 5150.14706.3309294.266999.65%97.25%HOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPAPaMPA-MMG3don 24 processors3,0651 116 04400:21:14115 802 8760.139511.2415294.266999.38%97.65%Septemper 3, 2013- 31
Work in progressContentsState of the artCommon needs of solvers regarding meshesWhat is PaMPAExample: Laplacian equation using P1 finite element methodSome resultsWork in progressUpcoming featuresHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 32
Work in progressWork in progressIRelease of version 0.2IIAvailable soon from Inria GforgeLicensed under GPLIQuality of parallel adapted meshesIPeriodic meshesHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 33
Upcoming featuresContentsState of the artCommon needs of solvers regarding meshesWhat is PaMPAExample: Laplacian equation using P1 finite element methodSome resultsWork in progressUpcoming featuresHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 34
Upcoming featuresUpcoming featuresICode industrialisationIMesh definition with a grammarIFace orientation and displacementUnbreakable relationsIIIPartitioner will not cut these edgesE.g. to implement DG methodsIMulti-grid meshesIParallel I/O with HDF5IParallel mesh adaptation scalabilityHOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 35
Upcoming featuresThank youFran ois PellegriniSeptember 4, 2013
BibliographieA. Basermann, J. Clinckemaillie, T. Coupez, J. Fingberg,H. Digonnet, R. Ducloux, J.-M. Gratien, U. Hartmann,G. Lonsdale, B. Maerten, D. Roose, and C. Walshaw.Dynamic load balancing of finite element applications with thedrama library, 2000.R. Chaube, R. L. Carino, and I. Banicescu.Effectiveness of a dynamic load balancing library for scientificapplications.In ISPDC ’07: Proceedings of the Sixth InternationalSymposium on Parallel and Distributed Computing, page 32,Washington, DC, USA, 2007. IEEE Computer Society.N. Chrisochoides.Parallel mesh generation.In in Numerical Solution of Partial Differential Equations onParallel Computers. Springer, 2005.HOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 37
BibliographieT. Coupez, H. Digonnet, and R. Ducloux.Parallel meshing and remeshing.Applied Mathematical Modelling, 25(2):153 – 175, 2000.Dynamic load balancing of mesh-based applications on parallel.K. Devine, B. Hendrickson, E. Boman, M. St. John, andC. Vaughan.Design of dynamic load-balancing tools for parallelapplications.In ICS ’00: Proceedings of the 14th international conferenceon Supercomputing, pages 110–118, New York, NY, USA,2000. ACM.HOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 38
BibliographieO. Hassan, K. A. Sørensen, K. Morgan, and N. P. Weatherill.A method for time accurate turbulent compressible fluid flowsimulation with moving boundary components employing localremeshing.In International Journal for Numerical Methods in Fluids,volume 53, pages 1243–1266. John Wiley & Sons, 2007.B. G. Larwood, N. Weatherhill, O. Hassan, and K. Morgan.Domain decomposition approach for parallel unstructuredmesh generation.In International Journal for Numerical Methods in Engineering,volume 58, pages 177–188, 2003.HOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 39
BibliographieU. Tremel, K. A. Sørensen, S. Hitzel, H. Rieger, O. Hassan,and N. P. Weatherill.Parallel remeshing of unstructured volume grids for cfdapplications.In International Journal for Numerical Methods in Fluids,volume 53, pages 1361–1379. John Wiley & Sons, 2007.HOSCAR - F. Pellegrini & C. Lachat & C. Dobrzynski - PaMPASeptemper 3, 2013- 40
Common needs of solvers regarding meshes Common needs of solvers regarding meshes I Handling of mesh structures I Distribution of meshes across the processors of a parallel architecture I Handling of load balance I Data exchange across neighboring entities I Iteration on mesh entities I Entities of any kind: e.g. elements, faces, edges, nodes, . I Entity sub-classes: e.g. regular or boundary .
