一种用于在稀疏动态域上进行分布式仿真的实用划分器,该方法基于最优传输理论

《ACM Transactions on Graphics》:A practical partitioner for distributed simulations on sparse dynamic domains using optimal transport

【字体: 大 中 小 】 时间:2026年02月02日 来源:ACM Transactions on Graphics

编辑推荐:

  摘要 要查看此由AI生成的摘要,您必须具有高级访问权限。了解更多信息请登录。 **摘要** 本研究解决了视觉效果行业中常见的大型物理模拟分布挑战。这些基于偏微分方程的模拟用于建模复杂现象,如自由表面液体、火焰和爆炸,并且其域的形状和拓扑结构会迅速变化。在此背景下,我

  摘要
要查看此由AI生成的摘要,您必须具有高级访问权限。了解更多信息请登录。

**摘要**
本研究解决了视觉效果行业中常见的大型物理模拟分布挑战。这些基于偏微分方程的模拟用于建模复杂现象,如自由表面液体、火焰和爆炸,并且其域的形状和拓扑结构会迅速变化。在此背景下,我们提出了一种新的划分算法,该算法采用最优传输技术(生成功率图),旨在处理随时间快速变化的多种模拟域形状。我们的Power划分器确保计算任务均匀分配,减少节点间数据交换,并保持时间一致性,同时具有直观性和艺术友好性。为了量化划分质量,我们引入了两个指标:表面指数和时间一致性指数,并在真实电影制作数据上进行了多种比较,结果表明我们的方法在大多数情况下优于现有技术。

**AI摘要**
要查看此由AI生成的通俗语言摘要,您必须具有高级访问权限。

**1 引言**
在分布式模拟的背景下,划分器的作用是将计算工作负载分配到多台机器(也称为节点或等级)上,以最大化性能。由于确切的计算和通信成本通常在事先是未知的,因此最优分配通常由一组启发式目标定义,例如确保计算任务的公平分配以防止个别节点过载(也称为负载平衡)以及减少等级间数据交换所需的通信开销。这些目标之间的固有冲突——增强一个目标可能会削弱另一个目标——带来了重大挑战。
我们的工作专注于为视觉效果(VFX)行业量身定制的模拟应用。这些模拟基于物理原理,利用偏微分方程(PDE)来建模复杂现象,如液体或烟雾。它们通常使用笛卡尔网格或混合粒子-单元方法进行离散化。重点主要放在输出的美学质量和视觉丰富性上,以吸引电影、游戏或其他媒体中的观众,而不是原始的计算精度。因此,从业者倾向于使用计算负担较轻的低阶方法,而不是传统工程应用中使用的方法。随着模拟分辨率的提高,当模拟不再适合工作内存(通常约为256-512 GB)时,从业者会采用分布式技术。
由于VFX模拟的特点是强调视觉上引人注目和动态的输出,因此模拟域往往表现出高度动态的行为,其拓扑结构稀疏且随时间迅速变化。这种快速变化使得最小化与从一个帧到下一个帧重构域相关的通信成本变得尤为重要,而不是静态划分域中相邻邻居数据传输的成本。

下面我们简要总结了为满足我们应用独特需求而确定的划分器要求:
- **公平的工作分配**:分配给每个等级的工作负载应尽可能均匀。由于无法准确预测实际的计算工作量,许多方法依赖于近似或代理指标,例如分配给给定等级的网格单元(也称为体素)或粒子数量,我们在当前工作中采用了这种方法。
- **最小化幽灵传输**:在基于PDE的模拟中,等级间的幽灵数据传输受空间局部性的影响:传输发生在不同等级的数据区域在空间上相遇的边界层。减小边界大小可以减少数据交换量,降低开销并提高效率。
- **时间一致性**:在VFX背景下,时间一致性是一个关键考虑因素,需要最小化连续模拟帧之间计算工作分配的显著变化,从而限制等级间数据移动的量。
- **艺术友好性**:划分器必须优先考虑简单性、透明性和可靠性,确保视觉效果行业的艺术家能够专注于创造力而不是技术调整。它应该开箱即用,无需手动调整或深入了解分布式系统。

为了了解当前最先进划分算法在处理稀疏动态域时的不足之处(将在第3节讨论),我们首先在第2节介绍我们域结构的数学基础。为了解决上述挑战,我们提出了一种基于正则化最优传输的新划分算法。它将计算工作单位(见第2节)映射到等级上,这些等级在模拟世界空间中被建模为点,通过最小化工作的总传输距离来实现。所得到的划分结果是一个功率图,等级位置作为站点,结合Lloyd算法[Lloyd 1982],我们可以在不进行任何用户干预的情况下确保平衡分配和最小化邻居传输。我们在第4节介绍了这种Power划分器,并在第5节和第6节将其与现有方法进行了比较。

**2 稀疏域和划分**
稀疏网格在计算机图形和VFX应用中非常普遍[Bridson 2003; Museth 2013; Setaluri et al. 2014; Bojsen-Hansen et al. 2021]。与分配完整的张量积(或密集)网格不同,稀疏网格采用分层结构,根据网格点与感兴趣区域的接近程度选择性地包含它们,从而大幅减少所需的内存,同时保持足够的空间覆盖范围。对于均匀网格,一种流行的实现选择是稀疏块结构[Lesser et al. 2022; McAdams et al. 2011; Zhu et al. 2010; Wang et al. 2005],其中网格域表示为一系列轴对齐的不重叠密集立方体体素块(见图2)。除了表示最小的空间覆盖范围外,这些块同时作为并行工作的单位。较小的块可以精确覆盖感兴趣的详细区域并提高并行性,但处理大量块可能会变得繁琐。相反,较大的块通过减少总数简化了管理,尽管它们可能不完全符合模拟域,导致不必要的填充,并且也更难以均匀划分。文献表明,最佳块大小介于\(4\times 4\times 4\)和\(8\times 8\times 8\)网格体素之间[Lesser et al. 2022; McAdams et al. 2011; Zhu et al. 2010]。

**图1.**
对于《阿凡达:水的世界》中的一个场景(顶部),一个考虑表面张力和粘性的稀疏粒子-单元溅水模拟(底部)[Stomakhin et al. 2023],其总内存消耗峰值约为500 GB,使用我们的Power划分器被分为8个等级(由颜色表示)。顶部图片来自AVATAR: WAY OF WATER ?2022 20th Century Studios, Inc. 保留所有权利。底部图片 ? Wētā FX Ltd.

**图2.**
一个2D稀疏网格模拟域的示意图,由块/桶(大方块)组成,每个块包含\(4\times 4\)个体素(小方块),在这个例子中,还有一些粒子(小圆圈)。着色表示将桶划分为2个等级。? Wētā FX Ltd.

下面我们给出与我们的稀疏域表示相关的正式定义。我们假设模拟发生在3D空间中,并将\(d= 3\),除非另有说明。

**定义2.1.**
感兴趣区域是一个随时间变化的子集\(\Omega _t\subset \mathbb {R}^d\),其中\(t\in \mathbb {R}\)代表时间,我们希望跟踪某些(离散的)函数的演变,这些函数代表视觉、物理或几何特征,如烟雾密度、温度、液体有符号距离场、粒子等属性。

**定义2.2.**
一个桶\({\mathbf {b}}\)是一个半开放的、立方体的、轴对齐的空间区域\(\mathbb {R}^d\),它将代表我们稀疏块网格结构中的一个块。假设所有桶B的组合能够无重叠地覆盖整个\(\mathbb {R}^d\)。

**定义2.3.**
桶化是一个函数\(\mathcal {B}: \mathbb {R}^d\rightarrow B\),它将任何点\(\mathbf {x}\in \mathbb {R}^d\)映射到包含它的桶\({\mathbf {b}}\in B\)。

**定义2.4.**
邻域函数\(\mathcal {N}: B\rightarrow 2^B\)定义了任何桶\({\mathbf {b}}\in B\)的邻居桶列表。一般来说,邻域概念不一定意味着物理空间中的接近性,而是描述了当前模拟系统内的交互模式,对于长距离力来说可能会变得相当复杂。然而,在PDE的情况下,邻域对应于直接相邻的桶。

**定义2.5.**
域描述\((\mathcal {B}, \mathcal {N})\)是桶化和邻域函数的配对。

**定义2.6.**
均匀网格域描述是通过选择桶大小\({\Delta }\gt 0\)并设置\begin{align} \mathcal {B}_{\Delta }(\mathbf {x}) &= \Big \lfloor \frac{\mathbf {x}}{{\Delta }} \Big \rfloor , \end{align} (1)来定义的,即集合B由间距为\({\Delta }\)的均匀网格立方体体素组成。如果两个桶之间的欧几里得距离为零,则认为它们是邻居,这意味着它们的封闭体共享一个面、一条边或一个角。

**定义2.7.**
桶子集是一个(有限的)集合\(S\in 2^B\)。模拟域是分配计算体积数据的区域,通过桶子集指定,我们将其称为(模拟)域子集\(D_t= \lbrace \cup _{\mathbf {x}\in \Omega _t} \mathcal {B}(\mathbf {x})\rbrace\)。

**定义2.8.**
填充函数\(\mathcal {T}: 2^B\rightarrow 2^B\)定义为\begin{equation} \begin{aligned}\mathcal {T}(S) &= \lbrace {\mathbf {b}}\cup \mathcal {N}({\mathbf {b}}), {\mathbf {b}}\in S\rbrace , \\ \end{aligned} \end{equation} (2),它通过一层桶来扩展给定的域子集。

**定义2.9.**
划分是一个函数,它将给定桶子集S的桶映射到等级\(\mathcal {P}: S\rightarrow {[R]}\),其中\({[R]}\equiv \lbrace 0 \dots R-1\rbrace\),R是等级的总数。对应于等级r的划分是分配给该等级的桶子集,具体来说\(P_r= \lbrace {\mathbf {b}}\in S: \mathcal {P}({\mathbf {b}}) = r\rbrace\)。除非另有说明,我们假设划分是在域子集上计算的,即\(S= D_t\)。我们将用于生成桶子集S的划分\(\mathcal {P}\)的算法称为划分器\(\mathbb {P}\),因此\(\mathbb {P}(S) = \mathcal {P}\)。

