This paper gathers the properties of Morton order and its mappings to other indexings, and outlines for compiler support of it. Statistics on matrix multiplication, a critical example, show how the new ordering and block algorithms achieve high flop rates and, indirectly, parallelism without low-level tuning.
Perhaps because of the early success of column-major representation with strength reduction, quadtree representation has been reinvented and redeveloped in areas far from the center that is Programming Languages. As target architectures move to multiprocessing, super-scalar pipes, and hierarchical memories, compilers must support quadtrees better, so that more programmers invent algorithms that use them to exploit the hardware.
CCS Categories and subject descriptors: E.1 [Data Structures]: Arrays; D.3.2 [Programming Languages]: Language Classifications--- concurrent, distributed and parallel languages; applicative (functional) languages; D.4.2 [Operating Systems]: Storage management---storage hierarchies; E.2 [Data Storage Representations]: contiguous representations; F.2.1 [Analysis of Algorithms and Problem Complexity]: Numerical algorithms and problems--- computations on matrices.
General Terms: Design, Performance. Additional Key Words and Phrases: caching, paging, quadtree matrices, matrix multiplication.