面向大规模微观结构模拟的基于链表的无冲突并行前沿元胞自动机

《Journal of Computational Science》：Conflict-Free Parallel Frontal Cellular Automata with Linked Lists for Large-Scale Microstructure Simulations

　　

摘要

大规模微观组织演化模拟需要计算高效的数值方法，能够处理不规则动态数据结构并支持大规模并行执行。前端元胞自动机（FCA）通过仅对活动界面单元进行计算来降低计算成本，而单链表与经典元胞自动机（CCA）相比进一步降低了计算复杂度。然而，基于链表的FCA的高效并行化仍具挑战性，因为对不规则分布的列表元素进行同时处理可能会在共享内存中产生写冲突，且传统的区域分解策略无法直接应用。

本研究提出了一种基于无冲突链表管理的大规模微观结构模拟的并行FCA框架。所提出的方法结合了链表加速技术与CPU和GPU的并行执行。通过将对相邻单元间的信息传输分离为方向性流，并引入额外的元胞自动机缓冲区进行分阶段数据交换，从而消除了内存访问冲突。这使得在保持模拟正确性的同时，能够安全地并行处理多个链表。

开发了空间和时间空间两种并行化方案并实现了它们。三维晶粒生长模拟的计算实验表明，在所考虑的FCA变体中（包括有和无链表的顺序计算，以及无链表的并行执行），所提出的基于链表的并行FCA取得了最高的性能。该方法在CPU和GPU实现中展现出良好的可扩展性，并大幅减少了大规模模拟的计算时间。

所提出的框架结合了算法复杂度降低与可扩展的并行执行，并可扩展到其他不规则链接数据模拟方法中，包括DECA。

引言

准确且计算高效的微观组织演化模拟对于建模晶粒生长、再结晶[1]-[5]、相变[6]-[8]、凝固[9]-[12]、增材制造[13]-[15]及相关材料现象[16]-[18]至关重要。具有高分辨率的大规模三维模拟需要兼具物理一致性与高计算性能和可扩展性的数值方法。

在用于微观组织演化建模的数值方法中，元胞自动机（CA）[19], [20]由于其简单的局部规则、良好的可扩展性和相对较低的计算成本，仍然是最有效且应用最广泛的方法之一。与相场和多相场方法[14], [21], [22]、前缘跟踪和顶点模型[23], [24]以及水平集模型[25], [26]相比，CA[4], [19], [20], [27]通常能在计算效率和可扩展性之间提供良好的平衡，尤其适用于大规模模拟。

用于晶粒生长的经典元胞自动机（CCA）通常基于局部转移规则，即单元的状态根据其相邻单元的状态发生变化。在标准实现中，新状态使用输入邻域确定，并且每个时间步通常都会扫描整个计算域。尽管这种方法简单且稳健，但在大规模三维模拟中计算成本很高。

前端元胞自动机（FCA）[27], [28]通过引入额外的瞬态并使用输出邻域代替传统的输入邻域来改进这种方法。在CCA中，单元的状态根据从相邻单元接收到的信息（输入邻域）进行更新。在FCA中，活动单元向外向相邻单元传输信息（输出邻域），这显著减少了所需的计算量，并为基于链表的加速和并行化奠定了基础。因此，计算仅限于活动界面单元，而不活动的体相区域则被排除在处理之外，从而大幅降低了计算成本。

FCA中常用过渡时间控制和单元定时器来保持晶粒形状准确性，同时避免不必要的整体状态更新。引入单链表进一步提高了计算效率，因为只处理位于移动晶界上的单元。这显著减少了处理的单元数量，并提高了具有演化界面的大规模模拟的可扩展性。

现代多核CPU和GPU使得CA模拟能够进行高效的大规模并行执行。在CCA中，通常使用几何域分解进行并行化，将计算空间划分为由不同线程或处理器独立处理的子域。虽然这种策略对标准CA有效，但对于基于链表的FCA要困难得多，因为不规则分布的列表元素可能会在共享内存中产生写冲突。

