Adaptive Strassen's matrix multiplication

ABSTRACT

Strassen's matrix multiplication (MM) has benefits with respect to any (highly tuned) implementations of MM because Strassen's reduces the total number of operations. Strassen achieved this operation reduction by replacing computationally expensive MMs with matrix additions (MAs). For architectures with simple memory hierarchies, having fewer operations directly translates into an efficient utilization of the CPU and, thus, faster execution. However, for modern architectures with complex memory hierarchies, the operations introduced by the MAs have a limited in-cache data reuse and thus poor memory-hierarchy utilization, thereby overshadowing the (improved) CPU utilization, and making Strassen's algorithm (largely) useless on its own.

In this paper, we investigate the interaction between Strassen's effective performance and the memory-hierarchy organization. We show how to exploit Strassen's full potential across different architectures. We present an easy-to-use adaptive algorithm that combines a novel implementation of Strassen's idea with the MM from automatically tuned linear algebra software (ATLAS) or GotoBLAS. An additional advantage of our algorithm is that it applies to any size and shape matrices and works equally well with row or column major layout. Our implementation consists of introducing a final step in the ATLAS/GotoBLAS-installation process that estimates whether or not we can achieve any additional speedup using our Strassen's adaptation algorithm. Then we install our codes, validate our estimates, and determine the specific performance.

We show that, by the right combination of Strassen's with ATLAS/GotoBLAS, our approach achieves up to 30%/22% speed-up versus ATLAS/GotoBLAS alone on modern high-performance single processors. We consider and present the complexity and the numerical analysis of our algorithm, and, finally, we show performance for 17 (uniprocessor) systems.

REFERENCES

