Vectorization of a Multiprocessor Multifrontal Code

Abstract

We describe design changes that enhance the vectoriza tion of a multiprocessor version of a multifrontal code for the direct solution of large sparse sets of linear equations. These changes employ techniques used with success in full Gaussian elimination and are based on the use of matrix-vector and matrix-matrix kernels as implemented in the Level 2 and Level 3 BLAS. We illus trate the performance of the improved code by runs on the IBM 3090/VF, the ETA-10P, and the CRAY-2. Al though our experiments are principally on a single pro cessor of these machines, we briefly consider the influ ence of multiprocessing. Speedup factors of more than 11 are obtained, and the modified code performs at over 200 MFLOPS on standard structures problems on one processor of the CRAY-2.

Get full access to this article

View all access options for this article.

References

Ashcraft, C. 1987. A vector implementation of the multifrontal method for large sparse, symmetric positive definite linear systems. Report ETA-TR-51 Seattle: Boeing Computer Services , ETA Division.

Ashcraft, C. , Grimes, R.G. , Lewis, J.G. , Peyton, B.W. , and Simon, H.D. 1987. Recent progress in sparse matrix methods for large linear systems on vector supercomputers. Internal. J. Supercomput. Appl. 1:10-30.

Demmel, J.W. , Dongarra, J.J. Du Croz, J. , Greenbaum, A. , Hammarling, S. , and Sorensen, D.C. 1987. Prospectus for the development of a linear algebra library for high-performance computers. Report TM-97 Argonne, Il l.: Argonne National Laboratory, Mathematics and Computer Science Division.

Daydé, M. , and Duff, I.S. 1989. Use of Level 3 BLAS in LU factorization on the CRAY-2, the ETA-10P, and the IBM 3090/VF. Internat. J. Supercomput. Appl., 3(2):40-70.

Dongarra, J.J. , Du Croz, J. , Duff, I.S. , and Hammarling, S. 1988. A set of level 3 basic linear algebra subprograms. Report TM 88 (Revision 1). Argonne, Ill.: Argonne National Laboratory, Mathematics and Computer Science Division. Report AERE R 13297. Oxford: AERE Harwell, Computer Science and Systems Division. ACM Trans. Math. Softw. , in press.

Duff, I.S. 1986. Parallel implementation of multifrontal schemes . Parallel Comput. 3:193-204.

Duff, I.S. 1988. Multiprocessing a sparse matrix code on the Alliant FX/8. Report CSS 210. Oxford: AERE Harwell, Computer Science and Systems Division. J. Comput. Appl. Math., in press.

Duff, I.S. , Erisman, A.M. , and Reid, J.K. 1986. Direct methods for sparse matrices. London: Oxford University Press.

Duff, I.S. , Grimes, R.G. , and Lewis, J.G. 1989. Sparse matrix test problems. ACM Trans. Math. Softw., 15:1-14.

10.

Duff, I.S. , and Reid, J.K. 1983. The multifrontal solution of indefinite sparse symmetric linear systems. ACM Trans. Math. Softw. 9:302-325.

11.

Duff, I.S. , and Reid, J.K. 1984. The multifrontal solution of unsymmetric sets of linear systems. SIAM J. Sci. Statist. Comput. 5:633-641.

12.

Hockney, R.W. , 1988. CRAY-2 performance measurements. I: Simple kernels on one CPU. Report CSS 215. Oxford: AERE Harwell, Computer Science and Systems Division.

13.

Reid, J.K. 1984. TREE-SOLVE. A Fortran package for solving large sets of linear finite-element equations. Report CSS 155. Oxford: AERE Harwell, Computer Science and Systems Division.

14.

Reingold, E.M. , and Hansen, W.J. 1986. Data structures in Pascal. Boston: Little, Brown.