给定每个桶\({\mathbf {b}}\)的计算工作量\(W_{\mathbf {b}}\),与等级r相关的划分\(P_r\)的计算工作量为\(W_r= \sum _{{\mathbf {b}}\in P_r} W_{\mathbf {b}}\)。我们特别感兴趣的划分器是:(1)在所有等级上产生最小的工作量变化\(W_r\);(2)对于每个划分\(P_r\),最小化不属于它的邻居桶的数量\(|\mathcal {T}(P_r) \setminus P_r\cap D_t|\);(3)随着\(D_t\)的演变保持划分的时间一致性。

**注释。**
定义2.5中的域定义允许更一般的形状(例如,自适应八叉树),而我们用方程(1)定义的均匀网格,无需对我们在第4节中概述的划分器算法进行任何更改。

**3 现有方法**
文献中有许多可用的划分器。
- **基于图的划分器**:基于图的划分器将计算域建模为图:顶点代表计算单元(例如我们稀疏网格结构中的桶),而边编码来自邻域函数\(\mathcal {N}\)的空间依赖关系。然后将划分问题视为图割优化任务,目标是最小化连接不同等级的边数,同时平衡计算负载,由顶点权重\(W_{\mathbf {b}}\)表示。广泛采用的METIS [Karypis and Kumar 1998]和ParMETIS [Schloegel et al. 2003]采用多级递归二分或k-way划分策略来实现这些目标。
- 对于稀疏和不规则域拓扑,这些方法产生接近最优的划分。然而,域子集的微小变化往往会导致划分的巨大变化,从而导致帧间的时间一致性较低。这种敏感性是因为基于图的方法仅基于连通性操作,对域的世界空间几何形状知之甚少,使得它们难以随时间保持空间一致性。在VFX应用中,由于域子集在帧间可能会发生显著变化,我们的测试显示这些方法的性能较差(见第5节)。
- **空间填充曲线(SFC)方法**:许多方法使用几何启发式方法来获得最优划分的合理近似。SFCs [Tsuzuki and Aoki 2016; Borrell et al. 2020],如Hilbert曲线或Morton(也称为Z-order)曲线,提供了一种计算效率高的方法,将多维数据映射为一维序列。有一种流行的说法是,这种映射方式能够保持局部性,这意味着原始多维空间中相邻的点在1D排序中仍然保持接近。这反过来意味着,当使用这种1D排序在各个等级之间分配工作(即桶)时,通信开销被最小化。然而,上述初始说法只是近似的:尽管概率很小,但在映射中仍然存在遇到非局部模式的可能性,这些模式发生在SFC的不同线圈在空间上相遇的地方。实际上,这会导致SFC划分器产生视觉上明显的伪影,从而破坏了局部性。此外,1D桶的排序会随着域子集边界框的变化而迅速变化,导致拓扑结构变化快速的域具有较差的时间一致性。为了说明最后两点,请考虑图3(左上角),其中一个月牙形域被Hilbert SFC划分(算法细节见第5节)。紫色的划分主要位于左上角,但也有一些散布在底部的桶,显示出较差的局部性。然后,当在当前域之外引入一个单独的桶时(图3,中间),域子集的边界框发生变化,导致划分发生剧烈变化。虽然这种情况看似人为设计,但在VFX模拟中非常常见:水花可以将单个水滴抛向空中,导致时间上不连贯的划分。

图3. 划分一致性。左列:在4个等级上对月牙形域\(S^1\)进行SFC和Power划分的可视化。中间列:添加了一个新的桶\({\mathbf {b}}\),得到\(S^2 = S^1 \cup {\mathbf {b}}\),然后重新划分域。右列:通过将等级发生变化的桶标记为白色来可视化\(\mathbb {P}(S^1)\)和\(\mathbb {P}(S^2)\)之间的差异。SFC划分的显著变化是由于域边界的变化。? Wētā FX Ltd.

Voronoi方法(例如,参考文献[Koradi等人2000])直观且强大,与我们的局部性和工作平衡目标非常契合。然而,传统的实现方式,如标准的质心Voronoi镶嵌,在动态VFX模拟中面临挑战。构建显式的Voronoi网格,如Fu等人[2017]所做的那样,会增加计算开销和实现复杂性,因为必须将桶分类到单元格中。重要的是,当\(W_{\mathbf {b}}\)在空间上不均匀时,负载平衡会变得越来越不准确,因为Voronoi划分仅依赖于几何形状,无法适应异构的工作分布。也可能无法直接划分任意形状的域,而是需要将其嵌入到凸包中,从而导致更多的开销和元素过度拉伸的网格。

我们的Power划分器在很大程度上受到了Voronoi方法的启发,并对其进行了改进。它产生了类似Voronoi的结构,因此保留了所有期望的局部性属性,同时也能够平等地划分任意形状的域和空间变化的工作函数。从概念上讲,Power划分器介于基于图的方法和纯几何启发式方法之间。正则化最优传输公式(第4.1节)可以被视为图划分的连续类比,用基于世界空间中等级和顶点之间距离的优化来替代离散的边切割最小化。然而,它并没有明确最小化通信量,而是在负载均衡、空间紧凑性和时间一致性之间提供了实际的平衡。因此,对于连接性稳定的域,基于图的方法可以实现较低的幽灵通信开销,尽管时间稳定性会降低。表1定性地总结了SFCs(Hilbert曲线)、基于图的方法(METIS)和我们的Power划分器在不同划分属性上的表现。我们将在第5节更定量地评估这些划分器。

表1. 分划器 速度 工作平衡 局部性 时间 图基 \(\star\)\(\star\)\(\star\)\(\star\)\(\star\)\(\star\)\(\star\)\(\star\)\(\star\)\(\star\)\(\star\)\(\star\) Hilbert曲线 \(\star\)\(\star\)\(\star\)\(\star\)\(\star\)\(\star\)\(\star\)\(\star\)\(\star\)\(\star\)\(\star\)\(\star\)\(\star\) Power图 \(\star\)\(\star\)\(\star\)\(\star\)\(\star\)\(\star\)\(\star\)\(\star\)\(\star\)\(\star\)\(\star\)\(\star\)\(\star\)

存在其他更适合于紧凑、盒形或基本静态的模拟域的划分策略。鉴于我们提出的目标,我们明确不考虑针对这些有限域形状定制的方法——例如静态划分技术[Irving等人2006;Wang等人2020]或轴对齐的平面切割技术[Surmin等人2015;Qiu等人2022]。尽管平面切割在VFX应用中很常见([Bailey等人2015;Lait 2016;Flores和Horsley 2009]),但它只有在有“首选”模拟方向时才能很好地工作。对于高度动态的模拟,如图1中强调的流体模拟,这样的方向并不总是可以指定的。此外,平面切割技术通常要求模拟操作员提前指定切割平面的数量及其方向,这与我们之前提出的艺术家友好性目标相冲突。灵活的递归变体平面切割(类似于kd树)在计算流体动力学中是经典的[Berger和Bokhari 1987],但众所周知,这些方法产生的划分质量比前面讨论的现代基于图的方案要低得多[Bruaset和Tveito 2005]。

另一个例子是Shah等人[2018]提出的推测性划分技术,他们通过同时进行低分辨率模拟来预测未来的感兴趣区域,从而考虑了划分的时间方面。由于我们感兴趣的许多特征都是尺度依赖的——例如表面张力效应(图1)或化学燃烧(图9)——低分辨率模拟很少能预测实际的未来模拟状态。

图4. 正则化对Power划分的影响。耦合\(\mathbf {T}\)(顶部)和结果划分\(\mathcal {P}\)(底部)在不同\(\varepsilon\)下的可视化,用于非凸域。等级用颜色\(\mathbf {\gamma }_r\)的圆圈表示。在顶部行中,颜色是根据\(\mathbf {\gamma }_{\mathbf {b}}= \left(\sum _{r} \mathbf {\gamma }_r\mathbf {T}_{r{\mathbf {b}}}\right)/\left\Vert \sum _{r} \mathbf {\gamma }_r\mathbf {T}_{r{\mathbf {b}}}\right\Vert _2\)计算的。在底部行中,颜色是根据\(\mathbf {\gamma }_{\mathbf {b}}= \mathbf {\gamma }_{\mathcal {P}({\mathbf {b}})}\)计算的。? Wētā FX Ltd.

图5. Power划分器收敛图。我们研究了算法1中Lloyd迭代循环的收敛性。域子集是一个在所有边上都有\(\lfloor \sqrt [3]{10^4R}\rfloor\)个桶的盒子,以保持每个划分\(P_r\)的大小大致相等。我们设置\(\tau _\text{load}= 0\)以确保算法1中的中断永远不会触发,并且我们改变等级的数量\(R= \lbrace 2, 4, 8, 16, 32\rbrace\)。? Wētā FX Ltd.

图6. 船尾流。在一个移动的船周围进行了混合粒子-单元格流体模拟,随着模拟的进行,域不断扩大。模拟的粒子根据它们的等级进行着色;在最后一帧中总共有169M个粒子(顶部)。运行时间:METIS由于时间不连贯性比Power慢了3倍以上,且图表被划分可视化所截断。表面指数:\(\max _r\sigma\)用实线表示。阴影着色区域代表\([\min _r\sigma , \max _r\sigma ]\)。? Wētā FX Ltd.

