Dendro: parallel algorithms for multigrid and AMR methods on 2:1 balanced octrees

ABSTRACT

In this article, we present Dendro, a suite of parallel algorithms for the discretization and solution of partial differential equations (PDEs) involving second-order elliptic operators. Dendro uses trilinear finite element discretizations constructed using octrees. Dendro, comprises four main modules: a bottom-up octree generation and 2:1 balancing module, a meshing module, a geometric multiplicative multigrid module, and a module for adaptive mesh refinement (AMR). Here, we focus on the multigrid and AMR modules. The key features of Dendro are coarsening/refinement, inter-octree transfers of scalar and vector fields, and parallel partition of multilevel octree forests. We describe a bottom-up algorithm for constructing the coarser multigrid levels. The input is an arbitrary 2:1 balanced octree-based mesh, representing the fine level mesh. The output is a set of octrees and meshes that are used in the multigrid sweeps. Also, we describe matrix-free implementations for the discretized PDE operators and the intergrid transfer operations. We present results on up to 4096 CPUs on the Cray XT3 ("BigBen"), the Intel 64 system ("Abe"), and the Sun Constellation Linux cluster ("Ranger").

REFERENCES

• 1: Mark F. Adams , Harun H. Bayraktar , Tony M. Keaveny , Panayiotis Papadopoulos, Ultrascalable Implicit Finite Element Analyses in Solid Mechanics with over a Half a Billion Degrees of Freedom, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.34, November 06-12, 2004 [doi>10.1109/SC.2004.62]
• 2: Vokan Akcelik , Jacobo Bielak , George Biros , Ioannis Epanomeritakis , Antonio Fernandez , Omar Ghattas , Eui Joong Kim , Julio Lopez , David O'Hallaron , Tiankai Tu , John Urbanic, High Resolution Forward And Inverse Earthquake Modeling on Terascale Computers, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.52, November 15-21, 2003
• 3: W. K. Anderson , W. D. Gropp , D. K. Kaushik , D. E. Keyes , B. F. Smith, Achieving high sustained performance in an unstructured mesh CFD application, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.69-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331600]
• 4: Satish Balay, Kris Buschelman, William D. Gropp, Dinesh Kaushik, Matt Knepley, Lois Curfman McInnes, Barry F. Smith, and Hong Zhang. PETSc home page, 2001. www.mcs.anl.gov/petsc.
• 5: Gregory T. Balls , Scott B. Baden , Phillip Colella, SCALLOP: A Highly Scalable Parallel Poisson Solver in Three Dimensions, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.23, November 15-21, 2003
• 6: R. Becker and M. Braack. Multigrid techniques for finite elements on locally refined meshes. Numerical Linear Algebra with applications, 7:363--379, 2000.
• 7: B Bergen , F. Hulsemann , U. Rude, Is 1.7 x 10^10 Unknowns the Largest Finite Element System that Can Be Solved Today?, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.5, November 12-18, 2005 [doi>10.1109/SC.2005.38]
• 8: Marshall W. Bern, David Eppstein, and Shang-Hua Teng. Parallel construction of quadtrees and quality triangulations. International Journal of Computational Geometry and Applications, 9(6):517--532, 1999.
• 9: M. Bittencourt and R. Feij'oo. Non-nested multigrid methods in finite element linear structural analysis. In Virtual Proceedings of the 8th Copper Mountain Conference on Multigrid Methods (MGNET), 1997.
• 10: Hans-Joachim Bungartz, Miriam Mehl, and Tobias Weinzierl. A parallel adaptive cartesian pde solver using space-filling curves. In E. Wolfgang Nagel, V. Wolfgang Walter, and Wolfgang Lehner, editors, Euro-Par 2006, Parallel Processing, 12th International Euro-Par Conference, volume 4128 of LNCS, pages 1064--1074, Berlin Heidelberg, 2006. Springer-Verlag.
• 11: Paul M. Campbell, Karen D. Devine, Joseph E. Flaherty, Luis G. Gervasio, and James D. Teresco. Dynamic octree load balancing using space-filling curves. Technical Report CS-03-01, Williams College Department of Computer Science, 2003.
• 12: Edmond Chow, Robert D. Falgout, Jonathan J. Hu, Raymond S. Tuminaro, and Ulrike M. Yang. A survey of parallelization techniques for multigrid solvers. In Michael A. Heroux, Padma Raghavan, and Horst D. Simon, editors, Parallel Processing for Scientific Computing, pages 179--195. Cambridge University Press, 2006.
• 13: William M. Deen. Analysis of transport phenomena. Topics in Chemical Engineering. Oxford University Press, New York, 1998.
• 14: L. F. Demkowicz, J. T. Oden, and W. Rachowicz. Toward a universal hp adaptive finite element strategy part 1: Constrained approximation and data structure. Computer Methods in Applied Mechanics and Engineering, 77:79--112, 1989.
• 15: R. D. Falgout, J. E. Jones, and U. M. Yang. The design and implementation of Hypre, a library of parallel high performance preconditioners. In A. M. Bruaset and A. Tveito, editors, Numerical Solution of Partial Differential Equations on Parallel Computers, volume 51, pages 267--294. Springer-Verlag, 2006.
• 16: Robert D. Falgout, An Introduction to Algebraic Multigrid, Computing in Science and Engineering, v.8 n.6, p.24-33, November 2006 [doi>10.1109/MCSE.2006.105]
• 17: D. M. Greaves and A. G. L. Borthwick. Hierarchical tree-based finite element mesh generation. International Journal for Numerical Methods in Engineering, 45(4):447--471, 1999.
• 18: M. Griebel and G. Zumbusch. Parallel multigrid in an adaptive PDE solver based on hashing. In E. H. D'Hollander, G. R. Joubert, F. J. Peters, and U. Trottenberg, editors. Parallel Computing: Fundamentals, Applications and New Directions, Proceedings of the Conference ParCo '97, 19--22 September 1997, Bonn, Germany, volume 12, pages 589--600, Amsterdam, 1998. Elsevier, North-Holland.
• 19: William D. Gropp , Dinesh K. Kaushik , David E. Keyes , Barry Smith, Performance modeling and tuning of an unstructured mesh CFD application, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.34-es, November 04-10, 2000, Dallas, Texas, United States
• 20: Frank Gu¨nther , Miriam Mehl , Markus Po¨gl , Christoph Zenger, A Cache-Aware Algorithm for PDEs on Hierarchical Data Structures Based on Space-Filling Curves, SIAM Journal on Scientific Computing, v.28 n.5, p.1634-1650, September 2006 [doi>10.1137/040604078]
• 21: Morton E. Gurtin. An introduction to continuum mechanics, volume 158 of Mathematics in Science and Engineering. Academic Press, San Diego, 2003.
• 22: Van Emden Henson , Ulrike Meier Yang, BoomerAMG: a parallel algebraic multigrid solver and preconditioner, Applied Numerical Mathematics, v.41 n.1, p.155-177, April 2002 [doi>10.1016/S0168-9274(01)00115-5]
• 23: Frank Hulsemann, Markus Kowarschik, Marcus Mohr, and Ulrich Rude. Parallel geometric multigrid. In Are M. Bruaset and Aslka Tveito, editors, Numerical Solution of Partial Differential Equations on Parallel Computers, pages 165--208. Birkauser, 2006.
• 24: A. C. Jones and P. K. Jimack. An adaptive multigrid tool for elliptic and parabolic systems. International Journal for Numerical Methods in Fluids, 47:1123--1128, 2005.
• 25: Xiaoye S. Li , James W. Demmel, SuperLU_DIST: A scalable distributed-memory sparse direct solver for unsymmetric linear systems, ACM Transactions on Mathematical Software (TOMS), v.29 n.2, p.110-140, June 2003 [doi>10.1145/779359.779361]
• 26: Dimitri J. Mavriplis , Michael J. Aftosmis , Marsha Berger, High Resolution Aerospace Applications using the NASA Columbia Supercomputer, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.61, November 12-18, 2005 [doi>10.1109/SC.2005.32]
• 27: Miriam Mehl. Cache-optimal data-structures for hierarchical methods on adaptively refined space-partitioning grids, September 2006.
• 28: Miriam Mehl, Tobias Weinzierl, and Christoph Zenger. A cache-oblivious self-adaptive full multigrid method. Numerical Linear Algebra with Applications, 13(2--3):275--291, 2006.
• 29: NCSA. Abe's system architecture. ncsa.uiuc.edu/UserInfo/Resources/Hardware/Intel64Cluster.
• 30: Stéphane Popinet, Gerris: a tree-based adaptive solver for the incompressible Euler equations in complex geometries, Journal of Computational Physics, v.190 n.2, p.572-600, 20 September 2003 [doi>10.1016/S0021-9991(03)00298-5]
• 31: PSC. Bigben's system architecture, www.psc.edu/machines/cray/xt3.
• 32: Rahul Sampath and George Biros. A parallel geometric multigrid method for finite elements on octree meshes. Technical report, Georgia Institute of Technology, 2008. Submitted for publication.
• 33: Rahul Sampath, Hari Sundar, Santi S. Adavani, Ilya Lashuk, and George Biros. Dendro home page, 2008. www.cc.gatech.edu/csela/dendro.
• 34: Hari Sundar , Rahul S. Sampath , Santi S. Adavani , Christos Davatzikos , George Biros, Low-constant parallel algorithms for finite element simulations using linear octrees, Proceedings of the 2007 ACM/IEEE conference on Supercomputing, November 10-16, 2007, Reno, Nevada [doi>10.1145/1362622.1362656]
• 35: Hari Sundar , Rahul S. Sampath , George Biros, Bottom-Up Construction and 2:1 Balance Refinement of Linear Octrees in Parallel, SIAM Journal on Scientific Computing, v.30 n.5, p.2675-2708, June 2008 [doi>10.1137/070681727]
• 36: TACC. Ranger's system architecture. www.tacc.utexas.edu/resources/hpcsystems.
• 37: Ulrich Trottenberg , Anton Schuller, Multigrid, Academic Press, Inc., Orlando, FL, 2000
• 38: TIANKAI TU , DAVID R. O'HALLARON , OMAR GHATTAS, Scalable Parallel Octree Meshing for TeraScale Applications, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.4, November 12-18, 2005 [doi>10.1109/SC.2005.61]
• 39: Weigang Wang, Special Bilinear Quadrilateral Elements For Locally Refined Finite Element Grids, SIAM Journal on Scientific Computing, v.22 n.6, p.2029-2050, 2000 [doi>10.1137/S1064827599358911]
• 40: Brian S. White , Sally A. McKee , Bronis R. de Supinski , Brian Miller , Daniel Quinlan , Martin Schulz, Improving the computational intensity of unstructured mesh applications, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088195]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Multigrid and multilevel methods

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance