97

通过编码是否有任何(非微优化)性能增益

float f1 = 200f / 2

相比

float f2 = 200f * 0.5

几年前,我的一位教授告诉我,浮点除法比浮点乘法慢,但没有详细说明原因。

这种说法是否适用于现代 PC 架构?

更新1

关于评论,请同时考虑这种情况:

float f1;
float f2 = 2
float f3 = 3;
for( i =0 ; i < 1e8; i++)
{
  f1 = (i * f2 + i / f3) * 0.5; //or divide by 2.0f, respectively
}

更新 2 引用评论:

[我想]知道什么是算法/架构要求导致 > 除法在硬件上比乘法复杂得多

4

7 回答 7

101

是的,许多 CPU 可以在 1 或 2 个时钟周期内执行乘法运算,但除法总是需要更长的时间(尽管 FP 除法有时比整数除法更快)。

如果您查看此答案,您会发现除法可以超过 24 个周期。

为什么除法比乘法花这么多时间?如果您还记得小学时,您可能还记得乘法基本上可以通过许多同时加法来执行。除法需要迭代减法,不能同时执行,因此需要更长的时间。事实上,一些 FP 单元通过执行倒数近似并乘以它来加速除法。它不太准确,但速度更快。

于 2010-11-08T15:09:48.880 回答
57

分割时要非常小心,并尽可能避免。例如,从循环中提升float inverse = 1.0f / divisor;并在循环内乘以inverse。(如果舍入误差inverse可以接受)

通常1.0/x不会精确表示为 afloatdoublex什么时候是 2 的幂是准确的。这让编译器可以x / 2.0fx * 0.5f不改变结果的情况下进行优化。

即使结果不准确(或使用运行时变量除数),为了让编译器为您执行此优化,您需要像 gcc -O3 -ffast-math. 具体来说,-freciprocal-math(由-funsafe-math-optimizationsenabled by 启用-ffast-math)让编译器在有用时替换x / y为。x * (1/y)其他编译器也有类似的选项,ICC 可能会默认启用一些“不安全”的优化(我认为确实如此,但我忘记了)。

-ffast-math对于允许 FP 循环的自动矢量化通常很重要,尤其是减少(例如,将一个数组求和为一个标量总数),因为 FP 数学不是关联的。 为什么 GCC 不将 a*a*a*a*a*a 优化为 (a*a*a)*(a*a*a)?

另请注意,C++ 编译器在某些情况下可以折叠+*放入 FMA(当为支持它的目标进行编译时,例如-march=haswell),但它们不能使用/.


在现代 x86 CPU 上,除法的延迟比乘法或加法(或FMA)差 2 到 4 倍,吞吐量差 6 到 40 1倍(对于只进行除法而不是乘法的紧密循环)。

由于@NathanWhitehead 的回答中解释的原因,divide / sqrt 单元没有完全流水线化。最差的比率是 256b 向量,因为(与其他执行单元不同)除法单元通常不是全角的,因此宽向量必须分成两半。不完全流水线的执行单元非常不寻常,以至于英特尔 CPU 有一个arith.divider_active硬件性能计数器,可以帮助您找到分频器吞吐量瓶颈的代码,而不是通常的前端或执行端口瓶颈。(或者更常见的是,内存瓶颈或长延迟链限制了指令级并行性,导致指令吞吐量低于每时钟约 4 个)。

但是,英特尔和 AMD CPU(KNL 除外)上的 FP 除法和 sqrt 是作为单个 uop 实现的,因此它不一定对周围代码的吞吐量影响很大。除法的最佳情况是乱序执行可以隐藏延迟,并且当除法可能并行发生大量乘法和加法(或其他工作)时。

(整数除法在英特尔上被微编码为多个微指令,因此它对整数相乘的周围代码总是有更大的影响。对高性能整数除法的需求较少,因此硬件支持不那么花哨。相关:微编码指令如idivcan导致对齐敏感的前端瓶颈。)

