Compiler Support for Morton-order Matrices

两个限制大计算的问题在面对矩阵及其组成块的不同表示时似乎放松了。Morton(或Z)序通过越来越大的块连续地表示计算机内存中的矩阵元素。这种局部性与行-主(或列-主)顺序不同，行-主(或列-主)顺序只存储彼此相邻的同一行(列)中的元素。该项目探索了用于Morton顺序的编译器，作为高级程序语言中数组的默认表示。它开发了重新编译现有程序的技术，该代码在内部使用Morton顺序，并尊重现代的存储器层次和超标量处理器。这些将干净地接口到使用Ahnentafel索引的未来程序，该索引是Morton顺序的推广，以控制分治算法到矩阵递归的下行块。因此，它还支持并行算法的设计，该并行算法将计算分解成分离的、内存局部的过程。Morton顺序，Morton顺序，而使用它的块算法，隐含地改进了对分层内存的访问模式：从寄存器、缓存到RAM，再到交换磁盘。也就是说，Morton顺序增强了一个进程的引用局部性，同时它有助于调度相互不干扰的多个进程。

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.