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.
%0 Journal Article
%1 adams2006additions
%A Adams, Michael D.
%A Wise, David S.
%C New York, NY, USA
%D 2006
%I ACM
%J SIGPLAN Notices
%K 2006 Morton arithmetic compilers dilated index integers myOwn order quadtrees
%N 5
%P 39--45
%R 10.1145/1149982.1149987
%T Fast additions on masked integers
%U http://portal.acm.org/citation.cfm?id=1149982.1149987
%V 41
%X 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.
@article{adams2006additions,
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.},
added-at = {2010-07-25T13:38:09.000+0200},
address = {New York, NY, USA},
author = {Adams, Michael D. and Wise, David S.},
biburl = {https://www.bibsonomy.org/bibtex/264d16f8718adbb982fbd5f01c68f1d2a/mdmkolbe},
description = {Fast additions on masked integers},
doi = {10.1145/1149982.1149987},
interhash = {ceb090cf03cb75962394d85099d3a2fa},
intrahash = {64d16f8718adbb982fbd5f01c68f1d2a},
issn = {0362-1340},
journal = {SIGPLAN Notices},
keywords = {2006 Morton arithmetic compilers dilated index integers myOwn order quadtrees},
month = may,
number = 5,
pages = {39--45},
publisher = {ACM},
timestamp = {2010-07-25T13:38:09.000+0200},
title = {Fast additions on masked integers},
url = {http://portal.acm.org/citation.cfm?id=1149982.1149987},
volume = 41,
year = 2006
}