ITR: A Paradigm of Parallel Programming for Morton-Ordered Matrices

我们提出了一种新的数据结构和算法的基本原理与泛型编程的生产工具的结合。他们共同承诺，可以为任何科学家提供高性能计算的工具。数据结构是矩阵(以及一般的数组)的Morton顺序表示，它同时允许行、列和象限分解。它的好处基于体系结构，在这种体系结构中，它解决了内存层次结构所有级别的局部性问题。受欢迎的算法使用分而治之的递归-一种与函数式编程相关的风格-因为它们解决了分布式和多处理的平衡调度和通信问题。泛型编程也有助于程序构造的这种更高级别的代数观点。预期的结果是一种无需显式编排内存或处理器的并行编程风格。也就是说，程序员可以使用更接近数学的高级语言来指定计算，并最终指定新的算法。我们建议开发工具和技术来将这些程序进行高效的并行实现。产品将包括新的编程风格、并行和网格计算的新效率、将旧代码带入该环境的工具、支持新一代程序的工具、对教授新一代程序员的支持，以及只有从编程的高级角度才能启发的新算法。

We propose a novel marriage of new fundamentals of data structures and algorithms with the productive tools of generic programming. Together they promise tools that could make high performance computing available to any scientist. The data structure is the Morton-order representation of matrices (and arrays in general), which admits both row, column, and quadrant decompositions. Its benefits are grounded in architecture where it solves problems of locality at all levels of a memory hierarchy. The favored algorithms use divide- and-conquer recursion-a style associated with functional programming-because they address the problems of balanced scheduling and communication of distributed and multiprocessing. Generic programming contributes, also, to this higher-level algebraic view of program construction. The anticipated result is a style for parallel programming without requiring explicit choreography either of memory or of processors. That is, the programmer can specify computations, and eventually new algorithms, with a high-level language closer to mathematics. We propose to develop the tools and the techniques to carry these programs to an efficient parallel implementation.Products will include a new programming style, new efficiencies for parallel and Grid computing, tools to carry old codes into this environment, tools to support the new generation of programs, support for teaching a new generation of programmers, and new algorithms that can only be inspired by this high-level perspective on programming.