floating-point - 处理 OpenCL 粒子系统中浮点精度不足的问题

Question

我正在编写一个基于 OpenCL 的粒子系统来加速大规模网络的可视化。从本质上讲，这是一个两相问题，其中第一阶段对每个粒子施加负引力(典型的 n 体问题)，因此它们都相互排斥，第二阶段然后根据粒子之间的边缘(或 Spring )吸引粒子。

在重力算法的每次迭代中，每个粒子的位置(表示为一对 float )受到彼此粒子的距离的影响(经典物理模型，无阻力，保持简单)。

在具有完美间隔的正方形粒子阵列的情况下，重力的应用应该导致 X 轴和 Y 轴对称。这在重力应用的开始是正确的，但随着时间的推移，将大量 float 相加时固有的精度不足会导致小的不均匀偏差。这反过来传播到整个 n 体系统，并发生对称性损失。

避免这种情况的一种简单方法是使用 double 字，但是我的 MacBook Pro 上的 GeForce 9600M GT 不支持 double 字。那么，在 OpenCL 中处理此类问题的好方法是什么？我考虑过将要添加的 float 截断到几位小数来避免这个问题，但这似乎有点矫揉造作。

Answer 1

您已经解决了数值分析领域的大部分基础问题；您应该准备阅读一些有关通常如何处理这些问题的资料。

首先，如果您的问题具有对称性，您可以利用它来减少所需的计算量，并消除由于数值错误而导致的任何自发的对称性破坏。

其次，意识到即使在处理相同的有限精度时，并非所有算法都是平等的:一些算法更多 numerically stable相对于其它的。使用更高精度的算法并不能消除数值不稳定性，它只会使它需要更长的时间才能变得明显。您的重力模拟当前很可能实现了等同于 Euler's Method 的东西。 .在不切换到 double 的情况下，您可以使用高阶方法(例如 Runge-Kutta)使您的模拟更加稳定/准确。 .

最后，听起来你在做 force-directed graph layout .简单地向前运行物理模拟很容易只找到局部最优，高度依赖于起始位置，并且(如您所发现的)通常非常不稳定。链接的 wiki 页面提到了其他几种可以更好地解决问题的方法。