例如,这将非常糟糕:

for ()
    a[i] = b[i] / scale;  // division throughput bottleneck

// Instead, use this:
float inv = 1.0 / scale;
for ()
    a[i] = b[i] * inv;  // multiply (or store) throughput bottleneck

您在循环中所做的只是加载/划分/存储,它们是独立的,因此重要的是吞吐量,而不是延迟。

像这样的减少accumulator /= b[i]会成为除法或乘法延迟的瓶颈,而不是吞吐量。但是使用最后除法或乘法的多个累加器,您可以隐藏延迟并仍然使吞吐量饱和。请注意延迟或吞吐量的sum += a[i] / b[i]瓶颈,但不是延迟,因为划分不在关键路径(循环携带的依赖链)上。adddivdiv


但是在这样的情况下(用两个多项式的比率近似函数log(x)),除法可能非常便宜

for () {
    // (not shown: extracting the exponent / mantissa)
    float p = polynomial(b[i], 1.23, -4.56, ...);  // FMA chain for a polynomial
    float q = polynomial(b[i], 3.21, -6.54, ...);
    a[i] = p/q;
}

log()尾数的范围内,两个 N 阶多项式的比率比具有 2N 个系数的单个多项式的误差要小得多,并且并行评估 2 可以在单个循环体中为您提供一些指令级并行性,而不是一个很长的循环体dep 链,使乱序执行变得更容易。

在这种情况下,我们不会成为除法延迟的瓶颈,因为乱序执行可以使循环在数组上的多次迭代保持在飞行状态。

只要我们的多项式足够大,以至于每 10 条 FMA 指令左右只有一个除法,我们就不会成为除法吞吐量的瓶颈。(在实际log()用例中,提取指数/尾数并将事物重新组合在一起需要做大量工作,因此在除法之间还有更多工作要做。)


当你确实需要除法时,通常最好只除法而不是rcpps

x86 有一个近似倒数指令 ( rcpps),它只给你 12 位的精度。(AVX512F 有 14 位,AVX512ER 有 28 位。)

您可以在x / y = x * approx_recip(y)不使用实际除法指令的情况下使用它。(rcppsitef 相当快;通常比乘法慢一点。它使用从 CPU 内部表中查找表。除法器硬件可能使用同一个表作为起点。)

在大多数情况下,x * rcpps(y)它太不准确了,需要 Newton-Raphson 迭代以使精度加倍。但这会花费您2 次乘法和 2 次 FMA,并且延迟大约与实际除法指令一样高。如果您所做的只是除法,那么它可能是吞吐量上的胜利(但是如果可以的话,你应该首先避免这种循环,也许通过将除法作为另一个循环的一部分来完成其他工作。)

但是,如果您将除法用作更复杂函数的一部分,则rcpps它本身 + 额外的 mul + FMA 通常会使仅用一条指令进行除法更快,除非在吞吐量divps非常低的 CPU 上。divps

