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.