浮点除法与浮点乘法

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

如果你看 this answer 你会看到除法可以超过24个循环。

为什么除法要比乘法长那么多?如果你记得回到小学,你可能会记得乘法基本上可以同时进行许多加法运算。除法要求迭代减法不能同时执行,因此需要更长的时间。事实上,一些FP单元通过执行一个倒数近似并乘以它来加速除法。它没有那么精确,但速度有点快。

除法本质上比乘法慢得多。

事实上,这可能是编译器 不能 (而且您可能不想)在许多情况下,由于浮点错误而进行优化。这两种说法:

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

是 不 语义相同- 0.1 不能精确表示为 double ,因此最终将使用稍微不同的值-在这种情况下,用乘法替换除法将产生不同的结果!

小心划分,尽可能避免划分。举个例子,举倾 float inverse = 1.0f / divisor; 超出循环并乘以 inverse 在循环中。(如果 逆 可接受)

通常 1.0/x 不能完全代表为 float 或 double . 确切的时间是什么时候 x 是2的幂。这使编译器能够优化 x / 2.0f 到 x * 0.5f 结果没有任何变化。

为了让编译器为您进行这种优化,即使结果不准确(或使用运行时变量除数),您需要如下选项 gcc -O3 -ffast-math . 明确地, -freciprocal-math (由启用) -funsafe-math-optimizations 启用者 -ffast-math )让编译器替换 x / y 具有 x * (1/y) 如果有用的话。其他编译器也有类似的选项,默认情况下,ICC可能会启用一些“不安全”的优化(我认为是这样,但我忘记了)。

-快速数学 通常重要的是允许自动向量化fp循环,尤其是减少(例如将数组求和为一个标量总数),因为fp数学不是关联的。 Why doesn't GCC optimize a*a*a*a*a*a to (a*a*a)*(a*a*a)?

还要注意C++编译器可以折叠 + 和 * 在某些情况下(为支持它的目标编译时,例如 -march=haswell 但是他们不能这么做 / .

除法的延迟比乘法或加法(或 FMA )在现代x86 CPU上是2到4倍,而吞吐量则是6到40倍。 ^一 (做一个紧密的循环 只有 部门而不是 只有 乘法)。

Divide/Sqrt装置没有完全安装管道,原因见 @NathanWhitehead's answer . 最坏的比率是256b向量,因为(与其他执行单元不同)被除单元通常不是全宽的,所以宽向量必须分为两部分。一个不完全流水线的执行单元是如此不寻常,以至于英特尔的CPU有一个 arith.divider_active Hardware performance counter(硬件性能计数器),帮助您查找对除法器吞吐量产生瓶颈的代码,而不是通常的前端或执行端口瓶颈。(或者更常见的情况是,内存瓶颈或长延迟链限制了指令级别的并行性,导致每个时钟的指令吞吐量小于~4)。

然而,在Intel和AMD CPU(而不是KNL)上的fp division和sqrt是作为单个UOP实现的,因此它不一定对周围的代码有很大的吞吐量影响。 . 对于除法来说,最好的情况是当无序执行可以隐藏延迟时,以及当有大量的乘法和加法(或其他工作)可以与除法并行发生时。

(integer division在intel上被微编码为多个uop,所以它总是对周围的代码产生更大的影响,整数乘法。由于对高性能整数除法的需求较少,所以硬件支持也不怎么理想。相关: microcoded instructions like idiv can cause alignment-sensitive front-end bottlenecks )

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

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] 瓶颈开启 add 延迟或 div 吞吐量,但不是 div 延迟,因为分区不在关键路径上(循环带有依赖链)。

但在这种情况下( approximating a function like log(x) with a ratio of two polynomials )这个分水岭很便宜。 :

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指令只有一个除法。(在真实的 日志() 在用例中,有大量的工作需要提取指数/尾数,然后再次将它们组合在一起,所以在划分之间还要做更多的工作。)

当你确实需要分开的时候,通常最好是分开而不是 rcpps

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

你可以用这个来做 x / y = x * approx_recip(y) 不使用实际的除法指令。( RCPPS 它的ef相当快;通常比乘法慢一点。它使用从CPU内部的表进行表查找。分隔器硬件可以使用相同的表作为起点。)

在大多数情况下, x * rcpps(y) 太不准确了,需要牛顿-拉斐逊迭代才能使精度加倍。但是你要付出代价 2 multiplies and 2 FMAs 和具有与实际的除法指令一样高的延迟。如果 全部的 你要做的是除法,然后它可以是吞吐量的胜利。(但是,如果可以的话,首先应该避免这种循环,可以将除法作为另一个循环的一部分来完成其他工作。)

