Compiler Support for Morton-order Matrices

点击翻译按钮获取中文摘要

Two problems that constrain big computationsappear to relax in the face of a differentrepresentation for matrices and their constituent blocks.Morton (or Z) order represents the elementsof a matrix in computer memory consecutivelyby larger and larger blocks. This locality contrastswith row-major (or column-major) order,which stores only elements in the same row(column) close to one another.This project explores compilers for Morton order asthe default representation for arrays in higher-level programminglanguages.It develops techniques to recompile existing programsto code that uses Morton-order internallyand respects modern memory hierarchies and superscalar processors.These will interface cleanly to future programs thatuse Ahnentafel indices, a generalization of Morton order,to control divide-and-conquer algorithms to descendblocks of a matrix recursively.So, it also supports the design of parallel algorithmsthat decompose a computation into disjoint, memory-local processes.Morton order, and block algorithms that use it,implicitly improve access patternsinto hierarchical memory:from registers, through caches, to RAM, to swapping disk.That is, Morton order enhances locality of referenceof one process,while it helps to schedule multiple processesthat don't interfere with each other.