不连续 Galerkin 真的比连续 Galerkin 更可并行化吗?

计算科学 有限元 并行计算 不连续-galerkin
2021-12-01 06:54:21

我一直听说容易并行化是 DG 方法的优点之一,但我真的不明白为什么这些原因中的任何一个也不适用于连续 Galerkin。

4个回答

DG 方法作为一种并行方法可能受到更多关注的一个原因是,很容易看出该方法本质上是元素的局部方法。DG 方法中的耦合很弱,因为它只通过相邻的边(或 3d 中的面)发生。因此,对于三角形或四边形,DG 最多将分别与三个或四个处理器通信。而 CG 方法将包括元素角,因此元素角的化合价变得很重要。根据使用的网格生成器,这个价可以是八个处理器(可能更高)。因此,对于 CG 方法,可以认为组装时间导数的成本“更高”。这对于频谱方法尤其值得关注,其中要传达的信息量可能非常大(并且随着每个分区的大小缩小,延迟隐藏会变得更加困难)。

但是 CG 组装它的时间导数的额外成本可以通过不同的负载平衡策略来补偿。不同的网格分区策略(我最熟悉 METIS)允许用户通过各种指标来平衡负载,例如,确保每个分区具有大致相同数量的元素或限制分区之间的通信量。我觉得 DG 的学术讨论会很容易并行化的一个原因是,将问题简单地分成相等的部分可以提供非常有效的并行实现,甚至在某些情况下由于缓存效应而呈现超线性加速(参见例如Baggag 等人) .Altmann 等人。)。而 CG 可能需要更聪明的分区方法。因此,将空间离散化从 DG 更改为 CG 可能需要重新考虑如何将网格划分为子问题。

根据我多年编写 FEM 软件的经验,我认为 DG 方案比 CG 方案更适合并行化的说法是杜撰的。它经常在 DG 论文的介绍中用作 DG 方法的理由,但我从未见过有实际调查该问题的参考文献证实了它。它类似于 NSF 关于数论项目的每一个提案,都将“密码学”作为一个具有更广泛影响的领域,这一声明在这一普遍性上也从未得到证实。

事实上,我认为,除了显式时间步进方案以及可能必须反转质量矩阵的问题之外,如果研究其中任何一种涉及的通信成本,DG 方案并不比 CG 方案好或差。我的意思是从实际意义上说:当然,一个人可能需要传递更少的数据,但我认为挂钟时间的差异对于所有其他操作程序对这些数据执行的操作来说可以忽略不计。

当然,如果有人接受挑战证明我错了,我会很高兴!

就像大多数关于数值方案的一般陈述一样,答案取决于您正在查看的确切情况。首先,DG 在并行化方面的优势主要在显式时间积分方案的情况下得到回报,因为

  • DG 方案的单元局部质量矩阵(因此您不必全局应用质量矩阵的逆)
  • CPU本地工作(体积积分)与通信相关工作(边缘积分)的有利比率,特别是对于更高阶

虽然这些陈述适用于通用 DG 离散化,但真正的HPC 应用程序(例如,使用数千个处理器)需要在并行化策略方面付出更多努力才能保持良好的可扩展性。例如,本文展示了如何实现几乎完美的扩展到每个处理器一个单元这当然是你不能从连续 FEM 中得到的东西,但如前所述,隐式方案是完全不同的东西。

在组装刚度矩阵时,存储在连续(节点)FEM 中的单元中的数据必须传递给它的所有节点邻居。相比之下,DGFEM 要求将元素数据传达给它的所有面部邻居。1D 节点和面邻居是相同的,但在 3D 中差异可能非常大:对于规则的六面体网格,有 26 个节点邻居,但只有 6 个面邻居。对于具有许多高价顶点的不规则网格,CG 的情况会变得更糟,而 DG 的情况则保持不变。