Morton-order Matrices Deserve Compilers ’ Support

A proof of concept is offered for the uniform representation of matrices serially in Morton-order (or Z-order) representation, as well as their divide-and-conquer processing as quaternary trees. Generally, d dimensional arrays are accessed as 2 d-ary trees. This data structure is important because, at once, it relaxes serious problems of locality and latency, while the tree helps schedule multi-processing. It enables algorithms that avoid cache misses and page faults at all levels in hierarchical memory, independently of a specific runtime environment. 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