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 个内核的小型笔记本电脑，到具有数万个内核的大型计算集群。然而，将这种巨大的计算能力转化为更好的预测和设计仍然是一个巨大的挑战。该研究计划的总体目标是创建一套创新且高效的数值算法，用于解决涉及偏微分方程（PDE）的模拟和优化问题。通过利用时间和空间上的并行性，我们的算法将能够充分利用现代的多核计算架构，因此只要有足够的处理器，大型问题就可以解决。我们研究计划的新颖之处在于它专注于时间并行化，即我们设计的算法中每个处理器在时域的不同部分工作。这与传统方法不同，传统方法中不同的处理器在空间的不同区域工作。我们将考虑两种类型的时间并行性：第一种是直接模拟，旨在根据已知的初始条件来预测系统的未来状态。尽管时间演化过程看起来完全是顺序的，但如果使用两个具有不同精度的求解器，实际上可以完成有用的并行工作；不太准确（但更便宜）的轨迹可用于快速找到粗略轨迹，而更昂贵（但更准确）的轨迹可以在不同的时间间隔并行运行以细化解决方案。在这里，我们建议以分层方式使用三个或更多求解器，以进一步增加可以并行运行的进程数量。我们还将通过结合允许同时运行多个迭代的自适应管道来提高一类时空并行算法（称为波形松弛方法）的效率。我们考虑的第二种时间并行性是偏微分方程约束下的优化问题；这里的主要障碍是前向演化控制方程与强制最优性的后向演化伴随偏微分方程之间的紧密耦合。在这里，我们提出了时间范围的分解，以获得具有相同优化结构的更小的问题。然后，我们的新算法将基于局部最优片段迭代地产生全局最优解决方案。我们还将为局部优化问题设计高效的求解器。对于非线性问题，我们将研究一种新的预处理策略以提高求解器的鲁棒性和效率。所有算法都将伴随严格的数学分析，以了解其模型问题的性能。将开发高效的实施方案，以在真正的并行机器上加速解决重要的实际问题，例如弹性和多孔介质流。我们开发的工具将使研究人员和从业者能够获得更高质量的模拟和优化结果。