ITR/AP: High Performance Iterative Methods on Parallel Computers and Distributed Shared Environments

大型稀疏线性方程组和特征值问题的数值解是许多科学和工程应用的核心。在并行计算机上执行的迭代方法通常是解决这些问题的唯一方法。迭代方法的大多数并行实现都采用了将方程细粒度分配到不同处理器的方法。然而，最近的建筑和计算的进步表明，细粒度的方法可能是不够的。具体而言，高网络延迟和同步开销可能使细粒度方法不适合工作站集群（COW）和大规模并行处理器（MPP）。此外，将问题划分到大量处理器可能会导致负载不平衡和处理器空闲。越来越多地使用由异构网络组成的计算网格只会使这些问题变得更糟。实现高性能需要在并行算法和在与运行时system.This项目的实现交互的新水平的复杂性将推进高性能，并行迭代方法，通过探索算法，结合联合收割机粗和细粒度，和动态资源利用方案的艺术状态。它将在传统并行化方法的基础上构建一个新的多粒度实现级别，在预处理步骤中引入更粗的粒度。它将识别系统感知的迭代算法和算法模式，使动态负载平衡，并使用它们来利用可用的运行时系统信息。由此产生的代码将提供给社区。

The numerical solution of large, sparse systems of linear equations and eigenvalue problems is central to many scientific and engineering applications. Iterative methods executed on parallel computers often provide the only means of solving these problems. Most parallel implementations of iterative methods have adopted a fine grain allocation of equations to different processors. However, recent architectural and computational advances suggest that fine-grain methods may be inadequate. Specifically, high network latencies and synchronization overheads may make fine grain methods ill suited to clusters of workstations (COWs) and massively parallel processors (MPPs). In addition, partitioning a problem to a large number of processors may lead to load imbalances and processor idling. The increasing use of Computational Grids consisting of heterogeneous networks only makes these problems worse. Achieving high performance requires new levels of sophistication in parallel algorithms and in the interaction of the implementation with the runtime system.This project will advance the state of the art in high performance, parallel iterative methods by exploring algorithms that combine coarse and fine granularity, and dynamic resource utilization schemes. It will build a new multigrain implementation level on top of traditional parallelization methods to introduce coarser granularity during the preconditioning step. It will identify system-aware iterative algorithms and algorithmic patterns that enable dynamic load balancing, and use them to exploit available runtime system information. The resulting codes will be made available to the community.