Anatomy of high-performance matrix multiplication

ABSTRACT

We present the basic principles that underlie the high-performance implementation of the matrix-matrix multiplication that is part of the widely used GotoBLAS library. Design decisions are justified by successively refining a model of architectures with multilevel memories. A simple but effective algorithm for executing this operation results. Implementations on a broad selection of architectures are shown to achieve near-peak performance.

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: E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 3: Leonardo Bachega , Siddhartha Chatterjee , Kenneth A. Dockser , John A. Gunnels , Manish Gupta , Fred G. Gustavson , Christopher A. Lapkowski , Gary K. Liu , Mark P. Mendell , Charles D. Wait , T. J. Chris Ward, A High-Performance SIMD Floating Point Unit for BlueGene/L: Architecture, Compilation, and Algorithm Design, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.85-96, September 29-October 03, 2004 [doi>10.1109/PACT.2004.2]
• 4: Paolo Bientinesi , John A. Gunnels , Margaret E. Myers , Enrique S. Quintana-Ortí , Robert A. van de Geijn, The science of deriving dense linear algebra algorithms, ACM Transactions on Mathematical Software (TOMS), v.31 n.1, p.1-26, March 2005 [doi>10.1145/1055531.1055532]
• 5: Paolo Bientinesi , Brian Gunter , Robert A. van de Geijn, Families of algorithms related to the inversion of a Symmetric Positive Definite matrix, ACM Transactions on Mathematical Software (TOMS), v.35 n.1, p.1-22, July 2008 [doi>10.1145/1377603.1377606]
• 6: Paolo Bientinesi , Enrique S. Quintana-Ortí , Robert A. van de Geijn, Representing linear algebra algorithms in code: the FLAME application program interfaces, ACM Transactions on Mathematical Software (TOMS), v.31 n.1, p.27-59, March 2005 [doi>10.1145/1055531.1055533]
• 7: 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]
• 8: Goto, K. 2005. www.tacc.utexas.edu/resources/software/.
• 9: Goto, K. and van de Geijn, R. 2006. High-performance implementation of the level-3 BLAS. FLAME Working Note #20, Tech. rep. TR-2006-23, Department of Computer Sciences, The University of Texas at Austin.
• 10: Goto, K. and van de Geijn, R. A. 2002. On reducing TLB misses in matrix multiplication. Tech. rep. CS-TR-02-55, Department of Computer Sciences, The University of Texas at Austin.
• 11: Gunnels, J., Gustavson, F., Henry, G., and van de Geijn, R. A. 2005. A family of high-performance matrix multiplication algrorithms. Lecture Notes in Computer Science, vol. 3732. Springer-Verlag, 256--265.
• 12: John A. Gunnels , Fred G. Gustavson , Greg M. Henry , Robert A. van de Geijn, FLAME: Formal Linear Algebra Methods Environment, ACM Transactions on Mathematical Software (TOMS), v.27 n.4, p.422-455, December 2001 [doi>10.1145/504210.504213]
• 13: John A. Gunnels , Greg M. Henry , Robert A. van de Geijn, A Family of High-Performance Matrix Multiplication Algorithms, Proceedings of the International Conference on Computational Sciences-Part I, p.51-60, May 28-30, 2001
• 14: 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]
• 15: Tze Meng Low , Robert A. van de Geijn , Field G. Van Zee, Extracting SMP parallelism for dense linear algebra algorithms from high-level specifications, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065965]
• 16: Enrique S. Quintana , Gregorio Quintana , Xiaobai Sun , Robert vande Geijn, A Note On Parallel Matrix Inversion, SIAM Journal on Scientific Computing, v.22 n.5, p.1762-1771, 2000 [doi>10.1137/S1064827598345679]
• 17: Strazdins, P. E. 1998. Transporting distributed BLAS to the Fujitsu AP3000 and VPP-300. In Proceedings of the 8th Parallel Computing Workshop (PCW'98). 69--76.
• 18: R. Clint Whaley , Jack J. Dongarra, Automatically tuned linear algebra software, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-27, November 07-13, 1998, San Jose, CA
• 19: Whaley, R. C., Petitet, A., and Dongarra, J. J. 2001. Automated empirical optimization of software and the ATLAS project. Parall. Comput. 27, 1--2, 3--35.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency

Keywords:
Linear algebra, basic linear algebra subprogrms, matrix multiplication