Space-time parallel algorithms for large scale simulation and optimization problems governed by partial differential equations

用于偏微分方程控制的大规模模拟和优化问题的时空并行算法

• 批准号: RGPIN-2021-02595
• 负责人: Kwok, WingHongFelix
• 金额: $ 1.31万
• 依托单位: Université Laval
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=759465
• 关键词: Space; time; parallel; algorithms; large

Parallel computers are becoming increasingly ubiquitous, from small laptops with 4-24 cores, to massive computing clusters with tens of thousands of cores. To translate this immense computing power into better predictions and designs, however, remains a great challenge. The overall goal of this research program is to create a set of innovative and efficient numerical algorithms for solving simulation and optimization problems involving partial differential equations (PDEs). By exploiting parallelism both in time and in space, our algorithms will be able to fully utilize modern, many-core computing architectures, so that large problems remain tractable as long as there are enough processors. The novelty of our research program is its focus on parallelization in time, i.e., we design algorithms where each processor works on a different part of the time domain. This is unlike classical approaches, where different processors work on different regions in space. We will consider two types of parallelism in time: the first one is for direct simulation, where one seeks to predict the future state of a system based on known initial conditions. Although the time evolution process appears completely sequential, useful parallel work can in fact be done if one resorts to two solvers with different accuracies; the less accurate (but cheaper) one can be used to find the rough trajectory quickly, while the more expensive (but more accurate) one can be run in parallel on different time intervals to refine the solution. Here, we propose using three or more solvers in a hierarchical fashion to further increase the number of processes that can be run in parallel. We will also improve the efficiency of a class of space-time parallel algorithms, known as waveform relaxation methods, by incorporating an adaptive pipeline that allows multiple iterations to be run at the same time. The second type of parallelism in time we consider is for optimization problems under PDE constraints; the main hurdle here is the tight coupling between the forward-evolving governing equation, and the backward-evolving adjoint PDE that enforces optimality. Here, we propose a decomposition of the time horizon to obtain smaller problems with the same optimization structure. Our new algorithms will then produce the globally optimal solution iteratively, based on locally optimal pieces. We will also design efficient solvers for local optimization problems. For nonlinear problems, we will investigate a new preconditioning strategy to increase solver robustness and efficiency. All algorithms will be accompanied by rigorous mathematical analysis to understand their performance for model problems. Efficient implementations will be developed to deliver speedup on real parallel machines for important practical problems, such as elasticity and porous media flow. The tools we develop will enable researchers and practitioners to obtain higher quality simulations and optimization results.

从具有4-24个核心的小笔记本电脑到拥有数万核的大规模计算簇，平行计算机变得越来越无处不在。但是，将这种巨大的计算能力转化为更好的预测和设计，仍然是一个巨大的挑战。该研究计划的总体目标是创建一组创新和有效的数值算法，以解决涉及偏微分方程（PDES）的模拟和优化问题。通过在时间和太空中利用并行性，我们的算法将能够充分利用现代的，多核的计算体系结构，因此，只要有足够的处理器，大问题仍然可以解决。我们的研究计划的新颖性是它的重点是时间平行化，即我们设计算法，每个处理器在时域的不同部分都可以工作。这与古典方法不同，在古典方法中，不同的处理器在空间的不同区域工作。我们将在时间上考虑两种类型的并行性：第一种是用于直接模拟，其中人们试图根据已知的初始条件来预测系统的未来状态。尽管时间演化过程似乎完全顺序，但如果一个人求助于具有不同精度的两个求解器，则实际上可以进行有用的并行工作。可以使用较少准确的（但便宜）快速找到粗糙的轨迹，而较昂贵（但更准确）的轨迹可以在不同的时间间隔并行运行以完善溶液。在这里，我们建议以层次结构的方式使用三个或更多求解器，以进一步增加可以并行运行的过程数量。我们还将通过合并一种自适应管道，允许同时运行多个迭代，提高一类时空平行算法（称为波形松弛方法）的效率。我们认为的第二种平行性是在PDE约束下进行优化问题。这里的主要障碍是向前发展的控制方程与实施最佳性的向后发展的伴随PDE之间的紧密耦合。在这里，我们提出了时间范围的分解，以获得具有相同优化结构的较小问题。然后，我们的新算法将基于本地最佳零件产生全球最佳解决方案。我们还将设计有效的求解器，以解决本地优化问题。对于非线性问题，我们将研究一种新的预处理策略，以提高求解器的鲁棒性和效率。所有算法都将伴随严格的数学分析，以了解其模型问题的性能。将开发有效的实现，以在实际平行机器上为重要的实践问题（例如弹性和多孔媒体流动）提供加速。我们开发的工具将使研究人员和从业人员获得更高质量的模拟和优化结果。