SI2-SSE: Fast Dynamic Load Balancing Tools for Extreme Scale Systems

大规模并行计算与可扩展的模拟工作流相结合，可以可靠地对感兴趣的系统进行建模，这是科学家、工程师和其他从业者继续寻求解决科学发现、工程设计和医疗方面的进步的核心。然而，为了发挥它们的潜力，这些方法必须能够在执行数百万个进程的大规模并行计算机上高效运行和扩展。要实现数百万个并行进程的目标，需要新的方法，在这些方法中，计算工作量非常平衡，处理器之间的通信开销最小。在现实的模拟工作流中，获得这样的并行性能是非常复杂的，其中模型及其离散的计算机表示必须发展以确保模拟的可靠性，或者考虑到不断变化的输入流。为了满足利用受控通信实现工作量平衡的需要，已经并将继续开发称为负载平衡程序的各种算法和相关软件。为了有效地执行工作负载演变的模拟工作流，必须在模拟中的多个点动态应用负载平衡过程。当前的负载平衡技术在作为动态负载平衡过程应用于非常大量的计算核心(例如，大于100,000个核心)时显示出两个缺陷：它们成为总并行计算的主要部分(在某些情况下永远不会在分配内完成)，并且它们不能为必须基于多个准则平衡的模拟步骤保持良好的负载平衡。在改进自适应非结构网格应用的动态负载平衡方法的最初努力的基础上，拟议的研究的目标是开发快速的多准则动态负载平衡方法，该方法能够快速地产生良好的平衡计算，并且具有良好的通信控制，用于广泛的应用。要开发的动态负载平衡过程的一个重要特征是将图形一般化，以考虑多种类型的计算实体和交互。支持多个实体类型的最初想法来自于平衡必须考虑多阶网格实体的有限元计算。这些概念将被提炼和概括，以支持多个应用领域。另一项开发将是快速混合动态负载平衡方法，它是“几何”、标准图和多准则图方法的组合，其中各个方法可以在更局部的级别(例如在节点级别)全局执行。将要开发的动态负载平衡方法将在三个应用中进行演示，在这些应用中，工作负载及其分布随着模拟的进行而变化。这些应用将是自适应网格模拟、自适应多尺度建模和大规模无尺度图。这些应用程序将在可用的大规模并行计算机上进行，其中将演示100万个核心的示例。要开发的动态负载平衡方法的一个目标是实现可伸缩性，并通过受控的数据移动来实现这一点，以便所使用的挂钟时间和能量大大少于同等精度的非自适应计算所需的时间和能量。由该项目产生的软件将作为开放源码组件提供。这些发展，再加上支持用户将其应用于开发新的模拟工具的努力，将对许多研究界产生影响。根据过去和现在的努力，私人投资促进机构充分预计，该项目开发的技术也将整合到未来的工业软件系统中。

Massively parallel computing combined with scalable simulation workflows that can reliably model systems of interest are central to the continued quest of scientists, engineers, and other practitioners to address advances in scientific discovery, engineering design, and medical treatment. However, to meet their potential, these methods must be able to operate efficiently and scale on massively parallel computers executing millions of processes. Reaching the goal of millions of parallel processes requires new methods in which the computational workload is extremely well balanced and interprocessor communications overheads are minimized. Attaining such parallel performance is greatly complicated in realistic simulation workflows where the models and their discrete computer representation must evolve to ensure simulation reliability, or to account for changing input streams. To address the need to obtain workload balance with controlled communications, various algorithms and associated software, referred to as load balancing procedures, have been, and continue to be, developed. To be effective in the execution of simulation workflows in which the workload evolves, the load balancing procedures must be applied dynamically at multiple points in the simulation. Current load balancing techniques demonstrate two deficiencies when applied as dynamic load balancing procedures at very large numbers of compute cores (e.g., greater than 100,000 cores): They become a major fraction of the total parallel computation (in some cases never finishing within an allocation) and they do not maintain good load balance for simulation steps that must balance based on multiple criteria. Building on initial efforts to improve dynamic load balancing methods for adaptive unstructured mesh applications, the goal of the proposed research is to develop fast multicriteria dynamic load balancing methods that are capable of quickly producing well balanced computations, with well controlled communications, for a wide variety of applications. An important characteristic of the dynamic load balancing procedures to be developed is generalizing the graph to account for multiple types of computational entities and interactions. The initial ideas for supporting multiple entity types came from consideration balancing finite element calculations that must consider multiple orders of mesh entities. These concepts will be refined and generalized to support multiple applications areas. An additional development will be fast hybrid dynamic load balancing methods that are combinations of "geometric", standard graph, and multicriteria graph methods in which the individual methods can be executed globally of at a more local level (such as at the node level). The dynamic load balancing method to be developed will be demonstrated on three applications in which the workload, and its distribution, is changing as the simulation proceeds. The applications will be adaptive mesh simulations, adaptive multiscale modeling, and massive scale free graphs. These applications will be carried out on available massively parallel computers where examples on 1 million cores will be demonstrated. A goal of the dynamic load balancing methods to be developed will be to attain scalability, and do so with controlled data movement such that the wall clock time and energy used is substantially less than that required for an equivalent accuracy non-adaptive calculation.The software produced by this project will be made available as open source components. These developments coupled with efforts to support users in applying them in the development of new simulation tools will impact many research communities. Based on past and present efforts, the PIs fully expect that technologies developed in this project will also be integrated into future industrial software systems.