Toward parallel mathematical software for elliptic partial differential equations

ABSTRACT

Three approaches to parallelizing important components of the mathematical software package ELLPACK are considered: an explicit approach using compiler directives available only on the target machine, an automatic approach using an optimizing and parallelizing precompiler, and a two-level approach based on extensive use of a set of low level computational kernels. The focus is on shared memory architectures. Each approach to parallelization is described in detail, along with a discussion of the effort involved. Performance on a test problem, using up to sixteen processors of a Sequent Symmetry S81, is reported and discussed. Implications for the parallelization of a broad class of mathematical software are drawn.

REFERENCES

• 1: Anderson , Bai , Bischof , Demmel , Dongarra , DuCroz , Greenbaum , Hammarling , McKenney , Sorenson, LAPACK Working Note 20: A Portable Linear Algebra Library For High-Performance Computers, University of Tennessee, Knoxville, TN, 1990
• 2: Edward Anderson , Jack Dongarra, LAPACK Working Note 19: Evaluating Block Algorithm Variants in LAPACK, University of Tennessee, Knoxville, TN, 1990
• 3: BONOMO, J P., DYKSEN, W. R, AND RICE, J.R. 1986. The ELLPACK performance evaluation system. Tech. Rep. CSD-TR 569, Dept. of Computer Sciences, Purdue Umv., West Lafayette, Ind.
• 4: CHAKRABORTY, A., ALLISON, D. C. S., RIBBENS, C. J, ANn WATSON, L.T. 1989. Parallel orthogohal decompositions of rectangular matrices for curve tracking on a hypercube. In J. L Gustafson, Ed, Proceedings Fourth Conference on Hypercubes, Concurrent Computers, and Applications, ACM, New York, 651 654.
• 5: CHAKRABORTY, A., ALLISON, D. C. S., RIEBENS, C. J., AND WATSON, L.T. 1991. Note on unit tangent vector computation for homotopy curve tracking on a hypercube. Parallel Camput. } 7, 1385 1395
• 6: James Demmel , Jack Dongarra , W. Kahan, LAPACK Working Note 39: On Designing Portable High Performance Numerical Libraries, University of Tennessee, Knoxville, TN, 1991
• 7: David S. Dodson , John G. Lewis, Proposed sparse extensions to the Basic Linear Algebra Subprograms, ACM SIGNUM Newsletter, v.20 n.1, p.22-25, January 1985 [doi>10.1145/1057935.1057938]
• 8: DONGARI~% J. J, BUNCH, J R., MOLER, C B., AND STEWART, G.W. 1979 LINPACK Users Guide. SIAM, Philadelphia, Pa.
• 9: J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
• 10: Jack J. Dongarra , Jeremy Du Croz , Sven Hammarling , Richard J. Hanson, An extended set of FORTRAN basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.14 n.1, p.1-17, March 1988 [doi>10.1145/42288.42291]
• 11: DuCRoz, J., MAYES, m., AND RADICATI, G. 1990. Factorizations of band matrices usmg level 3 blas. Tech. Rep. CS-90-109, Computer Scmnce Dept., Univ of Tennessee, Knoxville.
• 12: DYKSEN, W. R., HOUSTIS, E. N., LYNCH, R. E , AND RICE, J.R. 1984. The performance of the collocatmn and galerkin methods with hermite bi-cubics SIAM d. Numer Anal. 21,695 715
• 13: D'~SEN, W. R., RIBBENS, C. J., AND RICE, J. R 1988 The performance of numerical methods for elliptic problems with mixed boundary conditions Num. Meth PDEs 4, 347 361.
• 14: HOUSTIS, E. N, RICE, J. R., CHRISOCHOIDES, N. m., KARATHANASIS, H. C., PAPACHIOU, P. N., SAMARTZIS, M. K, VAVALIS, E. A., AND WANG, K-Y. 1990. Parallel ELLPACK' A numerical simulation programming environment for parallel mired machines. Tech. Rep. CSD-TR-949, Dept. of Computer Sciences, Purdue Umv., West Lafayette, Ind.
• 15: KINCAID, D. R., OPPE, T. C., AND YOUNG, D.M. 1989. ITPACKV 2D User's Guide. Tech. Rep. CNA-232, Center for Numerical Analysis, Univ. of Texas at Austin
• 16: David R. Kincaid , John R. Respess , David M. Young , Rober R. Grimes, Algorithm 586: ITPACK 2C: A FORTRAN Package for Solving Large Sparse Linear Systems by Adaptive Accelerated Iterative Methods, ACM Transactions on Mathematical Software (TOMS), v.8 n.3, p.302-322, Sept. 1982 [doi>10.1145/356004.356009]
• 17: KUCK & ASSOCIATES. 1989. KAP/Sequent User's Guide. Champaign, {1.
• 18: C. L. Lawson , R. J. Hanson , D. R. Kincaid , F. T. Krogh, Basic Linear Algebra Subprograms for Fortran Usage, ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.308-323, Sept. 1979 [doi>10.1145/355841.355847]
• 19: MAYES, P., AND RIDICATI, G. 1989 Banded cholesky factorization using level 3 bias. Tech. Rep. ANL/MCS-TM-134, Argonne National Lab., Argonne, I1.
• 20: OPPE, T. C., AND KINCAID, D.R. 1990. Are there iterative blas? In Proceedings of the Copper Mountain Conference on Iterative Methods.
• 21: Anita Osterhaug, Guide to parallel programming on Sequent computer systems: 2nd edition, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 22: RAMDAS, M., AND K~NCAID, D.R. 1991. Parallelizing ITPACKV 2D for the Cray Y-MP. Tech. Rep. CNA-249, Center for Numerical Analysis, Univ. of Texas at Austin.
• 23: Calvin J. Ribbens, On Parallel ELLPACK for Shared Memory Machines, Virginia Polytechnic Institute & State University, Blacksburg, VA, 1990
• 24: John R. Rice , Ronald F. Boisvert, Solving elliptic problems using ELLPACK, Springer-Verlag New York, Inc., New York, NY, 1985
• 25: RICE, J. R., HOUSTIS, E. N., AND DYKSEN, W.R. 1981. A population of linear, second order, elliptic partial differential equations on rectangular domains. Math. Comput. 36, 475-484.
• 26: SKJELLUM, A., AND BALDWIN, C. 1991. The multicomputer toolbox: scalable parallel libraries for large-scale concurrent applications. Tech. Rep. UCRL-JC-109251, Lawrence Livermore National Lab.
• 27: Robert E. Strout, II , James R. McGraw , Alan E. Hindmarsh, An examination of the conversion of software to multiprocessors, Journal of Parallel and Distributed Computing, v.13 n.1, p.1-16, Sept. 1991 [doi>10.1016/0743-7315(91)90105-I]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Elliptic equations

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Portability**; Efficiency

General Terms:
Algorithms, Performance

Keywords:
ELLPACK, shared memory