Parallel Memory-Efficient Adaptive Mesh Refinement on Structured Triangular Meshes with Billions of Grid Cells
Open Access
- 15 September 2016
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Mathematical Software
- Vol. 43 (3) , 1-27
Abstract
We present sam(oa)2, a software package for a dynamically adaptive, parallel solution of 2D partial differential equations on triangular grids created via newest vertex bisection. An element order imposed by the Sierpinski space-filling curve provides an algorithm for grid generation, refinement, and traversal that is inherently memory efficient. Based purely on stack and stream data structures, it completely avoids random memory access. Using an element-oriented data view suitable for local operators, concrete simulation scenarios are implemented based on control loops and event hooks, which hide the complexity of the underlying traversal scheme. Two case studies are presented: two-phase flow in heterogeneous porous media and tsunami wave propagation, demonstrated on the Tohoku tsunami 2011 in Japan.sam(oa)2features hybrid MPI+OpenMP parallelization based on the Sierpinski order induced on the elements. Sections defined by contiguous grid cells define atomic tasks for OpenMP work sharing and stealing, as well as for migration of grid cells between MPI processes. Using optimized communication and load balancing algorithms, sam(oa)2achieves 88% strong scaling efficiency from 16 to 512 cores and 92% efficiency in a weak scaling test on 8,192 cores with 10 billion elements—all tests including adaptive mesh refinement and load balancing in each time step.Keywords
This publication has 34 references indexed in Scilit:
- Quadtree-adaptive tsunami modellingOcean Dynamics, 2011
- Tsunami modelling with adaptively refined finite volume methodsActa Numerica, 2011
- DOLFINACM Transactions on Mathematical Software, 2010
- The PDE framework Peano applied to fluid dynamics: an efficient implementation of a parallel multiscale fluid dynamics solver on octree-like adaptive Cartesian gridsComputational Mechanics, 2009
- RooflineCommunications of the ACM, 2009
- A generic grid interface for parallel and adaptive scientific computing. Part I: abstract frameworkComputing, 2008
- Augmented Riemann solvers for the shallow water equations over variable topography with steady states and inundationJournal of Computational Physics, 2008
- Wave Dispersion Study in the Indian Ocean-Tsunami of December 26, 2004Marine Geodesy, 2006
- Practical implementation of the fractional flow approach to multi-phase flow simulationAdvances in Water Resources, 1999
- Multitasking the conjugate gradient method on the CRAY X-MP/48Parallel Computing, 1987