OAC Core: Small: Architecture and Network-aware Partitioning Algorithms for Scalable PDE Solvers

从研究引力波到设计气动汽车，求解大规模偏微分方程组(PDE)在科学和工程中很常见。考虑到这些问题的规模，解决这样的偏微分方程组需要超级计算资源。最新的超级计算体系结构不同于上一代领导力级别的体系结构，并且具有机器内部和跨机器的高度多样性的特点。这种多样性和异构性使得在不同的计算资源之间有效地分配工作，即划分数据或任务变得极其困难。由于建造领导力级别机器的主要目标是进一步的科学发现和国家繁荣，因此新旧应用程序都必须能够扩展和充分利用这些机器的潜力。该项目开发了新的数据和任务划分算法，该算法考虑了现代超级计算机的体系结构特征，以实现对当前和未来计算体系结构的高效和可扩展的利用。现有的数据和任务划分方案在划分时不显式地考虑底层体系结构拓扑，或者在算法和代码设计期间间接地进行。忽略拓扑会导致可扩展性和性能的损失，而将负担转移到算法/代码设计增加了开发成本和复杂性，并降低了可移植性。虽然针对并行化的数据和任务分区以及将分区映射到进程的研究由来已久，但它们并未被视为一个组合问题。这在很大程度上是由于集群计算体系结构中存在的简单结构和对称性。十年前没有显著影响性能和可伸缩性的效率低下，现在开始阻碍可伸缩性，从而阻碍科学发现。这个项目是确保科学发现不会因为将代码移植到新体系结构的困难而受到阻碍的第一步。该项目开发了新的基于图形和空间填充曲线的分区算法，这些算法能够感知体系结构拓扑，并能够自动生成数据/任务分区和映射，以解决当前方案存在的问题。作为该提案的一部分开发的算法和软件将产生广泛的影响，通过提高传统应用程序的性能和可扩展性，降低开发成本并提高新应用程序的可移植性，以便在从简单的共享内存体系结构到最大的异类集群的系统上高效运行。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Solving large-scale partial differential equations (PDE) is common in science and engineering, from studying gravitational waves to designing aerodynamic cars. Given the scale of these problems, solving such PDEs requires supercomputing resources. The latest supercomputing architectures are different from the previous generation of leadership class architectures and and are characterized by high levels of diversity within and across machines. Such diversity and heterogeneity makes it extremely difficult to effectively distribute work, i.e., partition the data or tasks, across disparate computing resources. Since the primary objective of building leadership class machines is to further scientific discovery and national prosperity, it is essential that applications, old and new, are able to scale and utilize these machines to their full potential. This project develops novel data and task partitioning algorithms that factor in the architectural characteristics of modern supercomputers to enable efficient and scalable utilization of current and future computing architectures.Existing data and task partitioning schemes do not explicitly consider the underlying architectural topology while partitioning or is done indirectly during the design of the algorithm and codes. Ignoring topology leads to loss of scalability and performance, while shifting the burden to algorithm/code design increases the development costs and complexity, and decreases portability. While data and task partitioning for parallelization, along with mapping the partitions to processes, have been studied for a long time, they have not been considered as a combined problem. To a large extent this was due to the simple structures and symmetry that existed in cluster computing architectures. Inefficiencies that did not significantly impact performance and scalability ten years ago are starting to inhibit scalability and thereby scientific discovery. This project is a first step in ensuring that scientific discovery is not hampered as a result of the difficulty in porting codes to new architectures. This project develops new graph and space-filling-curve-based partitioning algorithms that are aware of the architectural topology and are able to automatically generate data/task partitions and mappings to address problems with current schemes. The algorithms and software developed as part of this proposal will have wide-ranging impact, by improving the performance and scalability of legacy applications and reducing the development cost and improving the portability of new applications, to run efficiently on systems ranging from simple shared memory architectures to the largest heterogeneous clusters.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.