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

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

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.