Efficient parallel block algorithms for the LU factorization with partial pivoting, the Cholesky factorization, and the QR factorization transportable over a range of parallel MIMD architectures are presented. Parallel implementations of different block algorithms that utilize optimized uniprocessor level-3 BLAS are compared with corresponding routines of LAPACK (under development). Parallelism is mainly invoked implicitly in LAPACK by replacing calls to uniprocessor level-3 kernels by calls to parallel level-3 kernels and thereby maintaining portability. However, by parallelizing at the block level (explicitly) it is possible to overlap and pipeline different matrix-matrix operations and thereby gain some performance. Theoretical models give upper bounds on the best possible speedup of the explicitly and implicitly parallel block algorithms for the target machine.
Get full access to this article
View all access options for this article.
References
1.
AndersonE., BaiZ., BischofC., DemmelJ., DongarraJ., Du Croz, J., GreenbaumA., HammarlingS., McKenneyA., and SorensenD.1990. LAPACK: a portable linear algebra library for high-performance computers., Technical Report CS-90-105 (LAPACK Working Note No. 20). Knoxville: University of Tennessee.
2.
AnderssonE., and DongarraJ.1990a. Implementation guide for LAPACK. Technical Report CS-90-101 (LAPACK Working Note No. 18). Knoxville: University of Tennessee.
3.
AnderssonE., and DongarraJ.1990b. Evaluating block algorithm variants in LAPACK. In Parallel processing for scientific computing, edited by J. Dongarra, MessinaP., SorensenD., and VoigtR.. Philadelphia: SIAM Publications, pp. 3-8.
4.
BischofC.1989. Adaptive blocking in the QR factorization. J. Supercomput.3:193-208.
5.
BischofC., DemmelJ., DongarraJ., Du Croz, J., GreenbaumA., HammarlingS., McKenneyA., and SorensenD.1988. LAPACK provisional contents. Math. Comp. Sci. Report ANL-88-38 (LAPACK Working Note No. 5). Argonne, Illinois: Argonne National Laboratory.
6.
BischofC., and Van LoanC.1987. The WY representation for products of Householder matrices. SIAM J. Sci. Statist. Comput.8:s2–s13.
7.
CohenE., KingG., and BradyJ.1988. Storage hierarchies. IBM Systems J.28(1):62-76.
8.
DaydéM., and DuffI.1990. Use of level 3 BLAS in LU factorization in a multiprocessing environment on three vector multiprocessors: the Alliant FX/80, the CRAY-2, and the IBM 3090 VF. Technical Report. CERFACS.
9.
DongarraJ., Du Croz, J., HammarlingS., and HansonR.1988. An extended set of Fortran basic linear algebra subprograms. ACM Trans. Math. Software14:1-17, 18-32.
10.
DongarraJ., Du Croz, J., HammarlingS., and DuffI.1990. A set of level 3 basic linear algebra subprograms. ACM Trans. Math. Software16:1-17, 18-28.
11.
DongarraJ., DuffI., SorensenD., and Van der VorstH.1991. Solving linear systems on vector and shared memory computers. Philadelphia: SIAM Publications.
12.
DongarraJ., and SorensenD.1986. Linear algebra on high-performance computers. In High-performance computers 85, edited by U. Schendel. New York: North-Holland, pp. 3-32.
13.
ErikssonJ., JacobsonP., KågströmB., and LindströmE.1990. The CONLAB environment: algorithm design for and simulation of MIMD architectures. In Parallel processing for scientific computing, edited by J. Dongarra, MessinaP., SorensenD., and VoigtR.. Philadelphia: SIAM Publications, pp. 406-412.
14.
GallivanK., JalbyW., MeierU., and SamehA.1988. Impact of hierarchical memory systems on linear algebra algorithm design. Int. J. Supercomput. Appl.2:12-48.
15.
GallivanK., PlemmonsR., and SamehA.1990. Parallel algorithms for dense linear algebra computations. SIAM Rev.32:54-135.
16.
GolubG., and Van LoanC.1989. Matrix computations, 2nd ed. Baltimore: Johns Hopkins Press.
17.
IBM.1988. Engineering and scientific subroutine library guide and reference. SC23-0184-3.
18.
JacobsonP.1990. The CONLAB environment. Report UMINF-173.90. Umeå, Sweden: University of Umeå, Institute of Information Processing.
19.
KågströmB., and LingP.1989. Level 2 and 3 BLAS routines for IBM 3090 VF: implementation and experiences. In Vector and parallel computing, edited by J. Dongarra, DuffI., GaffneyP., and McKeeS.. Chichester, England: Ellis-Horwood, pp. 229-240.
20.
KågströmB., and Van LoanC.1989. GEMM-based level-3 BLAS. Technical Report. Ithaca, New York: Cornell University, Department of Computer Science.
21.
LawsonC., HansonR., KincaidR., and KroghF.1979. Basic linear algebra subprograms for Fortran usage. ACM Trans. Math. Software5:308-323.
22.
LingP.1990. A set of high performance level-3 BLAS structured and tuned for the IBM 3090 VF and implemented in Fortran 77. Report UMINF-179.90. Umeå, Sweden: University of Umeå, Institute of Information Processing.
23.
LiuB., and StrotherN.1988. Programming in VS Fortran on the IBM 3090 for maximum vector performance. IEEE ComputerJune (1988): 65-76.
24.
MolerC., LittleJ., and BangertS.1987. PRO-MATLAB user's guide. The MathWorks Inc.
25.
RadicatiG., RobertY., and SguazzeroP.1988. Block processing in linear algebra on the IBM 3090 vector multiprocessor. Supercomputer5(1): 15-25.
26.
SheikhQ., andLiu, J. 1990. Performance of block matrix factorization algorithms and LAPACK on CRAY Y-MP and CRAY-2. Cray Research Inc.
27.
SchreiberR., and Van LoanC.1989. A storage efficient WY representation for products of Householder transformations. SIAM J. Sci. Statist. Comput.10:53-57.
28.
ToomeyL., PlachyE., ScarboroughR., SahulkaR., ShawJ., and ShannonA.1988. IBM Parallel Fortran. IBM Systems J.27:416-435.
29.
TuckerS.1986. The IBM 3090 system: an overview. IBM Systems J.25(1):4-20.
