Towards Exascale Application Mapping - An algorithmic framework for load balancing on non-uniform, massively parallel machines

许多用于大规模并行计算机体系结构的最新应用程序都有一个缺点，即它们的通信成本与处理元素（pe）的数量不成比例地增长。由于pe数量的稳步增加，这个问题将在未来加剧。特别是，对新兴百亿亿级架构的投资可能无法充分发挥其潜力。因此，提出的研究项目旨在开发新方法，以显着降低大规模并行NUMA架构中重要应用程序类的通信成本。通常，通过所谓的应用程序图对通信和/或数据依赖性进行建模。为了以负载均衡和通信优化的方式将进程和/或数据分配给pe，应用程序图被适当地划分为子图，子图被映射到pe上。当前用于这种形式的分区和映射的并行工具不能充分扩展，或者在质量上有所妥协。提议的项目旨在显著改善可伸缩性和质量之间的权衡，并以几个因素为目标加速典型的通信绑定应用程序。该研究统一了潜在动态应用图的划分和映射。为此，我们利用典型非统一架构的图论特性来建模通信成本。为了优化通信成本，我们采用了多层框架，该框架已被证明在相关环境中非常有效。与通常的做法相反，在我们统一的方法中开发的算法将在多层框架的所有阶段优化应用程序的通信成本。在多层图划分和过程映射中使用的许多算法中，我们选择了两大类作为起点：(i)严格局部组合优化方法，（ii）更全局的基于扩散的方法。由于我们之前的工作，我们在这两个方面都有专长。严格的局部优化方法是短视的，并且通常不能很好地并行化。尽管全局优化方法具有更好的可伸缩性，但通常代价高昂。因此，我们希望将这两个类最理想的特性组合并扩展到“半局部”优化方法中。我们期望这种杂交能够克服上面描述的问题，也就是说，为非常大规模的并行机器提供高质量的映射。我们将把我们的新方法集成到我们外部合作伙伴的已建立的软件库中。这些库是免费的，并且对社区永久开放，因此促进了我们对现实世界前沿模拟代码的贡献的直接应用。

Many state-of-the-art applications for massively parallel computer architectures have the drawback that their communication costs grow disproportionately with respect to the number of processing elements (PEs). This problem will exacerbate in the future due to steadily increasing numbers of PEs. In particular, investments in emerging exascale architectures may not pay off to their full potential. Consequently, the proposed research project aims at developing new methods for significantly reducing the communication costs of important application classes for massively parallel NUMA architectures.Typically, one models communication and/or data dependencies by a so-called application graph. In order to assign processes and/or data to PEs in a load-balanced and communication-optimized manner, the application graph is suitably partitioned into subgraphs, and the latter are mapped onto the PEs. Current parallel tools for this form of partitioning and mapping do not scale sufficiently or compromise on quality. The proposed project aims at significantly improving the trade-off between scalability and quality, and targets an acceleration of typical communication-boundapplications by several factors.The proposed research unifies the partitioning and mapping of a potentially dynamic application graph. To this end, we model communication costs by exploiting graph-theoretical properties of typical non-uniform architectures. For the optimization of communication costs we employ the multilevel framework, which has proven extremely effective in related contexts. In contrast to common practice, the algorithms to be developed within our unified approach will optimize an application's communication costs in all phases of of the multilevel framework.Among the many algorithms that are used in the context of multilevel graph partitioning and process mapping, we have selected two main classes as a starting point: (i) strictly local combinatorial optimization methods, and (ii) more global diffusion-based methods. Due to our previous work, we have expertise in both classes. Strictly local optimization methods are myopic and most often do not parallelize well. Global optimization methods, in spite of better scalability, are usually prohibitively expensive. Consequently, we want to combine and extend the most desirable features of both classes into "semi-local" optimization methods. We expect this hybridization to overcome the problems depicted above, that is, to provide high-quality mappings for, and on, very large-scale parallel machines.We will integrate our new methods into the established software libraries of our external partner. The libraries are free and permanently available to the community, hence fostering immediate application of our contributions to real-world, frontier simulation codes.