计算科学 - 粒子分解和域分解并行化算法的优缺点是什么？ - 吾爱随笔录

粒子分解和域分解并行化算法的优缺点是什么？

计算科学并行计算效率分子动力学模拟

2021-12-13 00:04:38

我正在使用 Gromacs 和 DL_POLY 等几个软件包运行分子动力学 (MD) 模拟。

Gromacs现在支持粒子分解和域分解算法。默认情况下，Gromacs 模拟使用域分解，尽管多年来，直到最近，粒子分解是 Gromacs 中实现的唯一方法。在 Gromacs 的一篇论文 (DOI 10.1002/jcc.20291) 中，作者给出了他们最初选择粒子分解的原因：

“早期的设计决策是选择使用粒子分解而不是域分解来将工作分配给处理器。在后一种情况下，空间域被分配给处理器，这使得仅通过本地通信能够快速找到空间邻居，但由于复杂性对在空间边界上移动的粒子的影响是相当大的。只有当线性系统大小大大超过相互作用的范围时，域分解才是更好的选择，这在分子动力学中很少出现。通过粒子分解，每个处理器都计算力和坐标/速度更新对于指定的部分粒子，使用均匀分布在处理器上的预先计算的邻居列表。 $F_{ij}$ 和的更新必需的 $i$ $j$ $i$ $j$ , 只计算一次并传送给其他处理器。每个处理器都将系统的完整坐标集保存在其本地内存中，而不是将存储限制为它需要的坐标。这更简单并节省了通信开销，而内存要求通常根本不是限制因素，即使对于数百万个粒子也是如此。另一方面，邻居列表可以包含多达 1000 倍的粒子数量，分布在处理器上。通信本质上仅限于在处理器环周围的每个时间步发送一次坐标和力。随着时间的推移，这些选择已被证明是稳健的，并且很容易适用于现代处理器集群。”

“只有当线性系统大小大大超过相互作用范围时，域分解才是更好的选择，而分子动力学中很少出现这种情况”这句话中的“线性系统大小”是什么意思？从上面的段落中，我了解到粒子分解的优点是不必处理跨域边界移动的粒子。相反，您只需要为每个处理器提供足够的内存来存储整个系统配置。所以粒子分解看起来非常有利，而域分解看起来非常不利。

我确信这是一个非常复杂的问题（可能是许多书籍的主题），但基本上，如果粒子分解看起来如此有利，为什么有人需要使用域分解？ 如果系统的大小非常大（使得在每个处理器中存储总配置变得困难或不可能），域分解是否只是有利的？根据上面引用的段落，我不确定为什么域分解现在是 Gromacs 中的默认并行化算法，就在最近。

DL_POLY现在（第 4 版）似乎也使用域分解。来自第 4 版手册：

“以这种方式划分配置数据是基于模拟单元中原子的位置，系统数据的这种几何分配是 DD 算法的标志。请注意，为了使这种策略有效地工作，模拟的系统必须具有合理均匀的密度，以便为每个处理器分配几乎相等部分的原子数据（尽可能多）。通过这种方法，力计算和运动方程的积分在处理器和处理器之间（合理）平等地共享在很大程度上可以在每个处理器上独立计算。该方法在概念上很简单，但很难编程，特别适用于效率最高的大规模模拟。

...

在 DD 策略的情况下，SHAKE (RATTLE) 算法比 DL_POLY Classic 的复制数据方法更简单，后者需要原子位置的全局更新（合并和拼接）。”

这听起来好像域分解是好的，因为它可能更有效，即使可能更难以实现。

另一方面，以前的版本（DL_POLY Classic）使用复制数据并行化，这似乎是粒子分解的另一个名称。从该版本的手册中：

复制数据 (RD) 策略是在 MD 中实现并行化的几种方法之一。它的名字来源于并行计算机的每个节点上的配置数据的复制（即定义原子坐标，速度和力的数组，对于全部 $\textbf{r}_i$ $\textbf{v}_i$ $\textbf{f}_i$ $N$ 模拟系统中的原子，在每个处理节点上再现）。在这种策略中，大部分力的计算和运动方程的积分可以在节点之间轻松平等地共享，并且在很大程度上可以在每个节点上独立处理。该方法编程相对简单并且相当有效。此外，它可以很容易地“折叠”以在单个处理器上运行。然而，该策略在内存中可能很昂贵并且具有很高的通信开销，但总体而言，它已被证明在广泛的应用程序中是成功的。

这一段似乎与这个问题的第一段大体一致，除了它说复制的数据/粒子分解具有“高通信开销”。Gromacs 论文中的段落似乎相反——粒子分解更可取，因为它比域分解具有更低的通信开销。

你有什么想法吗？

3个回答

粒子和域分解与加速有限范围相互作用系统的力计算的两种主要方法直接相关 - Verlet 邻居列表和单元链接列表。如果您想了解详细信息，Allen 和 Tildesley 有一本非常不错的书，名为Computer Simulation of Liquids，被许多人认为是分子动力学和蒙特卡洛研究的“圣经”。然后是来自 Griebel、Knapek 和 Zumbusch的分子动力学数值模拟，它深入探讨了并行实现 MD 的各种技术。

