计算成本是多少X--√x在标准库中?

计算科学 效率
2021-11-28 20:37:10

我们在分子模拟中必须处理的主要问题之一是距离相关力的计算。如果我们可以将力和距离函数限制为具有间隔距离的均匀幂r,那么我们可以计算距离的平方r2=rr而不必担心r. 但是,如果有奇数的权力,那么我们需要处理r=r2.

我的问题是:计算有多贵x如在通用语言(C/C++、Fortran、Python)等库中实现的那样?通过手动调整特定架构的代码是否真的有很多性能改进?

3个回答

作为对moyner 答案的扩展,片sqrt上通常是一个rsqrt,即计算平方根的倒数a1/a. 所以如果在你的代码中你只会使用1/r(如果你在做分子动力学,你就是),你可以r = rsqrt(r2)直接计算并省去除法。之所以用rsqrt计算代替,sqrt是因为它的牛顿迭代没有除法,只有加法和乘法。

作为旁注,除法也是迭代计算的,几乎和硬件一样慢rsqrt如果您正在寻找效率,您最好尝试删除多余的划分。

一些更现代的架构(例如IBM 的 POWER 架构rsqrt)本身并没有提供精确到几位的估计,例如FRSQRTE当用户调用rsqrt时,这会生成一个估计值,然后使用常规乘法和加法对牛顿或戈德施密特算法进行一两次(根据需要进行多次)迭代。这种方法的优点是迭代步骤可以流水线化并与其他指令交错而不会阻塞 FPU(对于这个概念的非常好的概述,尽管在旧架构上,请参阅Rolf Strebel 的博士论文)。

对于交互势,sqrt使用势函数的多项式插值可以完全避免该操作,但我自己在该领域的工作(在 中实现mdcore)表明,至少在 x86 类型的体系结构上,sqrt指令足够快。

更新

由于这个答案似乎得到了相当多的关注,我还想解决你问题的第二部分,即尝试改进/消除诸如 ? 之类的基本操作真的值得sqrt吗?

在分子动力学模拟或任何具有截止限制相互作用的基于粒子的模拟的背景下,可以从更好的邻域查找算法中获得很多。如果您使用Cell 列表或类似的东西来查找邻居或创建Verlet 列表,您将计算大量虚假的成对距离。在幼稚的情况下,只有 16% 的被检查粒子对实际上会在彼此的截止距离内。尽管没有为这些对计算相互作用,但访问粒子数据和计算虚假的成对距离会带来很大的成本。

我自己在这方面的工作(这里这里这里)以及其他人的工作(例如这里)展示了如何避免这些虚假计算。如此处所述,这些邻居查找算法甚至胜过 Verlet 列表

我要强调的一点是,尽管通过更好地了解/利用底层硬件架构可能会获得一些改进,但在重新思考更高级别的算法时也可能会获得更大的收益。

平方根是在大多数处理器的硬件中实现的,也就是说,有特定的汇编指令,并且在大多数语言中性能应该是相当的,因为很难搞砸实现。您可能永远无法击败 FSQRT 指令,因为它是由一些智能硬件设计师设计的。

它在硬件中的实现方式可能会有所不同,但它可能是某种定点迭代,例如 Newton-Raphson 的方法,它执行特定次数的迭代,直到计算出所需的位数。硬件中的迭代方法通常比其他操作慢得多,因为在结果准备好之前必须完成几个周期。

还有一些流式 SIMD 指令可用于 XMM 寄存器,以进行快速向量计算这些寄存器相当小,但如果您有已知数量的坐标(例如,三维笛卡尔坐标系),它们可能会快很多。

如果您的语言水平足够低,您总是可以将类型转换为较低的精度或使用较低精度的数字作为坐标。单精度通常绰绰有余,据我记得计算平方根时会更快,因为迭代可以更早终止。

对不同语言进行基准测试应该很容易:只需将一长串随机数写入文件,使用不同语言加载它,然后计算平方根时间。

可以有性能增强,但首先应该知道计算 sqrt 的倒数是瓶颈(而不是,比如说,加载位置和保存力)。

GROMACS MD 项目源于一个想法,即利用 IEEE 浮点格式的细节来播种 Newton-Raphson 迭代方案,以计算平方根倒数的可接受近似值(参见http:/的附录 B.3 /www.gromacs.org/Documentation/Manual),但是 GROMACS 仍然使用这个想法的地方没有使用 HPC CPU。