The RISC BLAS: a blocked implementation of level 3 BLAS for RISC processors

ABSTRACT

We describe a version of the Level 3 BLAS which is designed to be efficient on RISC processors. This is an extension of previous studies by the authors and colleagues on a similar approach for efficient serial and parallel implementations on virtual-memory and shared-memory multiprocessors. All our codes are written in Fortran and use loop-unrolling, blocking, and copying to improve the performance. A blocking technique is used to express the BLAS in terms of operations involving triangular blocks and calls to the matrix-matrix multiplication kernel (GEMM). No manufacturer-supplied or assembler code is used. This blocked implementation uses the same blocking ideas as in our implementation for vector machines except that the ordering of loops is designed for efficient reuse of date held in cache and not necessarily for parallelization. All the codes are specifically tuned for RISC processors. The software also includes a tuned version of GEMM. A parameter which controls the blocking allows efficient exploitation of the memory hierarchy on the various target computers. We present results on a range of RISC-based workstations and multiprocessors: CRAY T3D, DEC 8400 5/300, HP 715/64, IBM SP2, MEIKO CS2-HA, SGI Power Challenge 10000, and SUN UltraSPARC-1 model 140. This implementation of the Level 3 BLAS is available on anonymous FTP, and we welcome input from users to improve and extend our BLAS implementation.

REFERENCES

• 1: R. C. Agarwal , F. G. Gustavson , M. Zubair, Exploiting functional parallelism of POWER2 to design high-performance numerical algorithms, IBM Journal of Research and Development, v.38 n.5, p.563-576, Sept. 1994
• 2: AMESTOY,P.R.AND DAYD~, M. J. 1993. Tuned block implementation of Level 3 BLAS for the CONVEX C220 and RISC processors. Distributed implementation of LU factorization using PVM. Tech. Rep. RT/APO/93/3 Toulouse, France.
• 3: AMESTOY,P.R.AND DUFF, I. S. 1989. Vectorization of a multiprocessor multifrontal code. Int. J. Supercomput. Appl. High Perform. Eng. 3, 3, 41-59.
• 4: AMESTOY,P.R.,DAYD~,M.J.,DUFF,I.S.,AND MOR~RE, P. 1995. Linear algebra calculations on a virtual shared memory computer. Int. J. High Speed Comput. 7, 1, 21-43.
• 5: E. Anderson , Z. Bai , C. Bischof , J. Demmel , J. Dongarra , J. Du Croz , A. Greenbaum , S. Hammarling , A. McKenney , S. Ostrouchov , D. Sorensen, LAPACK's user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 6: BELL, R. 1991. IBM RISC System/6000 NIC tuning guide for Fortran and C. Tech. Rep. GG24-3611-01, IBM International Technical Support Centers.
• 7: BERGER,P.AND DAYD~, M. J. 1991. Implementation and use of Level 3 BLAS kernels on a Transputer T800 ring network. Tech. Rep. TR/PA/91/54, CERFACS.
• 8: BODIN,F.AND SEZNEC, A. 1994. Cache organization influence on loop blocking. Tech. Rep. 803, IRISA, Rennes, France.
• 9: DAYD~,M.J.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. Supercomput. Appl. High Perform. Eng. 3,2, 40-70.
• 10: DAYD~,M.J.AND DUFF, I. S. 1995. Porting industrial codes and developing sparse linear solvers on parallel computers. Comput. Syst. Eng. 4, 5, 295-305.
• 11: DAYD~,M.J.AND DUFF, I. S. 1996. A blocked implementation of Level 3 BLAS for RISC processors. Tech. Rep. RAL-TR-96-014. Rutherford Appleton Lab., Didcot, Oxon, United Kingdom. Also ENSEEIHT-IRIT Tech. Rep. RT/APO/96/1 and CERFACS Rep. TR/PA/96/06.
• 12: DAYD~,M.J.AND DUFF, I. S. 1997. A block implementation of Level 3 BLAS for RISC processors, revised version. Tech. Rep. RT/APO/97/2, ENSEEIHT-IRIT.
• 13: Michel J. Daydé , Iain S. Duff , Antoine Petitet, A parallel block implementation of Level-3 BLAS for MIMD vector processors, ACM Transactions on Mathematical Software (TOMS), v.20 n.2, p.178-193, June 1994 [doi>10.1145/178365.174413]
• 14: J. J. Dongarra , Jermey Du Cruz , Sven Hammerling , I. S. Duff, Algorithm 679; a set of level 3 basic linear algebra subprograms: model implementation and test programs, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.18-28, March 1990 [doi>10.1145/77626.77627]
• 15: 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]
• 16: Jack J. Dongarra , Peter Mayes , Giuseppe R Brozolo, LAPPACK Working Note No. 28: The IBM RISC System/6000 and Linear Algebra Operations, University of Tennessee, Knoxville, TN, 1990
• 17: 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]
• 18: GALLIVAN, K., JALBY, W., MEIER, U., AND SAMEH, A. H. 1988. Impact of hierarchical memory systems on linear algebra algorithm design. Int. J. Supercomput. Appl. High Perform. Eng. 2, 1, 12-48.
• 19: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 20: Bo Kågström , Charles van Loan, Algorithm 784: GEMM-based level 3 BLAS: portability and optimization issues, ACM Transactions on Mathematical Software (TOMS), v.24 n.3, p.303-316, Sept. 1998 [doi>10.1145/292395.292426]
• 21: Bo Kågström , Per Ling , Charles van Loan, GEMM-based level 3 BLAS: high-performance model implementations and performance evaluation benchmark, ACM Transactions on Mathematical Software (TOMS), v.24 n.3, p.268-302, Sept. 1998 [doi>10.1145/292395.292412]
• 22: Per Ling, A set of high-performance level 3 BLAS structured and tuned for the IBM 3090 VF and implemented in Fortran 77, The Journal of Supercomputing, v.7 n.3, p.323-355, Sept. 1993 [doi>10.1007/BF01206242]
• 23: PUGLISI, C. 1993. QR Factorization of large sparse overdetermined and square matrices using the multifrontal method in a multiprocessor environment. Ph.D. Dissertation.
• 24: QRICHI ANIBA, A. 1994. Impl~mentation performante du BLAS de niveau 3 pour les processeurs RISC. Tech. Rep. Rapport 3~me Ann~e. D~partement Informatique et Math~-matiques Appliqu~es, ENSEEIHT, Toulouse, France.
• 25: SHEIKH,Q.AND LIU, J. 1989. Basic linear algebra subprogram optimization on the CRAY-2 system. CRAY Channels Spring.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

General Terms:
Algorithms, Measurement, Performance

Keywords:
RISC processors, blocking, level 3 BLAS, loop-unrolling, matrix-matrix kernels