Low-constant parallel algorithms for finite element simulations using linear octrees

ABSTRACT

In this article we propose parallel algorithms for the construction of conforming finite-element discretization on linear octrees. Existing octree-based discretizations scale to billions of elements, but the complexity constants can be high. In our approach we use several techniques to minimize overhead: a novel bottom-up tree-construction and 2:1 balance constraint enforcement; a Golomb-Rice encoding for compression by representing the octree and element connectivity as an Uniquely Decodable Code (UDC); overlapping communication and computation; and byte alignment for cache efficiency. The cost of applying the Laplacian is comparable to that of applying it using a direct indexing regular grid discretization with the same number of elements. Our algorithm has scaled up to four billion octants on 4096 processors on a Cray XT3 at the Pittsburgh Supercomputing Center. The overall tree construction time is under a minute in contrast to previous implementations that required several minutes; the evaluation of the discretization of a variable-coefficient Laplacian takes only a few seconds.

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, Matthew G. Knepley, Lois Curfman McInnes, Barry F. Smith, and Hong Zhang. PETSc Web page, 2001. http://www.mcs.anl.gov/petsc.
• 5: R. Becker and M. Braack. Multigrid techniques for finite elements on locally refined meshes. Numerical Linear Algebra with applications, 7:363--379, 2000.
• 6: 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]
• 7: 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.
• 8: 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.
• 9: S. W. Golomb. Run-length encodings. IEEE Transactions on Information Theory, 12(3):399--401, 1966.
• 10: Leslie Greengard , William Gropp, A Parallel Version of the Fast Multipole Method-Invited Talk, Proceedings of the Third SIAM Conference on Parallel Processing for Scientific Computing, p.213-222, December 01-04, 1987
• 11: 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.
• 12: 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
• 13: Bhanu Hariharan , Srinivas Aluru , Balasubramaniam Shanker, A scalable parallel fast multipole method for analysis of scattering from perfect electrically conducting surfaces, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-17, November 16, 2002, Baltimore, Maryland
• 14: E. Kim, J. Bielak, O. Ghattas, and J. Wang. Octree-based finite element method for large-scale earthquake ground motion modeling in heterogeneous basins. AGU Fall Meeting Abstracts, pages B1221+, December 2002.
• 15: Debra A. Lelewer , Daniel S. Hirschberg, Data compression, ACM Computing Surveys (CSUR), v.19 n.3, p.261-296, Sept. 1987 [doi>10.1145/45072.45074]
• 16: 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]
• 17: 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]
• 18: R. F. Rice. Some practical universal noiseless coding techniques. Technical Report JPL Publication 79--22, Jet Propulsion Laboratory, Pasadena, California, 1979.
• 19: Hari Sundar, Rahul S. Sampath, and George Biros. Bottom-up construction and 2:1 balance re nement of linear octrees in parallel. University of Pennsylvania Technical Report, MS-CIS-07-05, 2007.
• 20: Tiankai Tu and David R. O'Hallaron. Balance refinement of massive linear octree datasets. CMU Technical Report, CMU-CS-04(129), 2004.
• 21: Tiankai Tu and David R. O'Hallaron. Extracting hexahedral mesh structures from balanced linear octrees. In 13th International Meshing Roundtable, pages 191--200, Williamsburg, VA, Sandia National Laboratories, September 19--22 2004.
• 22: 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]
• 23: Tiankai Tu , Hongfeng Yu , Leonardo Ramirez-Guzman , Jacobo Bielak , Omar Ghattas , Kwan-Liu Ma , David R. O'Hallaron, From mesh generation to scientific visualization: an end-to-end approach to parallel supercomputing, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188551]
• 24: 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]
• 25: 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]
• 26: Lexing Ying , George Biros , Denis Zorin, A kernel-independent adaptive fast multipole algorithm in two and three dimensions, Journal of Computational Physics, v.196 n.2, p.591-626, 20 May 2004 [doi>10.1016/j.jcp.2003.11.021]
• 27: Lexing Ying , George Biros , Denis Zorin , Harper Langston, A New Parallel Kernel-Independent Fast Multipole Method, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.14, November 15-21, 2003