Article

Extreme-Scale AMR

Authors:

Carsten Burstedde,

Michael Gurnis,

Lucas WilcoxAuthors Info & Claims

SC '10: Proceedings of the 2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis

Pages 1 - 12

https://doi.org/10.1109/SC.2010.25

Published: 13 November 2010 Publication History

Abstract

Many problems are characterized by dynamics occurring on a wide range of length and time scales. One approach to overcoming the tyranny of scales is adaptive mesh refinement/coarsening (AMR), which dynamically adapts the mesh to resolve features of interest. However, the benefits of AMR are difficult to achieve in practice, particularly on the petascale computers that are essential for difficult problems. Due to the complex dynamic data structures and frequent load balancing, scaling dynamic AMR to hundreds of thousands of cores has long been considered a challenge. Another difficulty is extending parallel AMR techniques to high-order-accurate, complex-geometry-respecting methods that are favored for many classes of problems. Here we present new parallel algorithms for parallel dynamic AMR on forest-ofoctrees geometries with arbitrary-order continuous and discontinuous finite/spectral element discretizations. The implementations of these algorithms exhibit excellent weak and strong scaling to over 224,000 Cray XT5 cores for multiscale geophysics problems.

References

[1]

M. Ainsworth and J. T. Oden, A posteriori error estimation in finite element analysis, ser. Pure and Applied Mathematics (New York). New York: John Wiley & Sons, 2000.

[2]

I. Babu¿ka and T. Strouboulis, The finite element method and its reliability, ser. Numerical Mathematics and Scientific Computation. The Clarendon Press, Oxford University Press, New York, 2001.

[3]

R. Becker and R. Rannacher, "An optimal control approach to a posteriori error estimation in finite element methods," Acta Numerica, vol. 10, pp. 1-102, 2001.

[4]

L. Demkowicz, J. Kurtz, D. Pardo, M. Paszynski, W. Rachowicz, and A. Zdunek, Computing with hp Finite Elements II. Frontiers: Three-Dimensional Elliptic and Maxwell Problems with Applications. CRC Press, Taylor and Francis, 2007.

Digital Library

[5]

L. F. Diachin, R. Hornung, P. Plassmann, and A. Wissink, "Parallel adaptive mesh refinement," in Parallel Processing for Scientific Computing, ser. Software, Environments, and Tools, M. A. Heroux, P. Raghavan, and H. D. Simon, Eds. SIAM, 2006, no. 20, ch. 8.

[6]

C. Burstedde, O. Ghattas, M. Gurnis, E. Tan, T. Tu, G. Stadler, L. C. Wilcox, and S. Zhong, "Scalable adaptive mantle convection simulation on petascale supercomputers," in SC '08: Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis. ACM/IEEE, 2008.

Digital Library

[7]

C. Burstedde, L. C. Wilcox, and O. Ghattas, "p4est: Scalable algorithms for parallel adaptive mesh refinement on forests of octrees," 2010, submitted to SIAM Journal on Scientific Computing. http://ccgo.ices.utexas.edu/publications/ BursteddeWilcoxGhattas10.pdf.

Digital Library

[8]

L. C. Wilcox, G. Stadler, C. Burstedde, and O. Ghattas, "A high-order discontinuous Galerkin method for wave propagation through coupled elastic-acoustic media," Journal of Computational Physics, 2010, submitted, http://ccgo.ices.utexas.edu/ publications/WilcoxStadlerBursteddeEtAl10.pdf.

Digital Library

[9]

G. Stadler, M. Gurnis, C. Burstedde, L. C. Wilcox, L. Alisic, and O. Ghattas, "The dynamics of plate tectonics and mantle flow: From local to global scales," 2010, Science, In press.

[10]

M. J. Berger and J. Oliger, "Adaptive mesh refinement for hyperbolic partial differential equations," Journal of Computational Physics, vol. 53, no. 3, pp. 484-512, 1984.

[11]

A. Calder, B. Curtis, L. Dursi, B. Fryxell, G. Henry, P. MacNeice, K. Olson, P. Ricker, R. Rosner, F. Timmes, H. Tufo, J. Truran, and M. Zingale, "High-performance reactive fluid flow simulations using adaptive mesh refinement on thousands of processors," in SC '00: Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis. ACM/IEEE, 2000, pp. 56-56.

Digital Library

[12]

G. L. Bryan, T. Abel, and M. L. Norman, "Achieving extreme resolution in numerical cosmology using adaptive mesh refinement: Resolving primordial star formation," in SC '01: Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis. ACM/IEEE, 2001.

Digital Library

[13]

T. Goodale, G. Allen, G. Lanfermann, J. Massó, T. Radke, E. Seidel, and J. Shalf, "The Cactus framework and toolkit: Design and applications," in Vector and Parallel Processing - VECPAR '2002, 5th International Conference. Springer, 2003.

Digital Library

[14]

J. Luitjens, B. Worthen, M. Berzins, and T. Henderson, "Scalable parallel AMR for the Uintah multiphysics code," in Petascale Computing Algorithms and Applications, D. Bader, Ed. Chapman and Hall/CRC, 2007.

[15]

P. Colella, D. Graves, N. Keen, T. Ligocki, D. F. Martin, P. McCorquodale, D. Modiano, P. O. Schwartz, T. D. Sternberg, and B. Van Straalen, Chombo Software Package for AMR Applications. Design Document., Applied Numerical Algoirthms Group, NERSC Division, Lawrence Berkeley National Laboratory, Berkeley, CA, May 2007.

[16]

P. Colella, J. Bell, N. Keen, T. Ligocki, M. Lijewski, and B. van Straalen, "Performance and scaling of locally-structured grid methods for partial differential equations," Journal of Physics: Conference Series, vol. 78, pp. 1-13, 2007.

[17]

J. Luitjens and M. Berzins, "Improving the performance of Uintah: A large-scale adaptive meshing computational framework," in Proceedings of the 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2010.

[18]

J. E. Flaherty, R. M. Loy, M. S. Shephard, B. K. Szymanski, J. D. Teresco, and L. H. Ziantz, "Adaptive local refinement with octree load balancing for the parallel solution of three-dimensional conservation laws," Journal of Parallel and Distributed Computing, vol. 47, no. 2, pp. 139-152, 1997.

Digital Library

[19]

C. D. Norton, J. Z. Lou, and T. A. Cwik, "Status and directions for the pyramid parallel unstructured amr library," in Proceedings of the 15th IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2001, p. 120.

Digital Library

[20]

O. S. Lawlor, S. Chakravorty, T. L. Wilmarth, N. Choudhury, I. Dooley, G. Zheng, and L. V. Kalé, "ParFUM: a parallel framework for unstructured meshes for scalable dynamic physics applications," Engineering with Computers, vol. 22, no. 3, pp. 215-235, 2006.

Digital Library

[21]

B. Bergen, F. Hülsemann, and U. Rüde, "Is 1.7 × 10¹⁰ unknowns the largest finite element system that can be solved today?" in SC '05: Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis. ACM/IEEE, 2005.

Digital Library

[22]

M. Griebel and G. W. Zumbusch, "Parallel multigrid in an adaptive PDE solver based on hashing and space-filling curves," Parallel Computing, vol. 25, pp. 827-843, 1999.

Digital Library

[23]

S. Popinet, "Gerris: a tree-based adaptive solver for the incompressible Euler equations in complex geometries," Journal of Computational Physics, vol. 190, no. 2, pp. 572-600, 2003.

Digital Library

[24]

J. R. Stewart and H. C. Edwards, "A framework approach for developing parallel adaptive multiphysics applications," Finite Elements in Analysis and Design, vol. 40, no. 12, pp. 1599-1617, 2004.

Digital Library

[25]

D. Rosenberg, A. Fournier, P. Fischer, and A. Pouquet, "Geophysical-astrophysical spectral-element adaptive refinement (GASpAR): Object-oriented h-adaptive fluid dynamics simulation," Journal of Computational Physics, vol. 215, no. 1, pp. 59-80, 2006.

Digital Library

[26]

A. Laszloffy, J. Long, and A. K. Patra, "Simple data management, scheduling and solution strategies for managing the irregularities in parallel adaptive hp finite element simulations," Parallel Computing, vol. 26, pp. 1765-1788, 2000.

Digital Library

[27]

M. Paszynski, D. Pardo, C. Torres-Verdín, L. Demkowicz, and V. Calo, "A parallel direct solver for self-adaptive hp-finite element method," Journal of Parallel and Distributed Computing, vol. 70, pp. 270-281, 2010.

Digital Library

[28]

V. Akçelik, J. Bielak, G. Biros, I. Epanomeritakis, A. Fernandez, O. Ghattas, E. J. Kim, J. Lopez, D. R. O'Hallaron, T. Tu, and J. Urbanic, "High resolution forward and inverse earthquake modeling on terascale computers," in SC '03: Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis. ACM/IEEE, 2003, Gordon Bell Prize for Special Achievement.

Digital Library

[29]

T. Tu, D. R. O'Hallaron, and O. Ghattas, "Scalable parallel octree meshing for terascale applications," in SC '05: Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis. ACM/IEEE, 2005.

Digital Library

[30]

H. Sundar, R. S. Sampath, S. S. Adavani, C. Davatzikos, and G. Biros, "Low-constant parallel algorithms for finite element simulations using linear octrees," in SC '07: Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis. ACM/IEEE, 2007.