最近，D'Ambrosio等人[29]针对GPU上的规则流式模板算法提出了两种无冲突执行方案（CfAMe和CfAMo），这些方案基于分阶段的方向性信息传输来消除写冲突。尽管这两种方法都采用方向性传播来避免冲突的内存更新，但它们是针对整个计算域上的规则模板计算而设计的。相比之下，本研究解决的是基于链表的Frontal CA的无冲突并行化这一根本不同的问题，其中动态演化的活动单元列表需要专门的算法进行列表管理、调度和负载均衡。

因此，基于链表的FCA的高效并行化仍是一个主要挑战。由于链表是顺序结构，活动单元的空间分布不规则，CCA中使用的传统并行化方法无法直接转移到FCA中。因此，将链表的计算优势与高效的并行执行结合起来需要一种新的无冲突并行框架。

本研究的主要目标是开发一个适用于基于链表的FCA的可扩展并行框架，将算法加速与CPU和GPU的并行执行结合起来。为实现这一目标，提出了一种基于信息流方向分离和使用额外CA缓冲区进行分阶段数据交换的新无冲突并行列表管理方法。开发了空间和时间空间两种实现，并对三维晶粒生长模拟进行了评估。

结果表明，所提出的方法能够在保持基于链表的FCA计算效率的同时，实现安全且可扩展的并行执行。

章节摘要

FCA概念

本研究中使用的FCA公式[27], [28]基于三种单元状态：初始状态q₀、瞬态状态q₁和最终状态q₂。每次迭代中，仅处理位于活动晶界上、处于瞬态状态q₁的单元。与CCA在每个时间步都扫描整个计算域相比，这显著减少了操作次数。

在链表实现中，状态为q₁的单元存储在单链表中，而处于

元胞自动机中列表的并行管理

并行化基于链表的FCA的关键挑战是消除由不同线程同时处理的不规则分布的活动单元所产生的写冲突。提出的解决方案基于用多个独立列表替换单个链表，并引入通过额外元胞自动机缓冲区进行分阶段信息传输。

为了实现并行执行，单个链表被重新组织成多个具有相同内部结构的独立列表

算法实现与计算实验

计算实验的目的是验证所提出的并行FCA框架，并评估其在保持结果物理一致性的同时减少大规模模拟计算时间的能力。所有顺序和并行实现在相同的物理问题上产生的最终微观组织完全相同，证实了所提出的并行化策略不会引入依赖于分解的伪影，并保持了

科学贡献及与以往FCA研究的比较

以往关于经典元胞自动机（CA）和前端元胞自动机（FCA）的研究表明，将计算限制在活动界面单元上可显著提高微观组织演化模拟的计算效率[27], [28]。与最近提出的无冲突模板执行方案[29]不同，本研究针对的是不规则的基于链表的元胞自动机，因此需要额外的算法用于动态列表管理和活动单元调度。在

结论

本研究提出了一个基于链表的Frontal元胞自动机（FCA）并行框架，能够在多核CPU和GPU上高效执行。提出了两种互补的并行化策略（称为空间和时间空间方法），并在大规模微观组织演化模拟中进行了验证。

所提出的框架在保留原始FCA算法数值公式的同时，大幅减少了执行时间。取决于

资金

波兰科学与高等教育部（项目号16.16.110.663）、波兰国家科学中心（项目号2024/53/B/ST11/00799）提供了资金支持。本研究还由AGH大学IDUB计划、行动D21资助。

CRediT作者贡献声明

Krzysztof Bana?：撰写-审阅与编辑，撰写-初稿，可视化，软件，调查，形式分析，数据整理。Dmytro Svyetlichnyy：撰写-审阅与编辑，撰写-初稿，软件，方法学，调查，形式分析，数据整理，概念化。

利益冲突声明

作者声明以下可能被视为潜在利益冲突的财务利益/个人关系：Dmytro Svyetlichnyy报告称，获得了波兰共和国科学与高等教育部、国家科学中心和IDUB的资金支持。Krzysztof Banas报告称，获得了波兰共和国科学与高等教育部和IDUB的资金支持。如果还有其他作者，他们声明没有

Dmytro Svyetlichnyy|Krzysztof Bana?