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

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

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.