Digital Library

[31]

C. Burstedde, O. Ghattas, G. Stadler, T. Tu, and L. C. Wilcox, "Towards adaptive mesh PDE simulations on petascale computers," in Proceedings of Teragrid '08, 2008.

[32]

R. S. Sampath, S. S. Adavani, H. Sundar, I. Lashuk, and G. Biros, "Dendro: Parallel algorithms for multigrid and AMR methods on 2:1 balanced octrees," in SC '08: Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis. ACM/IEEE, 2008.

Digital Library

[33]

R. S. Sampath and G. Biros, "A parallel geometric multigrid method for finite elements on octree meshes," SIAM Journal on Scientific Computing, vol. 32, no. 3, pp. 1361-1392, 2010.

Digital Library

[34]

B. S. Kirk, J. W. Peterson, R. H. Stogner, and G. F. Carey, "libMesh: A C++ library for parallel adaptive mesh refinement/coarsening simulations," Engineering with Computers, vol. 22, no. 3-4, pp. 237-254, 2006.

Digital Library

[35]

W. Bangerth, R. Hartmann, and G. Kanschat, "deal.II - a general-purpose object-oriented finite element library," ACM Transactions on Mathematical Software, vol. 33, no. 4, p. 24, 2007.

Digital Library

[36]

G. M. Morton, "A computer oriented geodetic data base; and a new technique in file sequencing," IBM Ltd., Tech. Rep., 1966.

[37]

J. S. Hesthaven and T. Warburton, Nodal Discontinuous Galerkin Methods: Algorithms, Analysis, and Applications, ser. Texts in Applied Mathematics. Springer, 2008, vol. 54.

Digital Library

[38]

M. H. Carpenter and C. A. Kennedy, "Fourth-order 2N- storage Runge-Kutta schemes," NASA Langley Research Center, Hampton, Virginia 23681-0001, NASA Technical Memorandum 109112, June 1994.

[39]

M. Deville, P. Fischer, and E. Mund, High-Order Methods for Incompressible Fluid Flow, ser. Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, 2002, vol. 9.

[40]

C. Dohrmann and P. Bochev, "A stabilized finite element method for the Stokes problem based on polynomial pressure projections," International Journal for Numerical Methods in Fluids, vol. 46, pp. 183-201, 2004.

[41]

M. Gee, C. Siefert, J. Hu, R. Tuminaro, and M. Sala, "ML 5.0 smoothed aggregation user's guide," Sandia National Laboratories, Tech. Rep. SAND2006-2649, 2006.

[42]

C. Burstedde, O. Ghattas, G. Stadler, T. Tu, and L. C. Wilcox, "Parallel scalable adjoint-based adaptive solution for variable-viscosity Stokes flows," Computer Methods in Applied Mechanics and Engineering, vol. 198, pp. 1691-1700, 2009.

[43]

M. Billen and G. Hirth, "Rheologic controls on slab dynamics," Geochemistry, Geophysics, Geosystems, vol. 8, p. Q08012, 2007.

[44]

A. M. Dziewonski and D. L. Anderson, "Preliminary reference earth model," Physics of the Earth and Planetary Interiors, vol. 25, no. 4, pp. 297-356, 1981.

[45]

"Performance applications programming interface (PAPI)." {Online}. Available: http://icl.cs.utk.edu/papi/

[46]

A. Klöckner, T. Warburton, J. Bridge, and J. S. Hesthaven, "Nodal discontinuous Galerkin methods on graphics processors," Journal of Computational Physics, vol. 228, no. 21, pp. 7863-7882, 2009.

Digital Library

Cited By

Wolf SGalis MUphoff CGabriel AMoczo PGregor DBader M(2022)An efficient ADER-DG local time stepping scheme for 3D HPC simulation of seismic waves in poroelastic mediaJournal of Computational Physics10.1016/j.jcp.2021.110886455:COnline publication date: 15-Apr-2022
https://dl.acm.org/doi/10.1016/j.jcp.2021.110886
Mascagni MKirby ABrazell MYang ZRoy RAhrabi BStoellinger MSitaraman JMavriplis D(2020)Wind farm simulations using an overset hp-adaptive approach with blade-resolved turbine modelsInternational Journal of High Performance Computing Applications10.1177/109434201983296033:5(897-923)Online publication date: 17-Jun-2020
https://dl.acm.org/doi/10.1177/1094342019832960
Lin HZhu XYu BTang XXue WChen WZhang LHoefler TMa XLiu XZheng WXu J(2018)ShenTuProceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis10.5555/3291656.3291731(1-11)Online publication date: 11-Nov-2018
https://dl.acm.org/doi/10.5555/3291656.3291731
Show More Cited By

