Pursuing scalability for hypre's conceptual interfaces

ABSTRACT

The software library hypre provides high-performance preconditioners and solvers for the solution of large, sparse linear systems on massively parallel computers as well as conceptual interfaces that allow users to access the library in the way they naturally think about their problems. These interfaces include a stencil-based structured interface (Struct); a semistructured interface (semiStruct), which is appropriate for applications that are mostly structured, for example, block structured grids, composite grids in structured adaptive mesh refinement applications, and overset grids; and a finite element interface (FEI) for unstructured problems, as well as a conventional linear-algebraic interface (IJ). It is extremely important to provide an efficient, scalable implementation of these interfaces in order to support the scalable solvers of the library, especially when using tens of thousands of processors. This article describes the data structures, parallel implementation, and resulting performance of the IJ, Struct and semiStruct interfaces. It investigates their scalability, presents successes as well as pitfalls of some of the approaches and suggests ways of dealing with them.

REFERENCES

• 1: Ashby, S. F. and Falgout, R. D. 1996. A parallel multigrid preconditioned conjugate gradient algorithm for groundwater flow simulations. Nucl. Sci. Eng. 124, 1 (Sept.), 145--159. Also available as LLNL Tech. rep. UCRL-JC-122359. Lawrence Livermore National Laboratory, Livermore, CA.
• 2: Balay, S., Buschelman, K., Eijkhout, V., Gropp, W., Kaushik, D., Knepley, M., McInnes, L. C., Smith, B., and Zhang, H. 2004. PETSc user's manual. Tech. rep. ANL-95/11-Revision 2.2.1. Argonne National Laboratory, Argonne, IL.
• 3: Balay, S., Buschelman, K., Gropp, W., Kaushik, D., Knepley, M., McInnes, L. C., Smith, B., and Zhang, H. 2001. PETSc Web page. Tech. rep. Go to http://www.mcs.anl.gov/petsc.
• 4: Peter N. Brown , Robert D. Falgout , Jim E. Jones, Semicoarsening Multigrid on Distributed Memory Machines, SIAM Journal on Scientific Computing, v.21 n.5, p.1823-1834, April 2000 [doi>10.1137/S1064827598339141]
• 5: Edmond Chow, A Priori Sparsity Patterns for Parallel Sparse Approximate Inverse Preconditioners, SIAM Journal on Scientific Computing, v.21 n.5, p.1804-1822, April 2000 [doi>10.1137/S106482759833913X]
• 6: Clay, R., Mish, K., Otero, I., Taylor, L., and Williams, A. 1999. An annotated reference guide to the finite element interface (FEI) specification: version 1.0. Tech. rep. SAND99-8229, Sandia National Laboratories, Albuquerque, NM.
• 7: Dijkstra, E. and Scholten, C. 1980. Termination detection for diffusing computations. Inform. Process. Lett. 11, 1--4.
• 8: Falgout, R., Jones, J., and Yang, U. 2003. Conceptual interfaces in hypre. Fut. Gen. Comput. Syst. To appear. Also available as LLNL Tech. rep. UCRL-JC-148957, Lawrence Livermore National Laboratory, Livermore, CA.
• 9: Robert D. Falgout , Ulrike Meier Yang, hypre: A Library of High Performance Preconditioners, Proceedings of the International Conference on Computational Science-Part III, p.632-641, April 21-24, 2002
• 10: Nissim Francez, Distributed Termination, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.1, p.42-55, Jan. 1980 [doi>10.1145/357084.357087]
• 11: 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]
• 12: Hypre. 2005. High performance preconditioners. Available online at http://www.llnl.gov/CASC/linear_solvers/.
• 13: David Hysom , Alex Pothen, Efficient parallel computation of ILU(k) preconditioners, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.29-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331561]
• 14: Jeff Matocha , Tracy Camp, A taxonomy of distributed termination detection algorithms, Journal of Systems and Software, v.43 n.3, p.207-221, Nov. 1998 [doi>10.1016/S0164-1212(98)10034-1]
• 15: Pinar, A. and Hendrickson, B. 2001. Communication support for adaptive communication. In Proceedings of the 10th SIAM Conference on Parallel Processing for Scientific Computing.
• 16: Interprocessor Communication with Limited Memory, IEEE Transactions on Parallel and Distributed Systems, v.15 n.7, p.606-616, July 2004 [doi>10.1109/TPDS.2004.22]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: User interfaces; Software libraries

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Distributed data structures

General Terms:
Algorithms, Design, Performance

Keywords:
User interfaces, parallel programming, scalability