浮点除法与浮点乘法

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

float f1 = 200f / 2 

与…相比

 float f2 = 200f * 0.5 

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

这个声明是否适用于现代PC架构?

UPDATE1

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

 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从评论引用:

[我想]知道什么是algorithm/体系结构的要求,导致分裂在硬件上比乘法复杂得多

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

如果你看这个答案,你会看到,该部门可以超过24个周期。

为什么师比乘法要长得多? 如果你记得回到小学,你可能会记得,乘法基本上可以同时进行。 除法需要迭代减法,不能同时执行,所以需要更长的时间。 事实上,一些计划生育单位通过进行相互近似并乘以这个近似值来加速分裂。 这不是很准确,但有点快。

除了乘法本身就是一个非常慢的操作。

事实上这可能是由于浮点数不准确而导致编译器无法做到 (也许不想)在许多情况下优化的。 这两个陈述:

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

在语义上是相同的 – 0.1不能被精确地表示为double ,所以稍微不同的值就会被使用 – 在这种情况下用乘法替代除法将产生不同的结果!

是。 我知道的每个FPU执行乘法的速度比分区快得多。

但是,现代个人电脑速度非常快。 它们还包含stream水线架构,在许多情况下,这些stream水线架构可以忽略不计。 最后,任何体面的编译器都会执行您在编译时显示的优化打开的除法操作。 对于你更新的例子,任何体面的编译器都会自己执行这个转换。

所以一般来说, 你应该担心使你的代码可读 ,让编译器担心使它快速。 只有当你有一个测量速度的问题,你应该担心为了速度而使你的代码变形。 编译器非常清楚CPU的速度,通常比你所期望的要好得多。

考虑两个n位数相乘所需的条件。 用最简单的方法,你取一个数字x,并反复移动,并有条件地将其添加到累加器(基于另一个数y中的位)。 n添加后,你完成。 你的结果适合2n位。

对于分割,你从2n位的x和n位的y开始,你要计算x / y。 最简单的方法是长时间的分割,但是是二进制的。 在每一个阶段,你都会做一个比较和一个减法来得到一个商的位数。 这需要你n步。

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

分割时要非常小心,尽可能避免。 例如,起升float inverse = 1.0 / divisor; 在一个循环之外并且在循环内部乘以一个inverse 。 (如果inverse的舍入误差可以接受)

通常1.0/x不能完全表示为floatdouble float 。 当x是2的幂时,这将是确切的。这可以使编译器将x / 2.0优化为x * 0.5而不会改变结果。

为了让编译器为你做这个优化,即使结果不准确(或运行时variables除数),你也需要像gcc -O3 -ffast-math这样的选项。 具体来说, -freciprocal-math (通过由-funsafe-math-optimizations启用的-ffast-math -funsafe-math-optimizations启用)可让编译-ffast-math x * (1/y)replacex / y x * (1/y)如果有用的话)。 其他编译器有类似的select,ICC可能会默认启用一些“不安全”的优化(我认为是这样,但我忘了)。

-ffast-math对于允许FP循环的自动vector化非常重要,特别是减less(例如将一个数组合并成一个标量总和),因为FPmath不是关联的。 为什么GCC不能优化a * a * a * a * a到(a * a * a)*(a * a * a)?

另外请注意,在某些情况下,C ++编译器可以将+*折叠成FMA(编译支持它的目标时,如-march=haswell ),但不能用/


在现代的x86处理器上,除了乘法或者加法之外,分区的延迟要比原来的2到4倍,而吞吐量要差6到40倍 。 (比Silvermont和Jaguar这样的低功耗CPU,甚至在Xeon Phi(KNL,你应该使用AVX512ER的地方))还要糟糕。 例如,对于Ryzen和Skylake的标量(非vector化) double :8和Haswell分别是16到28(数据依赖,更可能是28周期结束,除非你的除数是整数)。 这些现代CPU具有非常强大的分频器,但是其每时钟2倍的吞吐量将其吹走。 (甚至当你的代码可以自动vector化256b AVXvector)。 另请注意,使用正确的编译器选项,那些吞吐量也适用于FMA 。

