Analyzing block locality in Morton-order and Morton-hybrid matrices

ABSTRACT

As the architectures of computers change, introducing more caches onto multicore chips, even more locality becomes necessary. With the bandwidth between caches and RAM now even more valuable, additional locality from new matrix representations will be important to keep multiple processors busy. The default storage representations of both C and FORTRAN, row- and column-major respectively, have fundamental deficiencies with many matrix computations. By switching the storage representation from cartesian to block indices, one is able to take better advantage of cache locality at all levels from LI to paging. This paper only changes storage representation from row-major to Morton-hybrid, and applies it to matrix multiplication. Its purpose is to show that, even with only traditional iterative algorithms, simply changing storage representation offers significant speedups.

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: M. Bader and C. Zenger. Cache oblivious matrix multiplication using an element ordering based on the Peano curve. In Parallel Processing and Applied Mathematics, volume 3911 of Lecture Notes in Comput. Sci., pages 1042--1049, Berlin, 2006.Springer. http://dx.doi.org/10.1007/11752578_126
• 3: 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]
• 4: 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]
• 5: G. C. Fox. A graphical approach to load balancing and sparse matrix-vector multiplication. In M. Schultz, editor, Numerical Algorithms for Modern Parallel Architectures, volume 13 of IMA Vol. in Math. & Appl., pages 37--61. Springer, New York, 1988.
• 6: Basilio B. Fraguela , Jia Guo , Ganesh Bikshandi , María J. Garzarán , Gheorghe Almási , José Moreira , David Padua, The Hierarchically Tiled Arrays programming approach, Proceedings of the 7th workshop on Workshop on languages, compilers, and run-time support for scalable systems, p.1-12, October 22-23, 2004, Houston, Texas [doi>10.1145/1066650.1066657]
• 7: 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
• 8: S. T. Gabriel, B. Chenoweth, K. P. Lorton, M. Carlson, and D. S. Wise. The Opie Compiler Distribution. Indiana University, Bloomington, IN, Apr. 2005. http://www.cs.indina.edu/~dswise/Opie/distribution.html
• 9: Steven T. Gabriel , David S. Wise, The Opie compiler from row-major source to Morton-ordered matrices, Proceedings of the 3rd workshop on Memory performance issues: in conjunction with the 31st international symposium on computer architecture, p.136-144, June 20-20, 2004, Munich, Germany [doi>10.1145/1054943.1054962]
• 10: Irene Gargantini, An effective way to represent quadtrees, Communications of the ACM, v.25 n.12, p.905-910, Dec 1982 [doi>10.1145/358728.358741]
• 11: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 12: K. Goto and R. van de Geijn. 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
• 13: K. Goto and R. A. van de Geijn. Anatomy of high-performance matrix multiplication. Technical report, Univ. of Texas, Austin. Submitted for publication. Visited Sept. 2006. http://www.cs.utexas.edu/users/flame/pubs/GOTO_TOMS.pdf
• 14: Innovative Computing Laboratory, Univ. of Tennessee, Knoxville, TN. Performance Application Programming Interface (PAPI), Dec. 2005. http://icl.cs.utk.edu/papi/
• 15: D. S. Johnson. A theoretician's guide to the experimental analysis of algorithms. In M. H. Goldwasser, D. S. Johnson, and C. C. McGeoch, editors, Data Structures, Near Neighbor Searches, and Methodology: 5th & 6th DIMACS Implementation Challenges, volume 59 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 215--250. Amer. Math. Soc., Providence, 2002. http://www.research.att.com/~dsj/papers.html
• 16: Scalable Parallel Matrix Multiplication on Distributed Memory Parallel Computers, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.307, May 01-05, 2000
• 17: J. Markoff. Writing the fastest code, by hand, for fun: A human computer keeps speeding up chips. The New York Times, CLV (53,412):Cl, C6, 2005 Nov. 28. http://www.nytimes.com/2005/11/28/technology/28super.html
• 18: G. M. Morton. A computer oriented geodetic data base and a new technique in file sequencing. Technical report, IBM Ltd., Ottawa, Ontario, Mar. 1966.
• 19: 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]
• 20: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 21: Joon-Sang Park , Michael Penner , Viktor K. Prasanna, Optimizing Graph Algorithms for Improved Cache Performance, IEEE Transactions on Parallel and Distributed Systems, v.15 n.9, p.769-782, September 2004 [doi>10.1109/TPDS.2004.44]
• 22: 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]
• 23: V. Valsalam and A. Skjellum. A framework for high-performance matrix multiplication based on hierarchical abstractions, algorithms and optimized low-level kernels. Concur. Comp. Prac. Exper., 14(10):805--839, 2002. http://dx.doi.org/10.1002/cpe.630
• 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: D. S. Wise, C. L. Citro, J. J. Hursey, F. Liu, and M. A. Rainey. A paradigm for parallel matrix algorithms: Scalable Cholesky. In J. C. Cunha and P. D. Medeiros, editors, Euro-Par 2005 - Parallel Processing, number 3648 in Lecture Notes in Comput. Sci., pages 687--698. Springer, Berlin, Aug. 2005. http://dx.doi.org/10.1107/11549468_76
• 26: M. Wolfe, More iteration space tiling, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.655-664, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76337]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.m Miscellaneous

  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

General Terms:
Design, Languages, Performance

Keywords:
Cholesky factorization, Morton order, quadtrees