The Opie compiler from row-major source to Morton-ordered matrices

ABSTRACT

The Opie Project aims to develop a compiler to transform C codes written for row-major matrix representation into equivalent codes for Morton-order matrix representation, and to apply its techniques to other languages. Accepting a possible reduction in performance we seek to compile a library of usable code to support future development of new algorithms better suited to Morton-ordered matrices.This paper reports the formalism behind the OPIE compiler for C, its status: now compiling several standard Level-2 and Level-3 linear algebra operations, and a demonstration of a breakthrough reflected in a huge reduction of L1, L2, TLB misses. Overall performance improves on the Intel Xeon architecture.

REFERENCES

• 1: Adamczyk, S., Spicer, J., and Vandevoorde, D. Edison Design Group: Compiler front ends for the OEM market, 2002. Visited Nov. 2002. http://www.edg.com/
• 2: Nawaaz Ahmed , Keshav Pingali, Automatic Generation of Block-Recursive Codes, Proceedings from the 6th International Euro-Par Conference on Parallel Processing, p.368-378, August 29-September 01, 2000
• 3: Allen, F. E., Cocke, J., and Kennedy, K. Reduction of operator strength. In Program Flow Analysis: Theory and Applications, S. W. Muchnick and N. D. Jones, Eds. Prentice-Hall, Englewood Cliffs, NJ, 1981, ch. 3.2, pp. 79--101.
• 4: Bjarne Stig Andersen , Jerzy Waśniewski , Fred G. Gustavson, A recursive formulation of Cholesky factorization of a matrix in packed storage, ACM Transactions on Mathematical Software (TOMS), v.27 n.2, p.214-244, June 2001 [doi>10.1145/383738.383741]
• 5: Jeff Bilmes , Krste Asanovic , Chee-Whye Chin , Jim Demmel, Optimizing matrix multiply using PHiPAC: a portable, high-performance, ANSI C coding methodology, Proceedings of the 11th international conference on Supercomputing, p.340-347, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263662]
• 6: Siddhartha Chatterjee , Vibhor V. Jain , Alvin R. Lebeck , Shyam Mundhra , Mithuna Thottethodi, Nonlinear array layouts for hierarchical memory systems, Proceedings of the 13th international conference on Supercomputing, p.444-453, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305231]
• 7: 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]
• 8: Cragon, H. G. A historical note on binary tree. SIGARCH Comput. Archit. News 18, 4 (Dec. 1990), 3.
• 9: 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]
• 10: Elmroth, E., and Gustavson, F. Applying recursion to serial and parallel QR factorization leads to better performance. IBM J. Res. Develop. 44, 4 (July 2000), 605--624. http://www.research.ibm.com/journal/rd/444/elmroth.html
• 11: Elmroth, E., Gustavson, F., Jonsson, I., and Kgström, B. Recursive blocked algorithms and hybrid data structures for dense matrix library software. SIAM Rev. 46, 1 (Mar. 2004), 3--45. http://epubs.siam.org/sam-bin/dbq/article/42869
• 12: S. I. Feldman , D. M. Gay , M. W. Maimone , N. L. Schryer, Availability of f2c—a Fortran to C converter, ACM SIGPLAN Fortran Forum, v.10 n.2, p.14-15, July 1991 [doi>10.1145/122006.122007]
• 13: 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
• 14: Jeremy D. Frens , David S. Wise, QR factorization with Morton-ordered quadtree matrices for memory re-use and parallelism, ACM SIGPLAN Notices, v.38 n.10, October 2003
• 15: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 16: Goto, K., and Van De Geijn, R. On reducing TLB misses in matrix multiplication. FLAME Working Note 9, Univ. of Texas, Austin, Nov. 2002. http://www.cs.utexas.edu/users/flame/pubs/GOTO.ps.gz
• 17: INTEL CORP. Intel Math Kernel Library. Santa Clara, CA, 2003. http://www.intel.com/software/products/mk1/
• 18: Morton, G. M. A computer oriented geodetic data base and a new technique in file sequencing. Tech. rep., IBM Ltd., Ottawa, Ontario, Mar. 1966.
• 19: J. A. Orenstein , T. H. Merrett, A class of data structures for associative searching, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588037]
• 20: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 21: 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]
• 22: Tocher, K. D. The application of automatic computers to sampling experiments. J. Roy. Statist. Soc. Ser. B 16, 1 (1954), 39--61. See pp. 53--55.
• 23: 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
• 24: David S. Wise, Ahnentafel Indexing into Morton-Ordered Arrays, or Matrix Locality for Free, Proceedings from the 6th International Euro-Par Conference on Parallel Processing, p.774-783, August 29-September 01, 2000
• 25: Wise, D. S., Citro, C., and Rainey, M. Parallel programming with Morton-ordered matrices. In preparation, 2003.
• 26: 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.3 PROGRAMMING LANGUAGES
      D.3.4 Processors

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

  E. Data
  E.1 DATA STRUCTURES
  E.2 DATA STORAGE REPRESENTATIONS

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

General Terms:
Design, Languages, Performance

Keywords:
cache, paging, quadtrees, scientific computing