Use of parallel level 3 BLAS in LU factorization on three vector multiprocessors the ALLIANT FX/80, the CRAY-2, and the IBM 3090 VF

ABSTRACT

We show how to transform the B-spline curve and surface fitting problems into suffix computations of continued fractions. Then a parallel substitution scheme is introduced to compute the suffix values on a newly proposed mesh-of-unshuffle network. The derived parallel algorithm allows the curve interpolation through n points to be solved in &Ogr;(log n) time using &THgr;n/log n) processors and allows the surface interpolation through m x n points to be solved in &Ogr;(log m log n) time using &THgr; (mn/(log m log n)) processors. Both interpolation algorithms are cost-optimal for their respective problems. Besides, the surface fitting problem can be even faster solved in &Ogr;(log m + log n) time if &THgr;(mn) processors are used in the network.

REFERENCES

• 1: Christian Bischof , Charles van Loan, The WY representation for products of householder matrices, SIAM Journal on Scientific and Statistical Computing, v.8 n.1, p.2-13, January 2, 1987 [doi>10.1137/0908009]
• 2: Bischof, C., Demmel, J., Dongarra J., DuCroz J., Greertbaum, A., Hammarling S., and Soreusen, D. (1988). LAPACK Working Note #5 : Provisional Contents. Report ANL-88-38. Mathematics and Computer Science Division, Argonne National Laboratory.
• 3: Bucher, I. and Jordan, T. (1984). Linear algebra programs for use on a vector computer with a secondary solid state storage device. In Advances in Computer Methods for Partial Differential Equations, E. R. Vichnevetsky and R. Stepleman (Eds), IMACS, 546-550.
• 4: Calahan, D.A. (1986). Block-oriented, localmemory-based linear equation solution on the CRAY-2: uniprocessor algorithms. Proceedings International Conference on Parallel Processing, August 1986. IEEE Computer Society Press, 375-378.
• 5: Carnevali, P., Radicati di Brozolo, G., Robert, Y., and Sguazzero, P. (1987). Efficient FORTRAN implementation of the Gaussian elimination and Householder reduction algorithms on the IBM 3090 vector multiprocessor. Report ICE- 0012, Rome : IBM European Center for Scientific and Engineering Computing, italy.
• 6: Dayd6, M. and Duff, I.S. (1989). Use of Level 3 BLAS in LU factorization ,on the CRAY-2, the ETA 10-P, and the IBM 3090/VF. Int. J. Supercomputers Applications 3(2), 40-70.
• 7: Dayd6, M. and Duff, I.S. (1991)). Use of Level 3 BLAS in LU factorization in a multiprocessing environment on three vector multiprocessors the ALLIANT F~80, the CRAY-2, and the IBM 3090/VF. CERFACS Report (To appear).
• 8: Dekker, E. (I989). Some aspects of the CRAY.2 architecture. Report TR 89/'8, CERFACS.
• 9: 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, Mathematics and Computer Science Division, Argonne National Laboratory.
• 10: Dongarra, J.J. (1988). Performance of various computers using standard linear equations software in a Fortran environment. Report TM 23. Mathematics and Computer Science Division, Argonne National Laboratory.
• 11: 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]
• 12: 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]
• 13: Dongarra, J.J., Du Croz, J., Duff, I.S., and Hammarling, S. (1988b). A set of level 3 Basic Linear Algebra Subprograms: model implementation and test programs. Report AERE R 13298, Harwell ~tboratory. To appear in A CM Tram. Math. Softw.
• 14: Dongarra, J.J., Gustavson, F. G., and Karp, A. (1984). Implementing linear algebra algorithms for dense matrices on a vector pipeline machine. SIAM Review 26, 91-112.
• 15: Kyle Gallivam , William Jalby , Ulrike Meier, The use of BLAS3 in linear algebra on a parallel processor with a hierarchical memory, SIAM Journal on Scientific and Statistical Computing, v.8 n.6, p.1079-1084, November 1, 1987 [doi>10.1137/0908086]
• 16: Gallivan, K., jalby, W., Meier, U., and Sameh A. (1988). impact of hierarchical memory systems on linear algebra algorithm design. Int. J. Supercomputers Applications 2( 1),12-48.
• 17: IBM (1986). Engineering and Scientific Subroutine Library. Program Number: 5668-863, IBM.
• 18: Kagstrom B., and Ling, P. (1988). Level 2 and Level 3 BLAS routines for IBM 3090 VF/400 : implementations and experiences. Report UMINF 154.88, University of Umea, Sweden.
• 19: 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]
• 20: C. L. Lawson , R. J. Hanson , F. T. Krogh , D. R. Kincaid, Algorithm 539: Basic Linear Algebra Subprograms for Fortran Usage [F1], ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.324-325, Sept. 1979 [doi>10.1145/355841.355848]
• 21: Peter Mayes , Giuseppi Radicati di Brozolo, Portable and efficient factorization algorithms on the IBM 3090/VF, Proceedings of the 3rd international conference on Supercomputing, p.263-270, June 05-09, 1989, Crete, Greece [doi>10.1145/318789.318818]
• 22: Robert, Y. and Sguazzero, P. (1987). The LU decomposition algorithm and its efficient Fortran implementation on the IBM 3090 vector multiprocessor. Report ICE-0006, Rome : IBM European Center for Scientific and Engineering Computing, Italy.
• 23: Sheikh, Q., and Liu, J. (1989). Basic Linear Algebra Subprogram Optimization on the CRAY-2 System. Cray Channels, Spring 1989.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Design, Performance, Theory