• 1: David H. Bailey , King Lee , Horst D. Simon, Using Strassen's algorithm to accelerate the solution of linear systems, The Journal of Supercomputing, v.4 n.4, p.357-371, 1990 [doi>10.1007/BF00129836]
• 2: D. H. Bailey , H. R. P. Gerguson, A Strassen-Newton algorithm for high-speed parallelizable matrix inversion, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.419-424, November 12-17, 1988, Orlando, Florida, United States
• 3: Gianfranco Bilardi , Paolo D'Alberto , Alexandru Nicolau, Fractal Matrix Multiplication: A Case Study on Portability of Cache Performance, Proceedings of the 5th International Workshop on Algorithm Engineering, p.26-38, August 28-31, 2001
• 4: Richard P. Brent, Algorithms for matrix multiplication, Stanford University, Stanford, CA, 1970
• 5: R. P. Brent. Error analysis of algorithms for matrix multiplication and triangular decomposition using Winograd's identity. Numerische Mathematik, 16:145--156, 1970.
• 6: Siddhartha Chatterjee , Alvin R. Lebeck , Praveen K. Patnala , Mithuna Thottethodi, Recursive array layouts and fast parallel matrix multiplication, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.222-231, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305645]
• 7: H. Cohn, R. Kleinberg, B. Szegedy, and C. Umans. Group-theoretic algorithms for matrix multiplication, Nov 2005.
• 8: D. Coppersmith , S. Winograd, Matrix multiplication via arithmetic progressions, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.1-6, January 1987, New York, New York, United States [doi>10.1145/28395.28396]
• 9: Paolo D'Alberto , Alexandru Nicolau, Adaptive Strassen and ATLAS's DGEMM: A Fast Square-Matrix Multiply for Modern High-Performance Systems, Proceedings of the Eighth International Conference on High-Performance Computing in Asia-Pacific Region, p.45, November 30-December 03, 2005 [doi>10.1109/HPCASIA.2005.18]
• 10: P. D'Alberto and A. Nicolau. Using recursion to boost ATLAS's performance. In The Sixth International Symposium on High Performance Computing (ISHPC-VI), 2005.
• 11: J. Demmel, J. Dongarra, E. Eijkhout, E. Fuentes, E. Petitet, V. Vuduc, R. C. Whaley, and K. Yelick. Self-Adapting linear algebra algorithms and software. Proceedings of the IEEE, special issue on "Program Generation, Optimization, and Adaptation", 93(2), 2005.
• 12: J. Demmel, J. Dumitriu, O. Holtz, and R. Kleinberg. Fast matrix multiplication is stable, Mar 2006.
• 13: James W. Demmel , Nicholas J. Higham, Stability of block algorithms with fast level-3 BLAS, ACM Transactions on Mathematical Software (TOMS), v.18 n.3, p.274-291, Sept. 1992 [doi>10.1145/131766.131769]
• 14: N. Eiron, M. Rodeh, and I. Steinwarts. Matrix multiplication: a case study of algorithm engineering. In Proceedings WAE'98, Saarbrücken, Germany, Aug 1998.
• 15: Jeremy D. Frens , David S. Wise, Auto-blocking matrix-multiplication or tracking BLAS3 performance from source code, Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.206-216, June 18-21, 1997, Las Vegas, Nevada, United States
• 16: M. Frigo and S. Johnson. The design and implementation of FFTW3. Proceedings of the IEEE, special issue on "Program Generation, Optimization, and Adaptation", 93(2):216--231, 2005.
• 17: Matteo Frigo , Charles E. Leiserson , Harald Prokop , Sridhar Ramachandran, Cache-Oblivious Algorithms, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.285, October 17-18, 1999
• 18: K. Goto and R. A. van de Geijn. Anatomy of high-performance matrix multiplication. ACM Transactions on Mathematical Software.
• 19: 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]
• 20: 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]
• 21: Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2002
• 22: Steven Huss-Lederman , Elaine M. Jacobson , Anna Tsao , Thomas Turnbull , Jeremy R. Johnson, Implementation of Strassen's algorithm for matrix multiplication, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.32-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States [doi>10.1145/369028.369096]
• 23: I. Kaporin. A practical algorithm for faster matrix multiplication. Numerical Linear Algebra with Applications, 6(8):687--700, 1999. Centre for Supercomputer and Massively Parallel Applications, Computing Centre of the Russian Academy of Sciences, Vavilova 40, Moscow 117967, Russia.
• 24: Igor Kaporin, The aggregation and cancellation techniques as a practical tool for faster matrix multiplication, Theoretical Computer Science, v.315 n.2-3, p.469-510, 6 May 2004 [doi>10.1016/j.tcs.2004.01.004]
• 25: P. Knight. Fast rectangular matrix multiplication and QR-decomposition. Linear algebra and its applications, 221:69--81, 1995.
• 26: Xiaoming Li , Maria Jesus Garzaran , David Padua, Optimizing Sorting with Genetic Algorithms, Proceedings of the international symposium on Code generation and optimization, p.99-110, March 20-23, 2005 [doi>10.1109/CGO.2005.24]
• 27: V. Pan. Strassen's algorithm is not optimal: Trililnear technique of aggregating, uniting and canceling for constructing fast algorithms for matrix operations. In FOCS, pages 166--176, 1978.
• 28: Victor Pan, How can we speed up matrix multiplication?, SIAM Review, v.26 n.3, p.393-415, July 1984 [doi>10.1137/1026076]
• 29: D. Priest. Algorithms for arbitrary precision floating point arithmetic. In P. Kornerup and D. W. Matula, editors, Proceedings of the 10th IEEE Symposium on Computer Arithmetic (Arith-10), pages 132--144, Grenoble, France, 1991. IEEE Computer Society Press, Los Alamitos, CA.
• 30: M. Püschel, J. M. F. Moura, J. Johnson, D. Padua, M. Veloso, B. W. Singer, J. Xiong, F. Franchetti, A. Gačić, Y. Voronenko, K. Chen, R. W. Johnson, and N. Rizzolo. SPIRAL: Code generation for DSP transforms. Proceedings of the IEEE, special issue on "Program Generation, Optimization, and Adaptation", 93(2), 2005.
• 31: V. Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 14(3):354--356, 1969.
• 32: Mithuna Thottethodi , Siddhartha Chatterjee , Alvin R. Lebeck, Tuning Strassen's matrix multiplication for memory efficiency, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-14, November 07-13, 1998, San Jose, CA
• 33: 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

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.3 Coding Tools and Techniques
          Subjects: Top-down programming
      D.2.8 Metrics
          Subjects: Complexity measures; Performance measures

Keywords:
fast algorithms, matrix multiplications