GEMM-based level 3 BLAS: high-performance model implementations and performance evaluation benchmark

ABSTRACT

The level 3 Basic Linear Algebra Subprograms (BLAS) are designed to perform various matrix multiply and triangular system solving computations. Due to the complex hardware organization of advanced computer architectures the development of optimal level 3 BLAS code is costly and time consuming. However, it is possible to develop a portable and high-performance level 3 BLAS library mainly relying on a highly optimized GEMM, the routine for the general matrix multiply and add operation. With suitable partitioning, all the other level 3 BLAS can be defined in terms of GEMM and a small amount of level 1 and level 2 computations. Our contribution is twofold. First, the model implementations in Fortran 77 of the GEMM-based level 3 BLAS are structured to reduced effectively data traffic in a memory hierarchy. Second, the GEMM-based level 3 BLAS performance evaluation benchmark is a tool for evaluating and comparing different implementations of the level 3 BLAS with the GEMM-based model implementations.

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: R. C. Agarwal , F. G. Gustavson , M. Zubair, Improving performance of linear algebra algorithms for dense matrices, using algorithmic prefetch, IBM Journal of Research and Development, v.38 n.3, p.265-275, May 1994
• 3: 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
• 4: Steve Carr , R. B. Lehoucq, Compiler blockability of dense matrix factorizations, ACM Transactions on Mathematical Software (TOMS), v.23 n.3, p.336-361, Sept. 1997 [doi>10.1145/275323.275325]
• 5: DACKLAND, K. 1995. Design issues and the performance of level 1 and level 2 kernels on Intel i860-based platforms. Report UMINF-95.xx, Department of Computing Science, Ume University, Ume , Sweden.
• 6: 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]
• 7: 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]
• 8: 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]
• 9: 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]
• 10: DONGARRA, J., MAYES, P., AND RADICATI DI BROZOLO, G. 1991. The IBM RISC System 6000 and linear algebra operations. Supercomput. 8, 4, 15-30.
• 11: Craig C. Douglas , Michael Heroux , Gordon Slishman , Roger M. Smith, GEMMW: a portable level 3 BLAS Winograd variant of Strassen's matrix-matrix multiply algorithm, Journal of Computational Physics, v.110 n.1, p.1-10, Jan. 1994 [doi>10.1006/jcph.1994.1001]
• 12: GALLIVAN, K., JALBY, W., MEIER, U., AND SAMEH, A. 1988. Impact of hierarchical memory systems on linear algebra algorithm design. Int. J. Supercomput. Appl. 2, 12-48.
• 13: GRASEMANN, H. 1989. Optimization of level 3 BLAS for SIEMENS VP systems. Tech. Rep. 38.89 (Sept.), University of Karlsruhe, Computer Center.
• 14: GREEN, M. 1994. High performance level 3 BLAS. A KSR implementation. Working Note (April), Department of Mathematics, University of Manchester, Manchester, UK.
• 15: Nicholas J. Higham, Exploiting fast matrix multiplication within the level 3 BLAS, ACM Transactions on Mathematical Software (TOMS), v.16 n.4, p.352-368, Dec. 1990 [doi>10.1145/98267.98290]
• 16: IBM. 1994. Engineering and Scientific Subroutine Library, Guide and Reference.
• 17: INTEL. 1993. Paragon Basic Math Library performance report. Technical Report. 312936- 001 (Oct.), Intel Supercomputer Division. Beaverton, Ore.
• 18: K GSTR(~M, B. AND VAN LOAN, C. 1989. GEMM-based level 3 BLAS. Technical Report CTC91TR47 (Dec.), Department of Computer Science, Cornell University.
• 19: K GSTR(~M, B., LING, P., AND VAN LOAN, C. 1991. High performance GEMM-based level 3 BLAS: Sample routines for double precision real data. In High Performance Computing II (Amsterdam, 1991). North-Holland, 269-281.
• 20: K GSTR(~M, B., LING, P., AND VAN LOAN, C. 1993. Portable high performance GEMM-based level 3 BLAS. In Parallel Processing for Scientific Computing (Philadelphia, 1993). SIAM Publications, 339-346.
• 21: K GSTR(~M, B., LING, P., AND VAN LOAN, C. 1994. GEMM-based level 3 BLAS: Algorithms for the model implementations. Report UMINF-94.13 (December), Department of Computing Science, Ume University, Ume , Sweden. Revised, December 1995.
• 22: 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]
• 23: 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]
• 24: 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]
• 25: Qasim Sheikh , Phuong Vu , Chao Yang , Michael Merchant, Implementation of the Level 2 and 3 BLAS on the CRAY Y-MP and the CRAY-2, The Journal of Supercomputing, v.5 n.4, p.291-305, Feb. 1992 [doi>10.1007/BF00127950]
• 26: STRASSEN, V. 1969. Gaussian elimination is not optimal. Numer. Math. 13, 354-356.
• 27: WINOGRAD, S. 1973. Some remarks on fast multiplication of polynomials. In Complexity of Sequential and Parallel Numerical Algorithms (New York). Academic Press, 181.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FORTRAN 77

  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.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency; Reliability and robustness; Certification and testing

General Terms:
Algorithms, Measurement, Performance

Keywords:
GEMM-based level 3 BLAS, blocked algorithms, matrix-matrix kernels, memory hierarchy, parallelization, vectorization