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.
dilated integers, Morton order, quadtrees, compilers, index arithmetic
and . Fast additions on masked integers. SIGPLAN Notices, 41(5):39–45, May 2006. ISSN 0362-1340. doi: 10.1145/1149982.1149987.
@article{adams2006additions,
author = {Adams, Michael D. and Wise, David S.},
title = {Fast additions on masked integers},
journal = {SIGPLAN Notices},
pages = {39--45},
year = {2006},
volume = {41},
number = {5},
address = {New York, NY, USA},
month = may,
publisher = {ACM},
issn = {0362-1340},
doi = {10.1145/1149982.1149987},
}