但是如果你使用除法作为更复杂函数的一部分, RCPPS 它本身加上额外的mul+fma通常可以更快地用 divps 指令,非常低的CPU除外 迪普斯 吞吐量。

(例如骑士登陆,见下文。KNL支架 AVX512ER ,因此 浮动 矢量 VRCP28PS 结果已经足够精确,不需要牛顿-拉斐逊迭代就可以进行乘法。 浮动 尾数大小只有24位。)

Agner Fog表格中的具体数字:

与其他所有的ALU操作不同,分区延迟/吞吐量依赖于某些CPU。再次说明,这是因为它太慢了,而且还没有完全安装管道。无序调度在固定延迟的情况下更容易实现,因为它避免了写回冲突(当相同的执行端口尝试在同一周期内生成2个结果时,例如运行3个周期的指令,然后运行两个1个周期的操作)。

一般来说,最快的情况是除数是一个类似于 2.0 或 0.5 (即,基础2 浮动 表示法在尾数中有许多尾随零)。

浮动 延迟 (周期) /吞吐量 (每个指令循环,使用独立输入背靠背运行):

                   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)

双重的 延迟 (周期) /吞吐量 (每个指令的周期数):

                   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和 即使是骑士的着陆(基于Silvermont的Xeon phi)也有非常低的分频性能。 ,即使是128B向量也比标量慢。AMD的低功耗Jaguar CPU(在某些控制台中使用)与此类似。一个高性能的分割需要很大的模具面积。Xeon Phi功率低 每芯 并且在模具上填充大量的核心使其具有比Skylake-AVX512更严格的模具区域限制。似乎AVX512ER rcp28ps / pd 是你“应该”在KNL上使用的。

(见 this InstLatx64 result 对于skylake-avx512,也就是skylake-x.数字 vdivps zmm :18C/10C,所以一半的吞吐量 ymm )

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

脚注1:我是如何组成这些部门与多部门绩效比率的:

fp divide与multiple性能比甚至比低功耗CPU(如silvermont和jaguar)和Xeon phi(knl,应该使用avx512er)的性能比还要差。

标量(非矢量化)的实际分乘吞吐量比 双重的 :8在Ryzen和Skylake上增加了分隔符,但16-28在Haswell上(取决于数据,除非除数是整数,否则更可能接近28周期结束)。这些现代的CPU有非常强大的分频器,但是它们的每时钟2倍的吞吐量会使它消失。(更重要的是,当您的代码可以使用256B AVX向量自动向量化时)。还要注意,使用正确的编译器选项, 这些乘法吞吐量也适用于fma。

数字来自 http://agner.org/optimize/ 用于Intel Haswell/Skylake和AMD Ryzen的指令表,用于SSE Scalar(不包括X87 fmul / fdiv )对于256b avx simd矢量 浮动 或 双重的 . 另请参见 x86 标记wiki。

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

然而,现代PC是 非常 快。它们还包含管道化架构,可以在许多情况下消除差异。最重要的是,任何合适的编译器都将执行您在中显示的除法操作。 编译时间 启用优化后。对于更新后的示例,任何合适的编译器都会自己执行该转换。

所以一般来说 你应该担心代码的可读性 ,让编译器担心如何快速执行。只有当您对该行的速度测量有问题时,才应该担心为了速度而歪曲代码。编译器很清楚什么比CPU上的更快,而且通常比您希望的优化器要好得多。

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

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

有些区别:乘法的每一步只需要看1位;除法的每一步在比较时都需要看N位。乘法的每个阶段都独立于所有其他阶段(不考虑部分积的添加顺序);对于除法,每个步骤都取决于前一步。这在硬件方面是个大问题。如果事情可以独立完成,那么它们可以在一个时钟周期内同时发生。

牛顿-瑞森通过线性代数的应用,解决了O(M(N))复杂性中的整数除法。比其他O(n*n)复杂性更快。

在代码中,该方法包含10mults9adds2bitwiseshifts。

这就解释了为什么一个除法的CPU节拍大约是乘法的12倍。

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

例如,在x86上对数组执行大量乘法应该比执行除法快得多,因为编译器应该创建使用SIMD指令的汇编程序代码。由于在SIMD指令中没有除法,那么使用乘法然后除法可以看到很大的改进。