基本上，Verlet 列表构建了给定半径内给定原子/分子（或一般粒子）的所有邻居的列表。稍后，当检查原子对以计算力时，会查阅该列表。一旦你构建了列表，很明显哪些粒子与其他粒子接近，并且它们可以分布在不同的处理器中进行评估。该列表只是不时地使用一些巧妙的技术来构建它以使其保持最新，因为它需要来构建（检查所有可能的粒子巴黎）。给定已构建列表的强制评估需要。 $O(N^2)$ $O(N)$

单元链接列表将空间划分为等大小的单元，这些单元大于相互作用势的截止距离，然后将每个粒子放在与其所属的单元相关联的列表中。这个过程需要。然后仅在同一单元格或其相邻单元格中搜索给定粒子的邻居。由于每个单元都有恒定数量的邻居（例如，在 3-D 情况下为 26 个），因此在中评估力。但是这里的常数乘数可能足够大，以使该算法的扩展性比 Verlet 列表方法更差。但是对于足够大的 $O(N)$ $O(N)$ $N$ 它可以更好地扩展。因此线性大小参数。域分解方法是单元链表方法的直接扩展 - 单元在不同的 CPU 中划分。

域分解的问题在于，当粒子从一个单元移动到另一个由另一个 CPU 处理的单元时，它必须进行通信。在较高的模拟温度下，这可能会成为问题，其中粒子倾向于移动到比其平衡位置更远的位置，或者当存在粒子流时。此外，来自域边界上的单元的信息必须在每次迭代时传输到相邻域。但所有这些都是本地同步通信，可以非常有效地完成。

复制数据是最简单的方法，但不幸的是，它要求在每一步中所有位置和速度信息都在全球范围内同步。这确实不能很好地扩展，对于非常大的系统，全局内存量是数据结构的大小乘以使用的 CPU 数量，而并行处理的目标之一是分布数据，以便每个 CPU 持有更少超过全球数据量。

总之，不存在适用于所有被模拟系统的“一刀切”的方法。大多数情况下，最好的并行化策略可以从系统几何结构中推断出来，并且可以选择适合这种情况的 MD 代码——毕竟它们都实现了或多或少相同的基础力场和积分器。

“只有当线性系统大小大大超过相互作用范围时，域分解才是更好的选择，这在分子动力学中很少出现”，那篇（非常古老的）GROMACS 论文的作者表示，如果邻居列表的空间大小是1nm量级，而模拟单元只有几纳米，那么做域分解的开销太高了。您不妨接受粒子分解中的全对全信息分布，而无需花时间在所有记账上进行域分解。

GROMACS 实现的粒子分解问题在于，随着时间的推移，分配给每个处理器的粒子会在空间中扩散。由于计算每个交互的责任由它们的初始位置固定，因此扩散逐渐增加了每个处理器为了构建其邻居列表而需要知道的总空间的体积，即使邻居列表描述的总计算量是恒定的。在实践中，您会定期重新启动模拟以重置数据和通信位置。

如果扩散在模拟的时间范围内很重要，那么您的假设“粒子分解具有不必处理跨域边界移动的粒子”的优点是不成立的。

域分解通过将交互责任与扩散一起迁移来处理这种“预先”，从而改善每个处理器上的数据局部性，并最大限度地减少通信量。

免责声明：我帮助开发 GROMACS，下周可能会淘汰粒子分解实现 ;-)

我想补充 Hristo Iliev 的答案。虽然他的帖子主要讨论了计算复杂性，但在并行化方面，通信复杂性至少同样重要——它是域分解的主要原因。

现代并行机通常具有某种圆环拓扑。这意味着每个 CPU 都有许多“相邻”的 CPU，它们可以非常快速地进行通信。与不是邻居的 CPU 通信成本更高。因此，拥有一种只需要与相邻 CPU 通信的算法总是有利的。

使用粒子分解时，粒子的交互伙伴随机分布在所有其他 CPU 上。为了能够计算交互，它需要知道所有伙伴的坐标，因此它需要与所有其他CPU 通信。实际上，这意味着当你有 $P$ 中央处理器， $\mathcal{O}(P^2)$ 需要沟通步骤。此外，很多通信都是与非相邻 CPU 进行的。

另一方面，在域分解方案中，所有交互伙伴都存在于相邻的 CPU 上。这意味着它只需要与它最近的邻居通信来获取更新的信息，即 $P$ CPU 需要 $\mathcal{O}(P)$ 沟通步骤。此外，所有的通信都是与相邻的 CPU 进行的。

显然，当系统分布不均匀时，这种方案就不是最优的。发生这种情况时，这要么意味着某些 CPU 的工作量明显高于其他 CPU，要么意味着必须动态调整域。这可能会导致域拓扑和网络拓扑不匹配（大型域有更多邻居）。尽管如此，通信的复杂性 $\mathcal{O}(P)$ 仍然成立。

但是请注意，非均匀系统并不像听起来那么普遍，它们仅在模拟真空中的某物或使用隐式溶剂时才会出现。晶体和液体的密度足够接近以进行域分解。

其它你可能感兴趣的问题

上一篇函数有理逼近的开源实现下一篇大型数据集计算问题的 I/O 策略？