Representation-transparent matrix algorithms with scalable performance

ABSTRACT

Positive results from new object-oriented tools for scientific programming are reported. Using template classes, abstractions of matrix representations are available that subsume conventional row-major, column-major, either Z- or И-Morton-order, as well as block-wise combinations of these. Moreover, the design of the Matrix Template Library (MTL) has been independently extended to provide recursators, to support block-recursive algorithms, supplementing MTL's iterators. Data types modeling both concepts enable the programmer to implement both iterative and recursive algorithms (or even both) on all of the aforementioned matrix representations at once for a wide family of important scientific operations.

We illustrate the unrestricted applicability of our matrix-recursator on matrix multiplication. The same generic block-recursive function, unaltered, is instantiated on different triplets of matrix types. Within a base block, either a library multiplication or a user-provided, platform-specific code provides excellent performance. We achieve 77% of peak-performance using hand-tuned base cases without explicit prefetching. This excellent performance becomes available over a wide family of matrix representations from a single program. The techniques generalize to other applications in linear algebra.

REFERENCES

• 1: Michael D. Adams , David S. Wise, Fast additions on masked integers, ACM SIGPLAN Notices, v.41 n.5, May 2006 [doi>10.1145/1149982.1149987]
• 2: Michael D. Adams , David S. Wise, Seven at one stroke: results from a cache-oblivious paradigm for scalable matrix algorithms, Proceedings of the 2006 workshop on Memory system performance and correctness, October 22-22, 2006, San Jose, California [doi>10.1145/1178597.1178604]
• 3: Advanced Micro Devices, Inc., Sunnyvale, CA. AMD Core Math Library (ACML), 2006. http://developer.amd.com/acml.jsp
• 4: P. Bientinesi, B. Gunter, and R. A. van de Geijn. Families of algorithms related to the inversion of a symmetric positive definite matrix. ACM Trans. Math. Softw., 2007. Accepted upon revisions. http://www.cs.utexas.edu/users/pauldj/pubs/TOMS_SPD.pdf
• 5: 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]
• 6: Siddhartha Chatterjee , Alvin R. Lebeck , Praveen K. Patnala , Mithuna Thottethodi, Recursive Array Layouts and Fast Matrix Multiplication, IEEE Transactions on Parallel and Distributed Systems, v.13 n.11, p.1105-1123, November 2002 [doi>10.1109/TPDS.2002.1058095]
• 7: J. J. Dongarra, H. W. Meuer, E. Strohmaier, and H. Simon. Top 500 supercomputer sites. http://www.top500.org, 2006.
• 8: J. J. Dongarra, C. B. Moler, J. R. Bunch, and G. W. Stewart. LINPACK Users' Guide. Society for Industrial and Applied Mathematics, Philadelphia, 1979.
• 9: Jeremy D. Frens , David S. Wise, Auto-blocking matrix-multiplication or tracking BLAS3 performance from source code, ACM SIGPLAN Notices, v.32 n.7, p.206-216, July 1997
• 10: 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
• 11: K. Goto and R. A. van de Geijn. Anatomy of high-performance matrix multiplication. Technical report, Univ. of Texas, Austin. Submittted for publication. Visited Sept. 2006. http://www.cs.utexas.edu/users/flame/pubs/GOTO_TOMS.pdf
• 12: P. Gottschling. Fundamental algebraic concepts in concept-enabled C++. Technical Report 638, Indiana University, Oct. 2006. http://www.cs.indiana.edu/cgi-bin/techreports/TRNNN.cgi?trnum=TR638
• 13: K. Patrick Lorton , David S. Wise, Analyzing block locality in Morton-order and Morton-hybrid matrices, Proceedings of the 2006 workshop on MEmory performance: DEaling with Applications, systems and architectures, p.5-12, September 16-20, 2006, Seattle, Washington [doi>10.1145/1166133.1166134]
• 14: A. Lumsdaine, J. Siek, L.-Q. Lee, and P. Gottschling. The Matrix Template Library home page. http://ww.osl.iu.edu/research/mtl, 2006.
• 15: G. M. Morton. A computer oriented geodetic data base and a new technique in file sequencing. Technical report, IBM Ltd., Ottawa, Ontario, Mar. 1966.
• 16: David R. Musser , Gilmer J. Derge , Atul Saini, STL tutorial and reference guide, second edition: C++ programming with the standard template library, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 17: Neungsoo Park , Bo Hong , Viktor K. Prasanna, Tiling, Block Data Layout, and Memory Hierarchy Performance, IEEE Transactions on Parallel and Distributed Systems, v.14 n.7, p.640-654, July 2003 [doi>10.1109/TPDS.2003.1214317]
• 18: R. Raman and D. S. Wise. Converting to and from dilated integers. Submitted for publication, Dec. 2006. http://www.cs.indiana.edu/~dswise/Arcee/castingDilated-comb.pdf
• 19: Günther Schrack, Finding neighbors of equal size in linear quadtrees and octrees in constant time, CVGIP: Image Understanding, v.55 n.3, p.221-230, May 1992 [doi>10.1016/1049-9660(92)90022-U]
• 20: Jeremy G. Siek , Andrew Lumsdaine, The Matrix Template Library: A Generic Programming Approach to High Performance Numerical Linear Algebra, Proceedings of the Second International Symposium on Computing in Object-Oriented Parallel Environments, p.59-70, December 08-11, 1998
• 21: J. Spieß. Untersuchungen des Zeitgewinns durch neue Algorithmen zur Matrix-Multiplication. Computing, 17:23--36, 1976.
• 22: A. Stepanov. The Standard Template Library --- how do you build an algorithm that is both generic and efficient? Byte Magazine, 20(10), Oct. 1995.
• 23: Jeyarajan Thiyagalingam , Olav Beckmann , Paul H. J. Kelly, Is Morton layout competitive for large two-dimensional arrays yet?: Research Articles, Concurrency and Computation: Practice & Experience, v.18 n.11, p.1509-1539, September 2006 [doi>10.1002/cpe.v18:11]
• 24: R. C. Whaley, A. Petitet, and J. J. Dongarra. Automated empirical optimization of software and the ATLAS project. Parallel Computing, 27(1--2):3--35, Jan. 2001. http://dx.doi.org/10.1016/S0167-8191(00)00087-9
• 25: David S. Wise , Jeremy D. Frens , Yuhong Gu , Gregory A. Alexander, Language support for Morton-order matrices, ACM SIGPLAN Notices, v.36 n.7, p.24-33, July 2001

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.5 Object-oriented Programming

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Software libraries
      D.2.3 Coding Tools and Techniques
          Subjects: Object-oriented programming

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Arrays
  E.2 DATA STORAGE REPRESENTATIONS

General Terms:
Design, Languages, Performance

Keywords:
Morton-order, dilated integers, doppled integers, matrix template library