%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 }