图7. 模拟语料库。我们在133个模拟数据缓存上运行METIS、SFC和我们的Power划分器。对于每个缓存中的每一帧,我们计算一个划分\(\mathcal {P}= \lbrace\)METIS, SFC, Power\(\rbrace\),并在直方图上报告相对指标METIS/Power(橄榄色)和SFC/Power(绿色)作为数据点。顶部:记录了每帧的相对最大表面指数(方程(19))。底部:记录了每帧的相对时间指数(方程(20)。每个直方图的均值用虚线垂直线表示;虚线蓝色线条对应于Power划分器,可以用来指导它与其他两种方法的比较。平均而言,Power在时间指数上优于SFC(9.34倍)和METIS(505倍);对于表面指数,Power优于SFC(1.83倍),但略逊于METIS(0.82倍)。? Wētā FX Ltd.

图8. 旋转台。一个矩形域快速旋转24帧,在此期间我们执行泊松求解,然后是欧拉平流步骤。显示了第1、8和23帧的划分(顶部);METIS每帧产生相似的划分,但它们在时间上有所移动;当域非轴对齐时,SFC会产生非局部划分(见第8和23帧);Power(我们的)产生局部且时间稳定的划分。时间指数\(\nu\)在箱形图中记录每帧(中间),以及总运行时间(底部)。? Wētā FX Ltd.

图9. 火焰喷射器。在一个体积燃烧模拟(左侧)中,我们在4台机器上使用了我们的Power划分器。这里火/烟密度(中间)和稀疏的模拟域桶(右侧)按等级着色。? Wētā FX Ltd.

我们强调,我们的方法与Kale和Krishnan [1993]以及Pearce等人[2012]的一般负载平衡框架很好地协调,这些框架利用实时数据进一步提高了划分质量;然而,我们认为这些技术是对这里介绍的划分器的补充,超出了我们工作的范围。

在图形学中,我们通过强调最优传输的增加使用来结束这一节。最早的例子之一是de Goes等人[2012]的工作,他们展示了如何使用最优传输进行蓝噪声采样。从那时起,已经有各种工作将最优传输应用于离散域([Mandad等人2017;Solomon等人2015;Solomon 2018])和物理模拟([de Goes等人2015;Qu等人2022;Wretborn等人2025;Qu等人2023;Zhai等人2020])。

当我们在非常动态的场景(例如图1)或稀疏的非凸域(例如图10中的“河流”形状)上观察到SFC划分时,需要一个新的划分器,因为在这些情况下,单个等级的划分会在相邻帧之间明显闪烁或表现出严重的非局部性。另请参见补充视频。

图10. 弱缩放。展示了River、Plume和Waves弱缩放示例的结果,比较了在静态域上不同的划分算法,我们执行了泊松求解,然后是欧拉平流步骤。我们提供了最终帧的表面指数\(\sigma _\mathcal {P}(r)\)(方程(19)(顶部行),以及运行时间最短的帧(10帧中的那一帧)的性能数字(中间行)。我们明确标记了计算划分所花费的时间和传输幽灵数据所花费的时间。由于域是静态的,我们没有提供时间一致性指数。为了进行视觉比较,我们还可视化了8台机器的划分;图像边框的颜色表示使用了哪种算法。这些模拟的性能指标在表4中总结。? Wētā FX Ltd.

我们的目标是开发一种新技术,以改进现有方法的局部性和时间一致性。为此,我们引入了一种基于正则化最优传输和功率图的新划分器,因此命名为“Power划分器”。这种方法产生了类似于Voronoi单元格的几何结构,可以用来创建高质量的划分,同时计算效率也很高。在本节中,我们首先描述了正则化最优传输在我们问题域中的应用(第4.1节),然后定义了我们的划分器并讨论了实现考虑因素(第4.2节)。

4.1 正则化功率图

我们将使用正则化功率图作为我们的空间启发式选择,可以通过最优传输的视角来理解。关于最优传输的入门知识,我们推荐Peyré和Cuturi [2019]的综述。

我们使用\(\mathbf {x}_{\mathbf {b}}\in \mathbb {R}^d\)来表示分配给给定桶\({\mathbf {b}}\in B\)的固定参考位置,并类似地用\(\mathbf {x}_r\in \mathbb {R}^d\)来关联每个等级\(r\in {[R]}\)。在求和表达式中,当上下文明显时,我们将省略表示集合成员资格的符号,例如,\(\sum _{\mathbf {b}}\)将意味着对所有\({\mathbf {b}}\in D_t\)进行求和。当时间无关或从上下文中清楚时,我们也将省略下标t。设\(\mathbf {C}: {[R]}\times D\rightarrow \mathbb {R}_+\)为所谓的成本函数,其中每个条目\(\mathbf {C}_{r{\mathbf {b}}}\)是等级和桶之间的平方距离\(\mathbf {C}_{r{\mathbf {b}}} = \left\Vert \mathbf {x}_r- \mathbf {x}_{\mathbf {b}}\right\Vert _2^2\)。我们定义每个等级的期望工作量为\(L= \sum _{\mathbf {b}}W_{\mathbf {b}}/ R\)。那么存在一个最优的耦合矩阵 \(\mathbf {T}: {[R]}\times D\rightarrow \mathbb {R}_+\),它满足以下条件:
\[
\begin{align}
\mathbf {T}= \text{\arg \!\min }_\mathbf {T}&\sum _{r, {\mathbf {b}}} \mathbf {T}_{r{\mathbf {b}}} \mathbf {C}_{r{\mathbf {b}}} - \varepsilon \mathcal {H}(\mathbf {T}),
\end{align}
\]
(3)
\[
\begin{align}
\text{受限于} &\sum _{\mathbf {b}}\mathbf {T}_{r{\mathbf {b}}} = L\; \forall r,
\end{align}
(4)
\[
\begin{align}
&\sum _r\mathbf {T}_{r{\mathbf {b}}} = W_{\mathbf {b}}\; \forall {\mathbf {b}},
\end{align}
(5)
\]
其中 \(\varepsilon \in \mathbb {R}_+\) 是用户定义的正则化参数,\(\mathcal {H}(\mathbf {T})\) 是离散熵,即 \(\mathcal {H}(\mathbf {T}) = -\sum _{r,{\mathbf {b}}}\mathbf {T}_{r{\mathbf {b}}} \left(\log \mathbf {T}_{r{\mathbf {b}}} - 1 \right)\)。
耦合矩阵 \(\mathbf {T}\) 表示等级和桶之间的工作分配,编码了 \(R\times |D|\) 个未知数。这些未知数受到预设的边际分布的约束:每个等级必须接收总工作量 L,而每个桶的整个工作量 \(W_{\mathbf {b}}\) 必须分配给各个等级。
目标函数平衡了运输成本 \(\sum _{r{\mathbf {b}}}\mathbf {T}_{r{\mathbf {b}}}\mathbf {C}_{r{\mathbf {b}}\)(倾向于等级和桶之间的接近性)和熵正则化项 \(\varepsilon \mathcal {H}(\mathbf {T})\)。这种正则化引入了严格的凸性,确保了最优解 \(\mathbf {T}\) 的存在性和唯一性,与未正则化的最优运输不同,在未正则化的情况下可能存在多个最优解。这种唯一性对我们的问题来说是一个理想的特性:它使得分区在时间上更加稳定,因为它减少了随着领域的发展而在质量相当但截然不同的解决方案之间切换的可能性。
\(\mathbf {T}\) 的几何解释是一个近似的功率图,等级位置作为站点,而随着 \(\varepsilon \rightarrow 0\),扩散的边/面逐渐变得尖锐;见图 4 的顶部行。值得注意的是,\(\varepsilon\) 的单位是长度,可以被视为功率单元之间扩散转换的特征宽度。一个等级的工作重心可以通过功率核 [Qu et al. 2022, Equation (6)] 计算得出,即
\[
\begin{equation}
\mathbf {c}_r= \frac{1}{L} \sum _{{\mathbf {b}}} \mathbf {T}_{r{\mathbf {b}}} \mathbf {x}_{\mathbf {b}}\; \forall r.
\end{equation}
(6)
方程 (3) 中给出的熵项的具体选择意味着解的形式为 [Peyré and Cuturi 2019, Prop. 4.3]
\[
\begin{equation}
\mathbf {T}_{r{\mathbf {b}}} = q_re^{-\mathbf {C}_{r{\mathbf {b}}}/\varepsilon } q_{\mathbf {b}}\; \forall r,{\mathbf {b}},
\end{equation}
(7)
对于每个等级和桶分别定义的未知变量 \(q_r\) 和 \(q_{\mathbf {b}}\)。这将未知数的数量减少到 \(R+ |D|\),使得计算解在计算上变得可行。
4.1.1 Sinkhorn 迭代。
方程 (7) 允许通过执行所谓的 Sinkhorn 迭代来高效地找到 \(\mathbf {T}\)。设 \(s=0,1,...\) 是表示当前迭代的递增索引。我们通过将方程 (7) 代入负载和工作约束方程 (4)–(5) 来执行交错投影:
\[
\begin{align}
q_r^{s+ 1} &= \frac{L}{\sum _{\mathbf {b}}e^{-\mathbf {C}_{r{\mathbf {b}}} / \varepsilon } q_{\mathbf {b}}^s} \; \forall r,
\end{align}
(8)
\[
\begin{align}
q_{\mathbf {b}}^{s+ 1} &= \frac{W_{\mathbf {b}}}{\sum _re^{-\mathbf {C}_{r{\mathbf {b}}} / \varepsilon } q_r^{s+ 1}} \; \forall {\mathbf {b}}.
\end{align}
(9)
方程 (8)–(9) 可以分别看作是一个矩阵-向量乘法和一个向量-向量逐元素除法,因此单次 Sinkhorn 迭代的复杂度为 \(O(R|D|)\)。迭代将线性收敛,作为停止准则,我们使用与方程 (4) 的最大相对偏差:
\[
\begin{equation}
\max _{r}\left|{\frac{\sum _{{\mathbf {b}}}\mathbf {T}_{r{\mathbf {b}}}^s}{L} - 1}\right| \lt \tau _\text{sinkhorn},
\end{equation}
(10)
对于某个用户定义的阈值 \(\tau _\text{sinkhorn}\)。我们通过使用 \(q_r^s\) 和 \(q_{\mathbf {b}}^s\) 来评估方程 (7) 来构建 \(\mathbf {T}^s\)。尽管 \(\mathbf {C}\) 可以从等级和桶的位置即时计算得出,但我们发现预先计算 \(e^{-\mathbf {C}/\varepsilon }\) 并将其存储在一个 \(R\times |D|\) 矩阵中是有益的。
4.1.2 对数域 Sinkhorn 迭代。
较小的正则化参数 \(\varepsilon\) 会产生更尖锐的功率图,但会导致收敛性变差 [Peyré and Cuturi 2019, Remark 4.7];特别是,计算 \(\mathbf {C}/ \varepsilon\) 可能会数值溢出。我们通过检测何时可能发生溢出来解决这个问题(第 4.2.1 节),在这种情况下,我们改用以下对数域计算:
\[
\begin{align}
p_r^{s+ 1} &= p_r^s+ \varepsilon \log L+ \text{\textrm {smoothmin}}_{{\mathbf {b}}} \left(\mathbf {C}_{r{\mathbf {b}}} - p_r^s-p_{\mathbf {b}}^s, \varepsilon \right) \; \forall r,
\end{align}
(11)
\[
\begin{align}
p_{\mathbf {b}}^{s+ 1} &= p_{\mathbf {b}}^s+ \varepsilon \log W_{\mathbf {b}}+ \text{\textrm {smoothmin}}_{r} \left(\mathbf {C}_{r{\mathbf {b}}} - p_{\mathbf {b}}^s- p_r^{s+ 1}, \varepsilon \right) \; \forall {\mathbf {b}},
\end{align}
(12)
对于对数域 Sinkhorn 变量 \(p_\star = \varepsilon \log q_\star , \star \in \lbrace r, {\mathbf {b}}\rbrace\) 和平滑最小值函数
\[
\begin{align}
\text{\textrm {smoothmin}}_{\star }(\mathbf {y}_\star , \varepsilon) = -\varepsilon \log \sum _\star e^{-\mathbf {y}_\star /\varepsilon }.
\end{align}
(13)
方程 (11)–(12) 是方程 (8)–(9) 的对数域等价物,并且对于任意 \(\varepsilon \gt 0\) 和一个好的初始猜测都是稳定的 [Peyré and Cuturi 2019, Remark 4.23];我们使用 \(p_r^0 = 0\) 和 \(p_{\mathbf {b}}^0 = \min _r\mathbf {C}_{r{\mathbf {b}}\) 来保证迭代不会溢出。耦合可以通过以下方式重构:
\[
\begin{equation}
\mathbf {T}_{r{\mathbf {b}}} = e^{\frac{p_r+ p_{\mathbf {b}}- \mathbf {C}_{r{\mathbf {b}}}}{\varepsilon }} \; \forall r, {\mathbf {b}},
\end{equation}
(14)
这是方程 (7) 的对数域等价物。
4.2 来自正则化功率图的分区器
配备了最优耦合矩阵 \(\mathbf {T}\)(方程 (3)–(5)),我们定义分区为:
\[
\begin{equation}
\mathcal {P}({\mathbf {b}}) = \text{\arg \!\max }_r\mathbf {T}_{r{\mathbf {b}}.
\end{equation}
(15)
方程 (15) 将每个桶分配给与其耦合最多的单个等级,由于 \(\mathcal {P}\) 是 D 上的函数,因此根据定义 2.9,这是一个有效的分区。然而,方程 (15) 将最优耦合从连续函数转换为离散函数,因此约束方程 (4)–(5) 可能不再满足。设 \(\mathbf {T}^\mathcal {P}: {[R]}\times D\rightarrow \mathbb {R}_+\) 是这样一个函数:如果 \(r= \mathcal {P}({\mathbf {b}})\) 则其值为 \(W_{\mathbf {b}}\),否则为 0,并考虑每个方程关于 \(\mathbf {T}^\mathcal {P}\) 的情况。
根据构造,有 \(\sum _r\mathbf {T}^\mathcal {P}_{r{\mathbf {b}}} = W_{\mathbf {b}}\),因为每个桶都被分配给一个确切的等级;因此 \(\mathbf {T}^\mathcal {P}\) 满足方程 (5)。等级负载平衡约束方程 (4) 通常不满足,即 \(\sum _{\mathbf {b}}\mathbf {T}^\mathcal {P}_{r{\mathbf {b}}} \ne L\),因为方程 (15) 引起的“舍入”可能导致 \(\mathbf {T}^\mathcal {P}\) 与 \(\mathbf {T}\) 有显著偏差。对于足够大的 \(\varepsilon\) 值,这是显而易见的,因为在极限 \(\varepsilon \rightarrow \infty\) 时,最优耦合 \(\mathbf {T}\) 是每个桶都与每个等级等耦合的最大熵解。实际上,当比率 \(\mathbf {C}/ \varepsilon\) 变小时,误差会变得显著。因此,我们更喜欢等级位于其相应功率单元中心附近的分区,并且使用较小的正则化参数。对于前者,我们采用 Lloyd 的算法 [Lloyd 1982] 并在外循环中迭代地将等级站点移动到工作重心(方程 (6))。完整的分区算法在算法 1 中概述。正则化参数对分区方程 (15) 的影响在图 4 的底部行中可视化。
4.2.1 检查溢出。
当由于方程 (7) 中的指数运算导致 \(\mathbf {C}/ \varepsilon\) 的数值溢出时,问题就会出现,这会使某个特定桶 \({\mathbf {b}}\) 的所有 \(\mathbf {T}_{r{\mathbf {b}} = 0\),从而使方程 (15) 无意义。在 \(\mathbf {C}\) 中最可能导致这种情况的元素是由离其最近等级最远的桶决定的,因为这样的桶与所有等级都相对较远。我们用以下公式表示该值:
\[
\begin{equation}
\Gamma (\mathbf {C}) = \max _{\mathbf {b}}\left(\min _r\mathbf {C}_{r{\mathbf {b}})\).
\end{equation}
(16)
如果 \(e^{-\Gamma (\mathbf {C})/\varepsilon }\) 低于浮点类型的精度,则可能会出现数值问题。我们对所有操作使用 64 位精度,如果 \(e^{-\Gamma (\mathbf {C})/\varepsilon } \lt 10^{-12}\)(方程 (11)–(12)),则回退到对数域 Sinkhorn 迭代(方程 (11)–(12)),否则使用标准 Sinkhorn 迭代(方程 (7)–(9))。
常规的 Sinkhorn 迭代由于方程 (13) 中的逐元素指数运算,计算速度明显快于其对数域对应物,因此保持上述阈值较小是有益的。我们保守地选择了阈值 \(10^{-12}\),并且在我们的所有测试中都没有遇到收敛问题,这表明可能可以进一步降低阈值。
4.2.2 选择正则化参数。
如前所述,较大的正则化参数 \(\varepsilon\) 倾向于产生次优的负载平衡,而较小的参数可能导致数值溢出和 Sinkhorn 算法的性能下降。为了克服这些缺点,我们建议通过 Lloyd 迭代逐渐减小 \(\varepsilon\)。具体来说,我们为第一次 Lloyd 迭代 \(l=1\) 定义正则化参数 \(\varepsilon ^{l}\) 为 \(\Gamma\)(方程 (16)),然后连续以固定因子 \(\eta \in (0, 1)\) 减小它,使得 \(\varepsilon ^1 = \Gamma (\mathbf {C}^1)/E\) 和 \(\varepsilon ^l= \eta \varepsilon ^{l- 1}\),其中 \(E\in \mathbb {R}_+\) 是某个用户定义的参数。这样我们首先对等级位置进行粗略估计,快速将它们移到解决方案的范围内,然后通过更低值的 \(\varepsilon\) 进行更精确的迭代来实现更好的负载平衡。我们发现 \(E= 10\) 和 \(\eta = 2/3\) 在实践中效果很好,并在所有示例中使用了这些值。
4.2.3 分区器收敛标准。
当达到目标负载指数 \(\tau _\text{load}\) 时,我们停止 Lloyd 迭代循环(关于我们的分区指标的解释见第 5.1 节)。我们所有的示例都使用 \(\tau _\text{load}= 0.01\),通常需要 1–3 次 Lloyd 迭代才能达到。我们在图 5 中测试了我们方法在等级之间实现负载平衡的收敛性。
4.2.4 初始化。
我们根据 Qiu 等人 [2022] 的方法估计计算工作量 \(W_{\mathbf {b}}\)。对于混合粒子-单元模拟(图 1 和 6;所有其他示例都是纯体积的),我们将 \(W_{\mathbf {b}}\) 设置为桶中的粒子数量;对于体积模拟,我们将所有桶的工作量 \(W_{\mathbf {b}}\) 设置为常数 1。
桶位置 \(\mathbf {x}_{\mathbf {b}}\) 是通过在桶的范围内选择一个随机(但时间上恒定的)位置来确定的。对于最优耦合 \(\mathbf {T}\) 为给定等级 r 产生(接近)轴对齐的功率单元的域,我们发现这种策略是有益的,例如,选择 \(\mathbf {x}_{\mathbf {b}}\) 为每个桶的中心。使用桶中心,所有位于这样的功率单元 r 边界的桶 \({\mathbf {b}}\) 的 \(\mathbf {T}_{r{\mathbf {b}}\) 将大致相等,使得单个桶难以改变等级,从而导致算法 1 的收敛性较差。增加的位置随机性有助于避免这种退化。
等级位置 \(\mathbf {x}_r\) 在第一个模拟帧中通过在域子集中选择一个随机的 \(\mathbf {x}_{\mathbf {b}}\) 来初始化。对于后续帧,我们通过使用前一个时间步的等级位置来“预热” Lloyd 迭代,从而促进时间步之间的连贯性。
4.2.5 为了效率而进行粗化。
对具有大量桶的域进行分区可能会很耗时,通常可以通过粗化 D 来降低问题复杂性,而不会对分区质量产生不利影响。我们在这里介绍了一种这样的粗化程序,通过引入一个更粗糙的均匀网格(方程 (1)),\(\mathcal {B}_{\Delta _{\text{coarse}}}(\mathbf {x})\),其中 \(\Delta _{\text{coarse}} = \Delta \cdot k\)。这里,k(通常为 2 或 3)将 \(k^3\) 个细桶合并为一个粗单元,k 的选择旨在达到可管理的桶数量。例如,我们在图 10 中的目标是 \(|D^{\text{coarse}}| \approx 64\,000\) 的粗化域。对于每个粗桶,我们将其细成分的工作量相加并平均它们的位置,然后将这些作为新的集合 \(\lbrace W_{\mathbf {b}}^\text{coarse}\rbrace\) 和 \(\lbrace \mathbf {x}_{\mathbf {b}}^\text{coarse}\rbrace\) 存储。这些粗化集合被用作算法 1 的输入,得到的分区被映射回原始桶结构。
4.2.6 管理动态域。
我们的分区器旨在每个时间步运行一次。然而,在单个时间步的计算过程中,域子集也可能发生变化。何时以及如何变化取决于特定的模拟类型和场景;对于我们的流体模拟器,变化可能发生在排放、平流或边界栅格化算法期间。
考虑一个域子集 \(D_t^0\) 和与之相关的分区 \(\mathcal {P}_t= \mathbb {P}(D_t^0)\) 对于特定的模拟时间 t,其中上标 \(^0\) 表示 \(D_t^0\) 是该时间 t 的初始域子集。算法可以通过移除或添加桶来改变域子集,从而创建 \(D_t^1, D_t^2\) 等。每次域发生变化时都进行完全重新划分的成本太高;因此,假设这种增量变化是适度的,我们采取一种启发式方法,将任何新桶分配给它最接近的排名,即
\[
\mathcal {P}_t({\mathbf {b}}) = \text{\arg \!\min }_r\left\Vert \mathbf {x}_r- \mathbf {x}_{\mathbf {b}}\right\Vert _2,\ \textrm {对于}\ {\mathbf {b}}\notin D_t^0。
\]
(17)
从 \(D_t^0\) 中移除桶不会改变划分,因为 \(D_t^0\) 上的划分也是任何子集 \(S\subset D_t^0\) 上的有效划分。在下一个模拟时间 \(t+ {\Delta t}\),我们用上一次的域子集初始化 \(D_{t+ {\Delta t}}^0 = D_t^{\textrm {last}}\),并计算新的划分 \(\mathcal {P}_{t+ {\Delta t}} = \mathbb {P}(D_{t+ {\Delta t}}^0)\)。该过程的概述显示在算法 2.5 中。

评估
设计一个好的划分器的最终目标是减少某些类别模拟的运行时间。性能损失可能来自多个来源,例如次优的局部性、较差的时间一致性或重新划分的成本。此外,从空间启发式方法(如 SFC 和我们的 Power 分划器)得出的划分质量取决于域的几何形状,这强调了需要在代表应用程序的域上评估划分器的必要性。因此,我们在第 5.1 节中引入了一些划分指标,并在第 5.3 节中将这些指标与 VFX 的一些典型模拟场景的运行时间进行了比较。然后,为了确保域形状不是挑选出来的,我们还在大量预先计算的流体模拟缓存序列上使用不同的划分器进行了比较。

5.1 指标
为了评估划分器满足我们目标的有效性,我们定义了几个定量指标。
负载指数。遵循公平的工作目标,我们希望每个排名接收总工作量 \(\sum _{{\mathbf {b}}} W_{\mathbf {b}}\) 的 \(1/R\),我们之前将其引入为期望的工作量 L。因此,我们为给定的划分 \(\mathcal {P}\) 和排名 r 定义负载指数 \(\lambda _\mathcal {P}: {[R]}\rightarrow \mathbb {R}_+\) 作为与 L 的相对偏差
\[
\lambda _\mathcal {P}(r) = \left| \frac{\sum _{{\mathbf {b}}\in \mathcal {P}_r} W_{\mathbf {b}}}{L} - 1 \right|。
\]
(18)
假设 \(W_{\mathbf {b}}\) 反映了处理给定桶所需的实际计算量,接近零的负载指数确保工作在机器之间均匀分配。

从 \(D_t^0\) 中移除桶不会改变划分,因为 \(D_t^0\) 上的划分也是任何子集 \(S\subset D_t^0\) 上的有效划分。在下一个模拟时间 \(t+ {\Delta t}\),我们用上一次的域子集初始化域子集 \(D_{t+ {\Delta t}}^0 = D_t^{\textrm {last}}\),并计算新的划分 \(\mathcal {P}_{t+ {\Delta t}} = \mathbb {P}(D_{t+ {\Delta t}}^0)\)。该过程的概述显示在算法 2.5 中。

5.3 应用实验
在以下部分,我们将使用 \(\mathcal {P}= \lbrace \textrm {SFC, METIS, Power}\rbrace\) 作为相应划分器创建的划分的标签。我们将省略负载指数的介绍(公式 (18)),因为所有划分器在排名上产生的负载大致均匀(即 \(\max _r\lambda _r\lt \tau _\text{load}= 0.01\) 对于所有示例)。除非另有说明,我们总是报告最大的表面指数 \(\max _r\sigma _\mathcal {P}(r)\)(公式 (19))。接下来,我们总结了我们在第 5.3 节中进行的实验,并报告了结果数据,将观察和讨论推迟到第 6 节。然后,为了确保域形状不是挑选出来的,我们还在大量预先计算的流体模拟缓存序列上使用不同的划分器进行了指标比较。

5.1 指标
为了评估划分器在满足我们目标方面的有效性,我们定义了几个定量指标。
负载指数。遵循公平的工作目标,我们希望每个排名接收总工作量 \(\sum _{{\mathbf {b}}} W_{\mathbf {b}}\) 的 \(1/R\),我们之前将其引入为期望的工作量 L。因此,我们为给定的划分 \(\mathcal {P}\) 和排名 r 定义负载指数 \(\lambda _\mathcal {P}: {[R]}\rightarrow \mathbb {R}_+\) 作为与 L 的相对偏差
\[
\lambda _\mathcal {P}(r) = \left| \frac{\sum _{{\mathbf {b}}\in \mathcal {P}_r} W_{\mathbf {b}}}{L} - 1 \right|。
\]
(18)
假设 \(W_{\mathbf {b}}\) 反映了处理给定桶所需的实际计算量,接近零的负载指数确保工作在机器之间均匀分配。

表面指数。任何非平凡的并行化模拟都涉及访问某种形式的邻居数据,在分布式环境中必须在机器之间通信。我们希望有一个指标来反映与此类通信相关的成本,这通常发生在划分的边界处。考虑排名 r 的桶的邻居桶集合,这些桶仍然是域子集 \(D_t\) 的一部分,即 \((\mathcal {T}(P_r)\setminus P_r) \cap D_t\)。我们定义表面指数 \(\sigma _\mathcal {P}: {[R]}\rightarrow \mathbb {R}_+\) 为
\[
\sigma _\mathcal {P}(r) = \frac{|(\mathcal {T}(P_r)\setminus P_r) \cap D_t|}{|P_r|},
\]
(19)
它衡量需要通信到排名 r 的桶的数量相对于它拥有的桶的数量。

时间一致性指数。另一个主要的通信来源是在响应域子集形状的变化时重新计算划分,导致排名之间的数据所有权重新分配。为了衡量这种效应,我们定义了一致性指数 \(\nu : (\mathcal {P}^1, \mathcal {P}^2, S) \rightarrow \mathbb {R}_+\),通过计算在给定桶子集 S 上的划分 \(\mathcal {P}^1\) 和 \(\mathcal {P}^2\) 之间改变排名的桶的相对数量来衡量
\[
\nu (\mathcal {P}^1, \mathcal {P}^2, S) = \frac{|\lbrace {\mathbf {b}}\in S: \mathcal {P}^1({\mathbf {b}}) \ne \mathcal {P}^2({\mathbf {b}}) \rbrace |}{|S|}。
\]
(20)
值为零意味着划分保持不变,因此不需要在排名之间传输数据;较大的值相应地反映了增加的传输成本。

在实践中,我们感兴趣的是跟踪划分随时间的一致性,或者更具体地说,是在连续的模拟时间步之间的稳定性。在我们的实现中,每次在 \(D^0_t\) 上进行模拟时,都会重新划分 \(\mathcal {P}_{t} = \mathbb {P}(D^0_t)\),并将其与之前的划分 \(\mathcal {P}_{t- {\Delta t}} = \mathbb {P}(D^0_{t- {\Delta t}}\) 进行比较,其中根据第 4.2.6 节已经添加了任何新桶。我们设置 \(S= D_t^0 = D_{t-{\Delta t}}^\textrm {last}\),因为这两种配置在内存中分配了相同的桶集,因此该指标值将指示传输成本。时间一致性的可视化显示在图 3.5 中。

5.2 与其他划分器的比较
我们进行了与 METIS 和 SFC 的比较,它们是常见的最先进的划分技术。下面介绍了如何将这些技术适应我们的稀疏域框架的相关细节。特别是,我们处理了动态桶的创建和删除,如第 4.2.6 节所述,不同之处在于,我们使用平均桶位置 \(\mathbf {x}_r= \sum _{{\mathbf {b}}\in P_r} \mathbf {x}_{\mathbf {b}}/ |P_r|\) 代替公式 (17) 中的排名位置 \(\mathbf {x}_r\),该位置在每次调用划分器后立即计算和存储。

SFC。为了对稀疏网格域 \(D_t\) 进行划分,将域嵌入到一个边界立方体中。然后将其划分为 \(n \times n \times n\) 个子盒子,并应用 SFC,其中 n 是 2 的幂。通常,对于我们的应用程序来说,1024 就足够了。从算法上讲,这意味着为每个子盒子分配一个从 0 到 \(n^3-1\) 的唯一索引,对应于其沿曲线的位置——这是 Hilbert、Morton (Z-order) 和其他 SFC 的既定程序——以便所有子盒子按长度为 \(n^3\) 的一维数组排序。然后根据邻近性将域 \(D_t\) 的桶映射到子盒子中,从而也将前者按一维数组排序。这个一维桶数组被划分为 R 个连续的区间,以便在排名之间分配。Tsuzuki 和 Aoki [2016] 提供了这种方法的进一步细节。我们对所有 SFC 测试使用了 Hilbert 曲线。

METIS。我们通过构建域的图 G 来利用 METIS,使用 \(D_t\) 作为顶点,\(\mathcal {N}\) 来创建边。然后我们将 G 传递给 METIS_PartGraphRecursive [Karypis 2013],它返回一个图划分,我们将其映射回 \(D_t\)。

5.3 应用实验
在以下部分,我们将使用 \(\mathcal {P}= \lbrace \textrm {SFC, METIS, Power}\rbrace\) 作为相应划分器创建的划分的标签。我们将省略负载指数的介绍(公式 (18)),因为所有划分器在排名上产生的负载大致均匀(即,\(\max _r\lambda _r\lt \tau _\text{load}= 0.01\) 对于所有示例)。除非另有说明,我们总是报告最大的表面指数 \(\max _r\sigma _\mathcal {P}(r)\)(公式 (19))。接下来,我们总结了我们在第 5.3 节中进行的实验,并报告了结果数据,将观察和讨论推迟到第 6 节。然后,为了确保域形状不是挑选出来的,我们还在大量预先计算的流体模拟缓存序列上使用不同的划分器进行了指标比较。

5.1 指标
为了评估划分器在满足我们目标方面的有效性,我们定义了几个定量指标。
负载指数。遵循公平的工作目标,我们希望每个排名接收总工作量 \(\sum _{{\mathbf {b}}} W_{\mathbf {b}}\) 的 \(1/R\),我们之前将其引入为期望的工作量 L。因此,我们为给定的划分 \(\mathcal {P}\) 和排名 r 定义负载指数 \(\lambda _\mathcal {P}: {[R]}\rightarrow \mathbb {R}_+\) 作为与 L 的相对偏差
\[
\lambda _\mathcal {P}(r) = \left| \frac{\sum _{{\mathbf {b}}\in \mathcal {P}_r} W_{\mathbf {b}}}{L} - 1 \right|。
\]
(18)
假设 \(W_{\mathbf {b}}\) 反映了处理给定桶所需的实际计算量,接近零的负载指数确保工作在机器之间均匀分配。

表面指数。任何非平凡的并行化模拟都涉及访问某种形式的邻居数据,在分布式环境中必须在机器之间通信。我们希望有一个指标来反映与此类通信相关的成本,这通常发生在划分的边界处。考虑排名 r 的桶的邻居桶集合,这些桶仍然是域子集 \(D_t\) 的一部分,即 \((\mathcal {T}(P_r)\setminus P_r) \cap D_t\)。我们定义表面指数 \(\sigma _\mathcal {P}: {[R]}\rightarrow \mathbb {R}_+\) 为
\[
\sigma _\mathcal {P}(r) = \frac{|(\mathcal {T}(P_r)\setminus P_r) \cap D_t|}{|P_r|},
\]
(19)
它衡量需要通信到排名 r 的桶的数量相对于它拥有的桶的数量。

时间一致性指数。另一个主要的通信来源是在响应域子集形状的变化时重新计算划分,导致排名之间的数据所有权重新分配。为了衡量这种效应,我们定义了一致性指数 \(\nu : (\mathcal {P}^1, \mathcal {P}^2, S) \rightarrow \mathbb {R}_+\),通过计算在给定桶子集 S 上的划分 \(\mathcal {P}^1\) 和 \(\mathcal {P}^2\) 之间改变排名的桶的相对数量来衡量
\[
\nu (\mathcal {P}^1, \mathcal {P}^2, S) = \frac{|\lbrace {\mathbf {b}}\in S: \mathcal {P}^1({\mathbf {b}}) \ne \mathcal {P}^2({\mathbf {b}}) \rbrace |}{|S|}。
\]
(20)
值为零意味着划分保持不变,因此不需要在排名之间传输数据;较大的值相应地反映了增加的传输成本。

在实践中,我们感兴趣的是跟踪划分随时间的一致性,或者更具体地说,是在连续的模拟时间步之间的稳定性。在我们的实现中,每次在 \(D^0_t\) 上进行模拟时,都会重新划分 \(\mathcal {P}_{t} = \mathbb {P}(D^0_t)\),并将其与之前的划分 \(\mathcal {P}_{t- {\Delta t}} = \mathbb {P}(D^0_{t- {\Delta t}}\) 进行比较,其中根据第 4.2.6 节已经添加了任何新桶。我们设置 \(S= D_t^0 = D_{t-{\Delta t}}^\textrm {last}\),因为这两种配置在内存中分配了相同的桶集,因此该指标值将指示传输成本。时间一致性的可视化显示在图 3.5 中。

5.2 与其他划分器的比较
我们进行了与 METIS 和 SFC 的比较,它们是常见的最先进的划分技术。下面介绍了如何将这些技术适应我们的稀疏域框架的相关细节。特别是,我们处理了动态桶的创建和删除,如第 4.2.6 节所述,不同之处在于,我们使用平均桶位置 \(\mathbf {x}_r= \sum _{{\mathbf {b}}\in P_r} \mathbf {x}_{\mathbf {b}}/ |P_r|\) 代替公式 (17) 中的排名位置 \(\mathbf {x}_r\),该位置在每次调用划分器后立即计算和存储。

SFC。为了对稀疏网格域 \(D_t\) 进行划分,将域嵌入到一个边界立方体中。然后将其划分为 \(n \times n \times n\) 个子盒子,并应用 SFC,其中 n 是 2 的幂。通常,对于我们的应用程序来说,1024 就足够了。从算法上讲,这意味着为每个子盒子分配一个从 0 到 \(n^3-1\) 的唯一索引,对应于其沿曲线的位置——这是 Hilbert、Morton (Z-order) 和其他 SFC 的既定程序——以便所有子盒子按长度为 \(n^3\) 的一维数组排序。然后根据邻近性将域 \(D_t\) 的桶映射到子盒子中,从而也将前者按一维数组排序。这个一维桶数组被划分为 R 个连续的区间,以便在排名之间分配。Tsuzuki 和 Aoki [2016] 提供了这种方法的进一步细节。我们对所有 SFC 测试使用了 Hilbert 曲线。

METIS。我们通过构建域的图 G 来利用 METIS,使用 \(D_t\) 作为顶点,\(\mathcal {N}\) 来创建边。然后我们将 G 传递给 METIS_PartGraphRecursive [Karypis 2013],它返回一个图划分,我们将其映射回 \(D_t\)。

5.3 应用实验
在以下部分,我们将使用 \(\mathcal {P}= \lbrace \textrm {SFC, METIS, Power}\rbrace\) 作为相应划分器创建的划分的标签。我们将省略负载指数的介绍(公式 (18)),因为所有划分器在排名上产生的负载大致均匀(即,\(\max _r\lambda _r\lt \tau _\text{load}= 0.01\) 对于所有示例)。除非另有说明,我们总是报告最大的表面指数 \(\max _r\sigma _\mathcal {P}(r)\)(公式 (19))。接下来,我们总结了我们在第 5.3 节中进行的实验,并报告了结果数据,将观察和讨论推迟到第 6 节。然后,为了确保域形状不是挑选出来的,我们还在大量预先计算的流体模拟缓存序列上使用不同的划分器进行了指标比较。

5.1 指标
为了评估划分器在满足我们目标方面的有效性,我们定义了几个定量指标。
负载指数。遵循公平的工作目标,我们希望每个排名接收总工作量 \(\sum _{{\mathbf {b}}} W_{\mathbf {b}}\) 的 \(1/R\),我们之前将其引入为期望的工作量 L。因此,我们为给定的划分 \(\mathcal {P}\) 和排名 r 定义负载指数 \(\lambda _\mathcal {P}: {[R]}\rightarrow \mathbb {R}_+\) 作为与 L 的相对偏差
\[
\lambda _\mathcal {P}(r) = \left| \frac{\sum _{{\mathbf {b}}\in \mathcal {P}_r} W_{\mathbf {b}}}{L} - 1 \right|。
\]
(18)
假设 \(W_{\mathbf {b}}\) 反映了处理给定桶所需的实际计算量,接近零的负载指数确保工作在机器之间均匀分配。

表面指数。任何非平凡的并行化模拟都涉及访问某种形式的邻居数据,在分布式环境中必须在机器之间通信。我们希望有一个指标来反映与此类通信相关的成本,这通常发生在划分的边界处。考虑排名 r 的桶的邻居桶集合,这些桶仍然是域子集 \(D_t\) 的一部分,即 \((\mathcal {T}(P_r)\setminus P_r) \cap D_t\)。我们定义表面指数 \(\sigma _\mathcal {P}: {[R]}\rightarrow \mathbb {R}_+\) 为
\[
\sigma _\mathcal {P}(r) = \frac{|(\mathcal {T}(P_r)\setminus P_r) \cap D_t|}{|P_r|},
\]
(19)
它衡量需要通信到排名 r 的桶的数量相对于它拥有的桶的数量。

时间一致性指数。另一个主要的通信来源是在响应域子集形状的变化时重新计算划分,导致排名之间的数据所有权重新分配。为了衡量这种效应,我们定义了一致性指数 \(\nu : (\mathcal {P}^1, \mathcal {P}^2, S) \rightarrow \mathbb {R}_+\),通过计算在给定桶子集 S 上的划分 \(\mathcal {P}^1\) 和 \(\mathcal {P}^2\) 之间改变排名的桶的相对数量来衡量
\[
\nu (\mathcal {P}^1, \mathcal {P}^2, S) = \frac{|\lbrace {\mathbf {b}}\in S: \mathcal {P}^1({\mathbf {b}}) \ne \mathcal {P}^2({\mathbf {b}}) \rbrace |}{|S|}。
\]
(20)
值为零意味着划分保持不变,因此不需要在排名之间传输数据;较大的值相应地反映了增加的传输成本。

在实践中,我们感兴趣的是跟踪划分随时间的一致性,或者更具体地说,是在连续的模拟时间步之间的稳定性。在我们的实现中,每次在 \(D^0_t\) 上进行模拟时,都会重新划分 \(\mathcal {P}_{t} = \mathbb {P}(D^0_t)\),并将其与之前的划分 \(\mathcal {P}_{t- {\Delta t}} = \mathbb {P}(D^0_{t- {\Delta t}}\) 进行比较,其中根据第 4.2.6 节已经添加了任何新桶。我们设置 \(S= D_t^0 = D_{t-{\Delta t}}^\textrm {last}\),因为这两种配置在内存中分配了相同的桶集,因此该指标值将指示传输成本。时间一致性的可视化显示在图 3.5 中。

5.2 与其他划分器的比较
我们进行了与 METIS 和 SFC 的比较,它们是常见的最先进的划分技术。下面介绍了如何将这些技术适应我们的稀疏域框架的相关细节。特别是,我们处理了动态桶的创建和删除,如第 4.2.6 节所述,不同之处在于,我们使用平均桶位置 \(\mathbf {x}_r= \sum _{{\mathbf {b}}\in P_r} \mathbf {x}_{\mathbf {b}}/ |P_r|\) 代替公式 (17) 中的排名位置 \(\mathbf {x}_r\),该位置在每次调用划分器后立即计算和存储。

SFC。为了对稀疏网格域 \(D_t\) 进行划分,将域嵌入到一个边界立方体中。然后将其划分为 \(n \times n \times n\) 个子盒子,并应用 SFC,其中 n 是 2 的幂。通常,对于我们的应用程序来说,1024 就足够了。从算法上讲,这意味着为每个子盒子分配一个从 0 到 \(n^3-1\) 的唯一索引,对应于其沿曲线的位置——这是 Hilbert、Morton (Z-order) 和其他 SFC 的既定程序——以便所有子盒子按长度为 \(n^3\) 的一维数组排序。然后根据邻近性将域 \(D_t\) 的桶映射到子盒子中,从而也将前者按一维数组排序。这个一维桶数组被划分为 R 个连续的区间,以便在排名之间分配。Tsuzuki 和 Aoki [2016] 提供了这种方法的进一步细节。我们对所有 SFC 测试使用了 Hilbert 曲线。

METIS。我们通过构建域的图 G 来利用 METIS,使用 \(D_t\) 作为顶点,\(\mathcal {N}\) 来创建边。然后我们将 G 传递给 METIS_PartGraphRecursive [Karypis 2013],它返回一个图划分,我们将其映射回 \(D_t\)。

5.3 应用实验
在以下部分,我们将使用 \(\mathcal {P}= \lbrace \textrm {SFC, METIS, Power}\rbrace\) 作为相应划分器创建的划分的标签。我们将省略负载指数的介绍(公式 (18),因为所有划分器在排名上产生的负载大致均匀(即,\(\max _r\lambda _r\lt \tau _\text{load}= 0.01\) 对于所有示例)。除非另有说明,我们总是报告最大的表面指数 \(\max _r\sigma _\mathcal {P}(r)\)(公式 (19))。接下来,我们总结了我们在第 5.3 节中进行的实验,并报告了结果数据,将观察和讨论推迟到第 6 节。然后,为了确保域形状不是挑选出来的,我们还在大量预先计算的流体模拟缓存序列上使用不同的划分器进行了指标比较。

5.1 指标
为了评估划分器在满足我们目标方面的有效性,我们定义了几个定量指标。
负载指数。遵循公平的工作目标,我们希望每个排名接收总工作量 \(\sum _{{\mathbf {b}}} W_{\mathbf {b}}\) 的 \(1/R\),我们之前将其引入为期望的工作量 L。因此,我们为给定的划分 \(\mathcal {P}\) 和排名 r 定义负载指数 \(\lambda _\mathcal {P}: {[R]}\rightarrow \mathbb {R}_+\) 作为与 L 的相对偏差
\[
\lambda _\mathcal {P}(r) = \left| \frac{\sum _{{\mathbf {b}}\in \mathcal {P}_r} W_{\mathbf {b}}}{L} - 1 \right|。
\]
(18)
假设 \(W_{\mathbf {b}}\) 反映了处理给定桶所需的实际计算量,接近零的负载指数确保工作在机器之间均匀分配。

表面指数。任何非平凡的并行化模拟都涉及访问某种形式的邻居数据,在分布式环境中必须在机器之间通信。我们希望有一个指标来反映与此类通信相关的成本,这通常发生在划分的边界处。考虑排名 r 的桶的邻居桶集合,这些桶仍然是域子集 \(D_t\) 的一部分,即 \((\mathcal {T}(P_r)\setminus P_r) \cap D_t\)。我们定义表面指数 \(\sigma _\mathcal {P}: {[R]}\rightarrow \mathbb {R}_+\) 为
\[
\sigma _\mathcal {P}(r) = \frac{|(\mathcal {T}(P_r)\setminus P_r) \cap D_t|}{|P_r|},
\]
(19)
它衡量需要通信到排名 r 的桶的数量相对于它拥有的桶的数量。

时间一致性指数。另一个主要的通信来源是在响应域子集形状的变化时重新计算划分,导致排名之间的数据所有权重新分配。为了衡量这种效应,我们定义了一致性指数 \(\nu : (\mathcal {P}^1, \mathcal {P}^2, S) \rightarrow \mathbb {R}_+\),通过计算在给定桶子集 S 上的划分 \(\mathcal {P}^1\) 和 \(\mathcal {P}^2\) 之间改变排名的桶的相对数量来衡量
\[
\nu (\mathcal {P}^1, \mathcal {P}^2, S) = \frac{|\lbrace {\mathbf {b}}\in S: \mathcal {P}^1({\mathbf {b}}) \ne \mathcal {P}^2({\mathbf {b}}) \rbrace |}{|S|}。
\]
(20)
值为零意味着划分保持不变,因此不需要在排名之间传输数据;较大的值相应地反映了增加的传输成本。

在实践中,我们感兴趣的是跟踪划分随时间的一致性,或者更具体地说,是在连续的模拟时间步之间的稳定性。在我们的实现中,每次在 \(D^0_t\) 上进行模拟时,都会重新划分 \(\mathcal {P}_{t} = \mathbb {P}(D^0_t)\),并将其与之前的划分 \(\mathcal {P}_{t- {\Delta t}} = \mathbb {P}(D^0_{t- {\Delta t}}\) 进行比较,其中根据第 4.2.6 节已经添加了任何新桶。我们设置 \(S= D_t^0 = D_{t-{\Delta t}}^\textrm {last}\),因为这两种配置在内存中分配了相同的桶集,因此该指标值将指示传输成本。时间一致性的可视化显示在图 3.5 中。

5.2 与其他划分器的比较
我们进行了与 METIS 和 SFC 的比较,它们是常见的最先进的划分技术。下面介绍了如何将这些技术适应我们的稀疏域框架的相关细节。特别是,我们处理了动态桶的创建和删除,如第 4.2.6 节所述,不同之处在于,我们使用平均桶位置 \(\mathbf {x}_r= \sum _{{\mathbf {b}}\in P_r} \mathbf {x}_{\mathbf {b}}/ |P_r|\) 代替公式 (17) 中的排名位置 \(\mathbf {x}_r\),该位置在每次调用划分器后立即计算和存储。

SFC。为了对稀疏网格域 \(D_t\) 进行划分,将域嵌入到一个边界立方体中。然后将其划分为 \(n \times n \times n\) 个子盒子,并应用 SFC,其中 n 是 2 的幂。通常,对于我们的应用程序来说,1024 就足够了。从算法上讲,这意味着为每个子盒子分配一个从 0 到 \(n^3-1\) 的唯一索引,对应于其沿曲线的位置——这是 Hilbert、Morton (Z-order) 和其他 SFC 的既定程序——以便所有子盒子按长度为 \(n^3\) 的一维数组排序。然后根据邻近性将域 \(D_t\) 的桶映射到子盒子中,从而也将前者按一维数组排序。这个一维桶数组被划分为 R 个连续的区间,以便在排名之间分配。Tsuzuki 和 Aoki [2016] 提供了这种方法的进一步细节。我们对所有 SFC 测试使用了 Hilbert 曲线。

METIS。我们通过构建域的图 G 来利用 METIS,使用 \(D_t\) 作为顶点,\(\mathcal {N}\) 来创建边。然后我们将 G 传递给 METIS_PartGraphRecursive [Karypis 2013],它返回一个图划分,我们将其映射回 \(D_t\)。

5.3 应用实验
在以下部分,我们将使用 \(\mathcal {P}= \lbrace \textrm {SFC, METIS, Power}\rbrace\) 作为相应划分器创建的划分的标签。我们将省略负载指数的介绍(公式 (18),因为所有划分器在排名上产生的负载大致均匀(即,\(\max _r\lambda _r\lt \tau _\text{load}= 0.01\) 对于所有示例)。除非另有说明,我们总是报告最大的表面指数 \(\max _r\sigma _\mathcal {P}(r)\)(公式 (19))。接下来,我们总结了我们在第 5.3 节中进行的实验,并报告了结果数据,将观察和讨论推迟到第 6 节。然后,为了确保域形状不是挑选出来的,我们还在大量预先计算的流体模拟缓存序列上使用不同的划分器进行了指标比较。

5.1 指标
为了评估划分器在满足我们目标方面的有效性,我们定义了几个定量指标。
负载指数。遵循公平的工作目标,我们希望每个排名接收总工作量 \(\sum _{{\mathbf {b}}} W_{\mathbf {b}}\) 的 \(1/R\),我们之前将其引入为期望的工作量 L。因此,我们为给定的划分 \(\mathcal {P}\) 和排名 r 定义负载指数 \(\lambda _\mathcal {P}: {[R]}\rightarrow \mathbb {R}_+\) 作为与 L 的相对偏差
\[
\lambda _\mathcal {P}(r) = \left| \frac{\sum _{{\mathbf {b}}\in \mathcal {P}_r} W_{\mathbf {b}}}{L} - 1 \right|。
\]
(18)
假设 \(W_{\mathbf {b}}\) 反映了处理给定桶所需的实际计算量,接近零的负载指数确保工作在机器之间均匀分配。

表面指数。任何非平凡的并行化模拟都涉及访问某种形式的邻居数据,在分布式环境中必须在机器之间通信。我们希望有一个指标来反映与此类通信相关的成本,这通常发生在划分的边界处。考虑排名 r 的桶的邻居桶集合,这些桶仍然是域子集 \(D_t\) 的一部分,即 \((\mathcal {T}(P_r)\setminus P_r) \cap D_t\)。我们定义表面指数 \(\sigma _\mathcal {P}: {[R]}\rightarrow \mathbb {R}_+\) 为
\[
\sigma _\mathcal {P}(r) = \frac{|(\mathcal {T}(P_r)\setminus P_r) \cap D_t|}{|P_r|},
\]
(19)
它衡量需要通信到排名 r 的桶的数量相对于它拥有的桶的数量。

时间一致性指数。另一个主要的通信来源是在响应域子集形状的变化时重新计算划分,导致排名之间的数据所有权重新分配。为了衡量这种效应,我们定义了一致性指数 \(\nu : (\mathcal {P}^1, \mathcal {P}^2, S) \rightarrow \mathbb {R}_+\),通过计算在给定桶子集 S 上的划分 \(\mathcal {P}^1\) 和 \(\mathcal {P}^2\) 之间改变排名的桶的相对数量来衡量
\[
\nu (\mathcal {P}^1, \mathcal {P}^2, S) = \frac{|\lbrace {\mathbf {b}}\in S: \mathcal {P}^1({\mathbf {b}}) \ne \mathcal {P}^2({\mathbf {b}}) \rbrace |}{|S|}。
\]
(20)
值为零意味着划分保持不变,因此不需要在排名之间传输数据;较大的值相应地反映了增加的传输成本。

在实践中,我们感兴趣的是跟踪划分随时间的一致性,或者更具体地说,是在连续的模拟时间步之间的稳定性。在我们的实现中,每次在 \(D^0_t\) 上进行模拟时,都会重新划分 \(\mathcal {P}_{t} = \mathbb {P}(D^0_t)\),并将其与之前的划分 \(\mathcal {P}_{t- {\Delta t}} = \mathbb {P}(D^0_{t- {\Delta t}}\) 进行比较,其中根据第 4.2.6 节已经添加了任何新桶。我们设置 \(S= D_t^0 = D_{t-{\Delta t}}^\textrm {last}\),因为这两种配置在内存中分配了相同的桶集,因此该指标值将指示传输成本。时间一致性的可视化显示在图 3.5 中。

5.2 与其他划分器的比较
我们进行了与 METIS 和 SFC 的比较,它们是常见的最先进的划分技术。下面介绍了如何将这些技术适应我们的稀疏域框架的相关细节。特别是,我们处理了动态桶的创建和删除,如第 4.2.6 节所述,不同之处在于,我们使用平均桶位置 \(\mathbf {x}_r= \sum _{{\mathbf {b}}\in P_r} \mathbf {x}_{\mathbf {b}}/ |P_r|\) 代替公式 (17) 中的排名位置 \(\mathbf {x}_r\),该位置在每次调用划分器后立即计算和存储。

SFC。为了对稀疏网格域 \(D_t\) 进行划分,将域嵌入到一个边界立方体中。然后将其划分为 \(n \times n \times n\) 个子盒子,并应用 SFC,其中 n 是 2 的幂。通常,对于我们的应用程序来说,1024 就足够了。从算法上讲,这意味着为每个子盒子分配一个从 0 到 \(n^3-1\) 的唯一索引,对应于其沿曲线的位置——这是 Hilbert、Morton (Z-order) 和其他 SFC 的既定程序——以便所有子盒子按长度为 \(n^3\) 的一维数组排序。然后根据邻近性将域 \(D_t\) 的桶映射到子盒子中,从而也将前者按一维数组排序。这个一维桶数组被划分为 R 个连续的区间,以便在排名之间分配。Tsuzuki 和 Aoki [2016] 提供了这种方法的进一步细节。我们对所有 SFC 测试使用了 Hilbert 曲线。

METIS。我们通过构建域的图 G 来利用 METIS,使用 \(D_t\) 作为顶点,\(\mathcal {N}\) 来创建边。然后我们将 G 传递给 METIS_PartGraphRecursive [Karypis 2013],它返回一个图划分,我们将其映射回 \(D_t\)。

5.3 应用实验
在以下部分,我们将使用 \(\mathcal {P}= \lbrace \textrm {SFC, METIS, Power}\rbrace\) 作为相应划分器创建的划分的标签。我们将省略负载指数的介绍(公式 (18),因为所有划分器在排名上产生的负载大致均匀(即,\(\max _r\lambda _r\lt \tau _\text{load}= 0.01\) 对于所有示例)。除非另有说明,我们总是报告最大的表面指数 \(\max _r\sigma _\mathcal {P}(r)\)(公式 (19))。接下来,我们总结了我们在第 5.3 节中进行的实验,并报告了结果数据,将观察和讨论推迟到第 6 节。然后,为了确保域形状不是挑选出来的,我们还在大量预先计算的流体模拟缓存序列上使用不同的划分器进行了指标比较。对于每个缓存序列,我们确定了具有最多桶的帧(\(\max _t|D_t|\),并选择了排名数量 \(R= \max _t|D_t|/50\textrm {k}\),将其四舍五入到最接近的 \(2^n\) 的倍数作为整个序列的排名。对于每个帧+分区器的组合,我们计算了时间索引,并记录了所有排名中的最大表面索引。为了消除与各种域大小和拓扑结构相关的噪声和缩放效应,这些因素导致索引的幅度差异巨大,我们计算了相对值 SFC/Power 和 METIS/Power,并将它们组织在直方图中,见图 7。汇总值显示在表 2 中。

战斗场景。我们从语料库中突出展示了一个特别具有挑战性的缓存序列:来自《阿凡达:水之道》的水模拟镜头,如图 1 所示。在这个极其混乱的场景中,Power 分区器在表面和时间指标上均优于 METIS 和 SFC(见表 2)。

船尾流和火焰喷射器。最后,我们在两个常见的 VFX 模拟场景中比较了不同的分区器。首先,使用混合粒子-单元方法 [Fu et al. 2017a] 模拟了平面上移动的船只,并逐渐扩展模拟域以捕捉产生的尾流(见图 6)。其次,我们使用基于物理的燃烧模型 [Edholm et al. 2023] 创建了一个移动的火焰喷射器(见图 9)。运行时间和指标在表 2.6 中报告。

讨论

我们在一系列具有挑战性的场景中评估了我们基于最优传输的新 Power 分区算法,证明了其在处理稀疏动态域配置方面的显著进步,运行时间加速高达 70%(例如,“船尾流”,表 2)。

时间一致性。当对模拟语料库进行平均时(见图 7),Power 分区器在时间属性上优于 SFC(9.34倍)和 METIS(505倍)。值得注意的是,METIS 在每个模拟步骤中平均重新排列了 57% 的域子集(见表 2),这使得它不适用于稀疏动态域。

与重新分区相关的数据传输可能会导致显著的性能损失。例如,在图 8 中,有多个实例表明,使用 METIS 时,重新分区的传输时间比同一时间步长的总幽灵(即邻居)传输时间更长。此外,在船尾流示例(图 6)中,由于 SFC 和 Power 的时间一致性指数较低,它们的模拟速度明显快于 METIS,同时它们的平均表面指数更高。重要的是,与幽灵传输相比,重新分区难以异步执行,因此成为模拟代码中的一个瓶颈部分。

我们方法的高时间一致性是两个关键方面的结果。首先是方程(3)中的正则化项,它确保了存在一个唯一的(正则化的)最优耦合 \(\mathbf {T}\);其次是我们的 \(\mathbf {x}_r\) 的预热程序。在 Lloyd 迭代过程中逐步减小 \(\varepsilon\)(第 4.2.2 节)确保了快速收敛到最优耦合,当通过方程(15)转换为分区时,满足了目标负载阈值(第 4.2.3 节)。由此产生的分区使得功率单元随时间平滑演变,即使模拟域经历了大的拓扑变化。图 5 中的收敛研究支持了我们方法的可靠性,尽管我们缺乏正式的收敛证明。虽然我们将 Lloyd 迭代次数限制在 10 次以内,但通常在 1-3 次迭代内就能达到我们的目标负载阈值 \(\tau _\text{load}= 0.01\)。为了使 \(\mathcal {P}\) 成为 \(\mathbf {T}\) 的良好近似(通过方程(15)),我们在所有示例中设置了 \(\tau _\text{sinkhorn}= 0.5 \tau _\text{load}\)(方程(10))。

算法 1 中 Lloyd 迭代的一个有益副作用是,分区倾向于大致朝向质心功率单元,尽管只是间接的,因为终止条件仅基于 \(\tau _\text{load}\)。可以引入一个额外的标准来明确限制 \(\left\Vert \mathbf {x}_r- \mathbf {c}_r\right\Vert\),但这通常会增加 Lloyd 迭代的次数。虽然更多的质心功率单元可以略微提高空间局部性,因为它们的形状往往更紧凑,但在我们的实验中,由此产生的传输时间减少是微不足道的,并不值得额外的迭代成本。

METIS 在所有测试中产生的分区都具有最高的空间局部性,这通过低表面指数(表 2-3)可以看出。这并不奇怪:METIS 通过 \(\mathcal {N}\) 接收到域的拓扑信息,而 Power 和 SFC 则没有。尽管如此,Power 分区器能够接近最优地划分许多具有挑战性和非凸形的场景,例如新月形(图 3)和河流(图 10,左侧)。

重要的是,与 SFC 相比,Power 分区器产生的分区更加稳健。考虑图 8 中使用 SFC 的静止帧分区(从顶部数第二行)。由于 SFC 嵌入到一个边界立方体中,域的微小旋转可能会对分区质量产生灾难性影响。

请注意,表面指数与幽灵数据传输量之间的关系在实践中并非简单明了。它取决于模拟器的实现细节,因为各个算法的数据访问模式以及桶数据内存布局决定了必须传输哪些数据以及何时传输。在这项工作中,我们没有尝试推导出精确的关系,而是提供了表 5-4 中的时间分解。

性能。随着 \(R\times |D|\) 的增长,Power 分区器的计算时间会恶化,这是由于 Sinkhorn 解法(方程(8)–(9)或对数域 Sinkhorn 解法(方程(11)–(12))中的密集矩阵-向量乘法造成的。我们发现一个简单的粗化程序(第 4.2.5 节)可以缓解这个问题(见图 10),确保分区所需的时间不到模拟时间的 2%,即使对于 \(R= 32\) 和 \(|D| \approx 2\)M 也是如此(具体数字见表 3 和 4)。有趣的是,粗化后的 Power 分区器有时会产生比未粗化版本更低的表面指数(见图 10),我们认为这是由于粗化创造了有益的邻居模式。原则上,可以根据正则化参数调整粗化级别,选择与 \(\varepsilon\) 引起的最优耦合的“模糊”相匹配的桶大小。由于我们典型问题的规模在 \(R\lt 10\) 和 \(|D| \lt 1\)M 之内,我们发现实际上并不需要粗化,我们将这种粗化策略的探索留待未来的工作。

我们的求解器的扩展性,无论是强扩展性(图 8)还是弱扩展性(图 10),按照超级计算的标准来看都是次优的。我们将这部分归因于幽灵传输通信,我们通过阻塞调用来实现通信,以确保能够准确测量通信与计算所花费的时间。然而,异步重叠的通信和计算不太可能隐藏所有的通信成本,因为许多在 VFX 中常用的算法都是内存受限的。因此,对高质量分区器的需求仍然很重要。

7 结论

我们提出的分区算法利用最优传输来生成基于域中工作分布的功率图,显著提高了 VFX 应用中大规模基于物理的模拟的分布效率。我们在真实世界的生产场景中评估了我们的方法,这些场景具有高度动态的域拓扑结构,分布在稀疏和非凸形域上。为了分析分区的质量,我们引入了表面指数和时间一致性指数,并分析了我们的方法对模拟运行时间的影响。图 7 中的研究表明,与 SFC 和 METIS 相比,时间指数有了显著改进。表面指数比 SFC 有显著提高,而略低于 METIS。总体而言,我们提出的方法在我们最初提出的定性目标上取得了良好的平衡,通常在总运行时间上优于 METIS 和 SFC。
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号