(例如 Knight's Landing,见下文。KNL 支持AVX512ER,因此对于float向量,VRCP28PS结果已经足够准确,无需 Newton-Raphson 迭代即可相乘。 float尾数大小仅为 24 位。)


Agner Fog 表格中的具体数字:

与其他所有 ALU 操作不同,除法延迟/吞吐量取决于某些 CPU 的数据。同样,这是因为它太慢并且没有完全流水线化。无序调度在固定延迟的情况下更容易,因为它避免了回写冲突(当同一个执行端口试图在同一个周期内产生 2 个结果时,例如运行 3 个周期的指令,然后运行两个 1 个周期的操作) .

通常,最快的情况是当除数是“整数”之类的2.0或时0.5(即,base2float表示在尾数中有很多尾随零)。

float 延迟(周期)/吞吐量(每条指令的周期,使用独立输入背靠背运行):

                   scalar & 128b vector        256b AVX vector
                   divss      |  mulss
                   divps xmm  |  mulps           vdivps ymm | vmulps ymm

Nehalem          7-14 /  7-14 | 5 / 1           (No AVX)
Sandybridge     10-14 / 10-14 | 5 / 1        21-29 / 20-28 (3 uops) | 5 / 1
Haswell         10-13 / 7     | 5 / 0.5       18-21 /   14 (3 uops) | 5 / 0.5
Skylake            11 / 3     | 4 / 0.5          11 /    5 (1 uop)  | 4 / 0.5

Piledriver       9-24 / 5-10  | 5-6 / 0.5      9-24 / 9-20 (2 uops) | 5-6 / 1 (2 uops)
Ryzen              10 / 3     | 3 / 0.5         10  /    6 (2 uops) | 3 / 1 (2 uops)

 Low-power CPUs:
Jaguar(scalar)     14 / 14    | 2 / 1
Jaguar             19 / 19    | 2 / 1            38 /   38 (2 uops) | 2 / 2 (2 uops)

Silvermont(scalar)    19 / 17    | 4 / 1
Silvermont      39 / 39 (6 uops) | 5 / 2            (No AVX)

KNL(scalar)     27 / 17 (3 uops) | 6 / 0.5
KNL             32 / 20 (18uops) | 6 / 0.5        32 / 32 (18 uops) | 6 / 0.5  (AVX and AVX512)

double 延迟(周期)/吞吐量(每条指令的周期):

                   scalar & 128b vector        256b AVX vector
                   divsd      |  mulsd
                   divpd xmm  |  mulpd           vdivpd ymm | vmulpd ymm

Nehalem         7-22 /  7-22 | 5 / 1        (No AVX)
Sandybridge    10-22 / 10-22 | 5 / 1        21-45 / 20-44 (3 uops) | 5 / 1
Haswell        10-20 /  8-14 | 5 / 0.5      19-35 / 16-28 (3 uops) | 5 / 0.5
Skylake        13-14 /     4 | 4 / 0.5      13-14 /     8 (1 uop)  | 4 / 0.5

Piledriver      9-27 /  5-10 | 5-6 / 1       9-27 / 9-18 (2 uops)  | 5-6 / 1 (2 uops)
Ryzen           8-13 /  4-5  | 4 / 0.5       8-13 /  8-9 (2 uops)  | 4 / 1 (2 uops)

  Low power CPUs:
Jaguar            19 /   19  | 4 / 2            38 /  38 (2 uops)  | 4 / 2 (2 uops)

Silvermont(scalar) 34 / 32    | 5 / 2
Silvermont         69 / 69 (6 uops) | 5 / 2           (No AVX)

KNL(scalar)      42 / 42 (3 uops) | 6 / 0.5   (Yes, Agner really lists scalar as slower than packed, but fewer uops)
KNL              32 / 20 (18uops) | 6 / 0.5        32 / 32 (18 uops) | 6 / 0.5  (AVX and AVX512)

Ivybridge 和 Broadwell 也不同,但我想保持桌子小。(Core2(Nehalem 之前)具有更好的分频器性能,但其最大时钟速度较低。)

Atom、Silvermont,甚至 Knight's Landing(基于 Silvermont 的 Xeon Phi)的除法性能都非常低,甚至 128b 的向量也比标量慢。AMD 的低功耗 Jaguar CPU(用于某些游戏机)类似。高性能分频器占用大量芯片面积。Xeon Phi 的每核功耗低,并且在一个裸片上封装大量核心使其在裸片面积上的限制比 Skylake-AVX512 更严格。似乎 AVX512ER rcp28ps/pd是您“应该”在 KNL 上使用的。

(请参阅Skylake-AVX512 aka Skylake-X 的InstLatx64 结果。数字为vdivps zmm:18c / 10c,因此吞吐量的一半ymm。)


当它们被循环携带时,或者当它们太长以至于它们停止乱序执行以寻找与其他独立工作的并行性时,长延迟链就会成为一个问题。


脚注 1:我是如何构成这些 div 与 mul 性能比的:

FP 分频与倍数性能比甚至比 Silvermont 和 Jaguar 等低功耗 CPU 甚至在 Xeon Phi(KNL,您应该使用 AVX512ER)中更差。

标量(非矢量化)的实际除法/乘法吞吐量比double:在 Ryzen 和 Skylake 上使用增强的除法器为 8,但在 Haswell 上为 16-28(取决于数据,并且更有可能在 28 周期结束时,除非您的除数是圆形的数)。这些现代 CPU 具有非常强大的除法器,但其每时钟 2 倍的乘法吞吐量将其击倒。(当您的代码可以使用 256b AVX 向量自动向量化时更是如此)。另请注意,使用正确的编译器选项,这些乘法吞吐量也适用于 FMA。

英特尔 Haswell/Skylake 和 AMD Ryzen、SSE 标量(不包括 x87 / )和 256b AVX SIMD 向量的http://agner.org/optimize/指令表中的数字or 。另请参阅标签 wiki。fmulfdivfloatdouble

于 2017-08-26T20:00:42.053 回答
22

除法本质上是比乘法慢得多的运算。

这实际上可能是编译器在许多情况下由于浮点不准确性而无法(而且您可能不想)优化的东西。这两种说法:

double d1 = 7 / 10.;
double d2 = 7 * 0.1;

在语义上并不0.1相同 -不能完全表示为 a double,因此最终将使用稍微不同的值 - 在这种情况下用乘法代替除法会产生不同的结果!

于 2010-11-08T15:20:11.490 回答
10

是的。我所知道的每个 FPU 执行乘法都比除法快得多。

但是,现代 PC 的速度非常快。它们还包含流水线架构,可以在许多情况下使差异可以忽略不计。最重要的是,任何体面的编译器都会执行您在编译时显示的除法运算,并打开优化。对于您更新的示例,任何体面的编译器都会自行执行该转换。

所以通常你应该担心让你的代码可读,让编译器担心让它变得更快。只有当您对该行有测量速度问题时,您才应该担心为了速度而扭曲您的代码。编译器很清楚什么比他们的 CPU 上的要快,并且通常比你所希望的要好得多。

于 2010-11-08T15:13:24.900 回答
8

想想两个 n 位数相乘需要什么。使用最简单的方法,您取一个数字 x 并重复移位并有条件地将其添加到累加器(基于另一个数字 y 中的一位)。在 n 次添加之后,您就完成了。您的结果适合 2n 位。

对于除法,您从 2n 位的 x 和 n 位的 y 开始,您想要计算 x / y。最简单的方法是长除法,但是是二进制的。在每个阶段,您都进行比较和减法以获得更多的商。这需要你 n 个步骤。

一些区别:乘法的每一步只需要看1位;除法的每个阶段都需要在比较过程中查看n位。乘法的每个阶段都独立于所有其他阶段(添加部分产品的顺序无关紧要);对于除法,每一步都取决于上一步。这对硬件来说是一件大事。如果事情可以独立完成,那么它们可以在一个时钟周期内同时发生。

于 2011-03-16T07:15:36.870 回答
2

Newton rhapson 通过线性代数逼近解决 O(M(n)) 复杂度中的整数除法。比 O(n*n) 复杂度更快。

在代码中该方法包含 10mults 9adds 2bitwiseshifts。

这就解释了为什么除法的 CPU 滴答数大约是乘法的 12 倍。

于 2016-04-02T16:30:37.380 回答
1

答案取决于您正在编程的平台。

例如,在 x86 上对数组进行大量乘法运算应该比除法运算快得多,因为编译器应该创建使用 SIMD 指令的汇编代码。由于 SIMD 指令中没有除法,因此您会看到使用乘法然后除法的巨大改进。

于 2010-11-08T15:23:58.093 回答