英特尔Haswell / Skylake和AMD Ryzen的http://agner.org/optimize/指令表中的数字,用于SSE标量(不包括x87 fmul / fdiv )和256b AVX SIMDvectorfloatdouble float 。 另请参阅x86标记wiki。 (分/ sqrt单元没有完全stream水线,理由在@ NathanWhitehead的答案中解释)。 最坏的比率是256bvector,因为除法单位通常不是全angular,所以宽vector必须分成两半。 一个不完全stream水线的执行单元是非常不寻常的,英特尔CPU有一个arith.divider_active硬件性能计数器,以帮助您find代码的瓶颈分频器吞吐量。

然而,英特尔和AMD CPU(除了KNL之外)的FP部门是作为一个单一的uop实现的,所以它不一定对周围的代码有很大的吞吐量影响。 最好的划分方式是无序执行可以隐藏延迟,并且当有大量的乘法和增加(或其他工作),可以发生并行的鸿沟。

(整数除法被微码化为多个uop,所以它总是对整数乘法的周围代码产生更大的影响,对高性能整数除法的要求不高,所以对硬件的支持不是那么理想。 alignment敏感的前端瓶颈) 。

例如,这将是非常糟糕的:

 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]这样的减less将会在分裂或倍增延迟上,而不是吞吐量方面产生瓶颈。 但是,如果最终分割或乘法的多个累加器,则可以隐藏延迟并仍然使吞吐量饱和。 请注意, sum += a[i] / b[i]瓶颈是add延迟或div吞吐量,但不是div延迟,因为分区不在关键path(循环运载的依赖链)上。


但是在这样的情况下( 近似一个像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)而不使用实际的除法指令。 ( rcpps itsef相当快,通常比乘法要慢一点,它使用从CPU内部的一个表中查找的表,分频器硬件可以使用同一个表作为起始点。

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

但是,如果将division用作更复杂function的一部分, rcpps本身+额外的mul + FMA通常会使用divps指令进行分割的速度更快,除非吞吐量非常低的CPU。

(例如Knight's Landing,KNL支持AVX512ER ,所以对于float向量, VRCP28PS结果已经足够精确,只需要乘法而不需要Newton-Raphson迭代, float尾数只有24位。


来自Agner Fog桌子的具体数字:

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

一般来说,最快的情况是当除数是像2.00.5这样的“舍入”数字(即base2 float表示在尾数中有很多尾随零)时。

float 延迟 (周期) /吞吐量 (每条指令的周期数,以独立input背靠背的方式运行):

  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) 

艾维布里奇和布罗德韦尔也不一样,但我想保持小桌子。 (Core2(Nehalem之前)有更好的分频性能,但最大时钟频率更低。)

Atom,Silvermont, 甚至Knight's Landing(基于Silvermont的Xeon Phi)的分割性能都非常低 ,甚至128b向量比标量要慢。 AMD的低功耗Jaguar CPU(在一些调音台中使用)类似。 高性能的分频器需要大量的芯片面积。 至强皮芯片功耗低,在芯片上封装大量内核,使Skylake-AVX512的芯片面积受到更严格的限制。 看来,AVX512ER rcp28ps / pd是你在KNL上“应该”使用的。

(见Skylake-AVX512又名Skylake-X的InstLatx64结果 , vdivps zmm数字为18c / 10c,所以ymm的吞吐量只有ymm


长时延链在循环传输时,或者当它们太长以致于无法执行与其他独立工作的并行性时,就会成为问题。

牛顿rhapson通过线性代数apploximation求解O(M(n))复杂度的整数除法。 比其他O(n * n)复杂度更快。

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

这就解释了为什么一个分区的CPU数量大约是乘法的12倍。

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

例如,在x86上执行大量的数组乘法应该比分割要快得多,因为编译器应该创build使用SIMD指令的汇编代码。 由于SIMD指令中没有划分,所以使用乘法和除法可以看到很大的改进。