Extreme-Scale AMR
1. Mathematics of computing
  1. Mathematical analysis
    1. Differential equations

Recommendations

Large scale parallel structured AMR calculations using the SAMRAI framework
SC '01: Proceedings of the 2001 ACM/IEEE conference on Supercomputing

This paper discusses the design and performance of the parallel data communication infrastructure in SAMRAI, a software framework for structured adaptive mesh refinement (SAMR) multi-physics applications. We describe requirements of such applications ...
Coarse Mesh Partitioning for Tree-Based AMR
^† Special Section: 2016 Copper Mountain Conference

In tree-based adaptive mesh refinement, elements are partitioned between processes using a space-filling curve. The curve establishes an ordering between all elements that derive from the same root element, the tree. When representing complex geometries by ...
Visualization of AMR Data With Multi-Level Dual-Mesh Interpolation

We present a new technique for providing interpolation within cell-centered Adaptive Mesh Refinement (AMR) data that achieves C^0 continuity throughout the 3D domain. Our technique improves on earlier work in that it does not require that adjacent ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SC '10: Proceedings of the 2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis

November 2010

634 pages

ISBN:9781424475599

Conference Chair:
Barry V. Hess

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture
IEEE-CS: Computer Society

Publisher

IEEE Computer Society

United States

Publication History

Published: 13 November 2010

Check for updates

Qualifiers

Article

Conference

SC '10

Sponsor:

SIGARCH
IEEE-CS

SC '10: International Conference for High Performance Computing, Networking, Storage and Analysis

November 13 - 19, 2010

Acceptance Rates

SC '10 Paper Acceptance Rate 51 of 253 submissions, 20%;

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
421
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wolf SGalis MUphoff CGabriel AMoczo PGregor DBader M(2022)An efficient ADER-DG local time stepping scheme for 3D HPC simulation of seismic waves in poroelastic mediaJournal of Computational Physics10.1016/j.jcp.2021.110886455:COnline publication date: 15-Apr-2022
https://dl.acm.org/doi/10.1016/j.jcp.2021.110886
Mascagni MKirby ABrazell MYang ZRoy RAhrabi BStoellinger MSitaraman JMavriplis D(2020)Wind farm simulations using an overset hp-adaptive approach with blade-resolved turbine modelsInternational Journal of High Performance Computing Applications10.1177/109434201983296033:5(897-923)Online publication date: 17-Jun-2020
https://dl.acm.org/doi/10.1177/1094342019832960
Lin HZhu XYu BTang XXue WChen WZhang LHoefler TMa XLiu XZheng WXu J(2018)ShenTuProceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis10.5555/3291656.3291731(1-11)Online publication date: 11-Nov-2018
https://dl.acm.org/doi/10.5555/3291656.3291731
Lin HZhu XYu BTang XXue WChen WZhang LHoefler TMa XLiu XZheng WXu J(2018)ShenTuProceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis10.1109/SC.2018.00059(1-11)Online publication date: 11-Nov-2018
https://dl.acm.org/doi/10.1109/SC.2018.00059
Camata JSilva VValduriez PMattoso MCoutinho A(2018)In situ visualization and data analysis for turbidity currents simulationComputers & Geosciences10.1016/j.cageo.2017.09.013110:C(23-31)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1016/j.cageo.2017.09.013
Uphoff CRettenberger SBader MMadden EUlrich TWollherr SGabriel AMohr BRaghavan P(2017)Extreme scale multi-physics simulations of the tsunamigenic 2004 sumatra megathrust earthquakeProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3126908.3126948(1-16)Online publication date: 12-Nov-2017
https://dl.acm.org/doi/10.1145/3126908.3126948
de la Asuncin MCastro M(2017)Simulation of tsunamis generated by landslides using adaptive mesh refinement on GPUJournal of Computational Physics10.1016/j.jcp.2017.05.016345:C(91-110)Online publication date: 15-Sep-2017
https://dl.acm.org/doi/10.1016/j.jcp.2017.05.016
Feng DTsolakis CChernikov AChrisochoides N(2017)Scalable 3D hybrid parallel Delaunay image-to-mesh conversion algorithm for distributed shared memory architecturesComputer-Aided Design10.1016/j.cad.2016.07.01085:C(10-19)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1016/j.cad.2016.07.010
Wahib MMaruyama NAoki TWest J(2016)DainoProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.5555/3014904.3014975(1-12)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.5555/3014904.3014975
Bakhtiari AMalhotra DRaoofy AMehl MBungartz HBiros GWest J(2016)A parallel arbitrary-order accurate AMR algorithm for the scalar advection-diffusion equationProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.5555/3014904.3014963(1-12)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.5555/3014904.3014963
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents