Fast additions on masked integers

ABSTRACT

Suppose the bits of a computer word are partitioned into d disjoint sets, each of which is used to represent one of a d-tuple of cartesian indices into d-dimensional space. Then, regardless of the partition, simple group operations and comparisons can be implemented for each index on a conventional processor in a sequence of two or three register operations.These indexings allow any blocked algorithm from linear algebra to use some non-standard matrix orderings that increase locality and enhance their performance. The underlying implementations were designed for alternating bit postitions to index Morton-ordered matrices, but they apply, as well, to any bit partitioning. A hybrid ordering of the elements of a matrix becomes possible, therefore, with row-/column-major ordering within cache-sized blocks and Morton ordering of those blocks, themselves. So, one can enjoy the temporal locality of nested blocks, as well as compiler optimizations on row- or column-major ordering in base blocks.

REFERENCES

• 1: 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.
• 2: John Backus, The history of FORTRAN I, II, and III, ACM SIGPLAN Notices, v.13 n.8, p.165-180, August 1978 [doi>10.1145/960118.808380]
• 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: 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
• 6: 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]
• 7: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 8: Heller, J. Catch-22. Simon and Schuster, New York, 1961.
• 9: Morton, G. M. A computer oriented geodetic data base and a new technique in file sequencing. Tech. rep., IBM Ltd., Ottawa, Ontario, Mar. 1966.
• 10: Alan J. Perlis, Special Feature: Epigrams on programming, ACM SIGPLAN Notices, v.17 n.9, p.7-13, September 1982 [doi>10.1145/947955.1083808]
• 11: Raman, R., and Wise, D. S. Converting to and from dilated integers. Submitted for publication, Jan. 2006.
• 12: 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]
• 13: 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

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.0 General

  E. Data
  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:
Algorithms, Performance

Keywords:
compilers, dilated integers, index arithmetic, morton order, quadtrees