Auto-blocking matrix-multiplication or tracking BLAS3 performance from source code

ABSTRACT

An elementary, machine-independent, recursive algorithm for matrix multiplication C+=A*B provides implicit blocking at every level of the memory hierarchy and tests out faster than classically optimrd code, tracking hand-coded BLAS3 routines. Proof of concept is demonstrated by racing the in-place algorithm against manufacturer's hand-tuned BLAS3 routines; it can win.The recursive code bifurcates naturally at the top level into independent block-oriented processes, that each writes to a disjoint and contiguous region of memory. Experience has shown that the indexing vastly improves the patterns of memory access at all levels of the memory hierarchy, independently of the sizes of caches or pages and without ad hoc programming. It also exposed a weakness in SGI's C compilers that merrily unroll loops for the super-scalar R8000 processor, but do not analogously unfold the base cases of the most elementary recursions. Such deficiencies might deter future programmers from using this rich class of recursive algorithms.

REFERENCES

• 1: Jennifer M. Anderson , Saman P. Amarasinghe , Monica S. Lam, Data and computation transformations for multiprocessors, ACM SIGPLAN Notices, v.30 n.8, p.166-178, Aug. 1995
• 2: Rajesh Bordawekar , Alok Choudhary , Ken Kennedy , Charles Koelbel , Michael Paleczny, A model and compilation strategy for out-of-core data parallel programs, ACM SIGPLAN Notices, v.30 n.8, p.1-10, Aug. 1995
• 3: F.W. Burton & J. G. Kollias. Comment on 'The explicit quad tree as a structure for computer graphics.' Comput. J. 26, 2 (May 1983), 188.
• 4: David Cann, Retire Fortran?: a debate rekindled, Communications of the ACM, v.35 n.8, p.81-89, Aug. 1992 [doi>10.1145/135226.135231]
• 5: 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]
• 6: Michał Cierniak , Wei Li, Unifying data and control transformations for distributed shared-memory machines, ACM SIGPLAN Notices, v.30 n.6, p.205-217, June 1995
• 7: J. Cohen & M. Roth. On the implementation of Strassen's fast multiplication algorithm. Acta Informat. 6, 4 (August 1976), 341-355.
• 8: David E. Culler , Richard M. Karp , David Patterson , Abhijit Sahay , Eunice E. Santos , Klaus Erik Schauser , Ramesh Subramonian , Thorsten von Eicken, LogP: a practical model of parallel computation, Communications of the ACM, v.39 n.11, p.78-85, Nov. 1996 [doi>10.1145/240455.240477]
• 9: 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]
• 10: 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]
• 11: Richard J. Fateman, Symbolic mathematics system evaluators (extended abstract), Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.86-94, July 24-26, 1996, Zurich, Switzerland [doi>10.1145/236869.236907]
• 12: Patrick C. Fischer , Robert L. Probert, Storage reorganization techniques for matrix computation in a paging environment, Communications of the ACM, v.22 n.7, p.405-415, July 1979 [doi>10.1145/359131.359134]
• 13: J. Frens & D. S. Wise. Matrix inversion using quadtrees implemented in GOFER. Technical Report 433, Computer Science Dept., Indiana University (May 1995).
• 14: K. A. Gallivan , R. J. Plemmons , A. H. Sameh, Parallel algorithms for dense linear algebra computations, SIAM Review, v.32 n.1, p.54-135, March 1990 [doi>10.1137/1032002]
• 15: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 16: Paul Hudak , Joseph H. Fasel, A gentle introduction to Haskell, ACM SIGPLAN Notices, v.27 n.5, p.1-52, May 1992 [doi>10.1145/130697.130698]
• 17: 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]
• 18: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 19: A. C. McKellar , E. G. Coffman, Jr., Organizing matrices and matrix operations for paged memory systems, Communications of the ACM, v.12 n.3, p.153-165, March 1969 [doi>10.1145/362875.362879]
• 20: J. Spiess. Untersuchungen des Zeitgewinns durch neue Algorithmen zur Matrix-Multiplikation. Computing 17, 1 (1976), 23-36.
• 21: V. Strassen. Gaussian elimination is not optimal. Numer. Math. 13 (1969), 354-356.
• 22: Guy Lewis Steele, Jr., Debunking the “expensive procedure call” myth or, procedure call implementations considered harmful or, LAMBDA: The Ultimate GOTO, Proceedings of the 1977 annual conference, p.153-162, January 1977 [doi>10.1145/800179.810196]
• 23: David S. Wise, Representing matrices as quadtrees for parallel processors: extended abstract, ACM SIGSAM Bulletin, v.18 n.3, p.24-25, August 1984 [doi>10.1145/1089389.1089398]
• 24: D. S. Wise. Undulant block elimination and integerpreserving matrix inversion. Sci. Comput. Programming (to appear). Technical Report 418, Computer Science Department, Indiana University (revised, August 1995).

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Arrays

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory

Keywords:
cache misses, indexing, paging, quadtrees, storage management, swapping