在视觉特效（VFX）行业的物理模拟领域，处理如自由表面液体、火焰、爆炸等复杂现象时，常常面临大规模分布式计算的挑战。这些基于偏微分方程（PDE）的模拟，其计算域（即模型的空间区域）的形状和拓扑结构会随时间快速演变，呈现出稀疏且动态的特性。如何高效地将这些模拟的计算负载分配到多个计算节点（或称秩，ranks）上，是提升性能的关键。一个理想的分区器（Partitioner）需要满足几个核心目标：一是确保计算任务在节点间的公平分配，即负载均衡（Load Balancing）；二是尽量减少节点间为交换数据（即“幽灵”数据，ghost data）而产生的通信开销；三是保持相邻时间步之间分区的一致性，以获得良好的时间连贯性；四是算法对艺术家友好，易于使用，无需复杂的参数调整。
为了应对这些需求，该研究团队提出了一种名为“Power Partitioner”的创新分区算法。该算法的核心思想是将分区问题建模为最优运输（Optimal Transport， OT）问题，通过最小化“计算工作负载”从空间位置（模拟域中的“桶”，buckets）运输到各计算节点（秩的位置）的总距离来实现优化。具体而言，该算法采用正则化形式的最优运输模型，引入了熵正则化项以确保解的唯一性和计算的稳定性。这种方法的几何学结果是生成一个幂图（Power Diagram），其中每个计算节点（秩）的位置作为一个“据点”（site），整个模拟空间被划分成围绕这些据点的幂单元。
算法的工作流程结合了Sinkhorn迭代来高效求解最优运输耦合矩阵，以及劳埃德（Lloyd）算法的思想进行迭代优化。在每次迭代中，首先根据当前的节点位置和桶（bucket）位置，通过Sinkhorn算法计算出一个最优的、软分配的耦合矩阵。然后，根据这个耦合矩阵，将每个桶硬性分配给与之耦合最强的节点，形成一个初步的分区。接着，计算每个节点分区内桶的“工作量”的质心（即工作负载中心），并将节点位置更新到这个新的质心位置。这个过程循环进行，直到满足收敛条件（如负载均衡度达到阈值）。通过这种方式，算法能够动态地调整节点在空间中的位置及其对应的分区形状，在保证负载均衡的同时，最小化分区边界（即通信接口）的长度，并自然地维持了分区在时间上的连贯性。
为了量化分区质量，作者引入了两个关键指标：表面指数（Surface Index， σ） 和时间一致性指数（Temporal Consistency Index， ν）。表面指数衡量了每个分区（对应一个计算节点）的表面与体积之比，反映了通信开销的大小，值越小表明分区越紧凑，通信成本越低。时间一致性指数则量化了相邻时间帧之间分区发生变化的程度，值越低表明分区随时间越稳定。
研究团队将该“Power Partitioner”与当前的主流分区方法，如图形分区器（如METIS）和空间填充曲线（SFC，如希尔伯特曲线）方法，在大量真实世界电影生产数据集（包含133个模拟缓存）上进行了全面比较。结果显示：
- •
在负载均衡和时间一致性方面：“Power Partitioner”表现优异。与希尔伯特曲线SFC相比，其时间一致性指数平均提升了约9.34倍；与METIS相比，提升幅度更是高达约505倍。这得益于最优运输模型对几何空间的连续感知和正则化带来的解的唯一性，使得分区对域的微小变化不敏感。
- •
在表面指数（通信开销）方面：“Power Partitioner”优于希尔伯特曲线SFC（平均提升约1.83倍），但略逊于专为最小化边割而设计的图形分区器METIS（METIS约为Power Partitioner的0.82倍）。然而，图形分区器在动态场景中往往会产生剧烈变化的分区，其优异的分割性能被糟糕的时间稳定性所抵消，导致在实际动态模拟中总开销反而更高。
- •
在适用性和稳健性方面：“Power Partitioner”能够自然地处理各种复杂、非凸、快速演变的稀疏动态域，无需用户指定切割方向或进行复杂调参。相比之下，传统的平面切割方法（plane-cutting）在缺乏明显主导方向的模拟中效果不佳，而基于预测（speculative）的分区方法则难以准确捕捉小尺度特征。
文章通过多个生动的案例展示了“Power Partitioner”的实效。例如，在电影《阿凡达：水之道》中的一个复杂飞溅水体模拟场景中，峰值内存消耗约500GB的模拟被成功划分为8个计算节点，分区结果在视觉上连贯且高效。在另一个船尾流模拟中，随着模拟域的扩展，“Power Partitioner”在保持时间一致性和较低通信开销方面显著优于其他方法，而METIS则因频繁的重分区导致运行时间大幅增加。
此外，研究还探讨了算法中的关键参数——正则化系数ε 的影响。当ε较大时，分区边界模糊，算法倾向于更均衡但可能不太紧凑的分区；当ε趋近于0时，幂图退化为经典的沃罗诺伊图（Voronoi Diagram），分区边界变得锐利。在实际应用中，作者建议将ε设置为与桶（block）尺寸相当的数量级，以在负载均衡和分区紧凑性之间取得良好平衡。
综上所述，这项研究提出并验证了一种基于最优运输理论的、实用且强大的分区器“Power Partitioner”。它巧妙地将计算负载分配问题转化为几何空间中的质量运输问题，在动态视觉特效模拟所需的负载均衡、通信开销最小化和时间连贯性等多个目标之间取得了出色的综合平衡。该算法不仅性能优越，而且对用户友好，为处理日益复杂和大规模的稀疏动态域分布式模拟提供了有力的新工具。
