整数乘法与现代CPU上的加法速度完全相同

Question

我经常听到这种说法,现代硬件上的乘法是如此优化,以至于它实际上与加法相同.真的吗？

我从来没有得到任何权威的确认.我自己的研究只会增加问题.速度测试通常会显示让我感到困惑的数据.这是一个例子:

#include <stdio.h>
#include <sys/time.h>

unsigned int time1000() {
    timeval val;
    gettimeofday(&val, 0);
    val.tv_sec &= 0xffff;
    return val.tv_sec * 1000 + val.tv_usec / 1000;
}

int main() {
    unsigned int sum = 1, T = time1000();
    for (int i = 1; i < 100000000; i++) {
        sum += i + (i+1); sum++;
    }
    printf("%u %u\n", time1000() - T, sum);
    sum = 1;
    T = time1000();
    for (int i = 1; i < 100000000; i++) {
        sum += i * (i+1); sum++;
    }
    printf("%u %u\n", time1000() - T, sum);
}

上面的代码可以显示乘法更快:

clang++ benchmark.cpp -o benchmark
./benchmark
746 1974919423
708 3830355456

但是对于其他编译器,其他编译器参数,不同编写的内部循环,结果可能会有所不同,我甚至无法得到近似值.

Answer 1

实际上,你接受的以理论为中心的答案是100%错误的.

实际上,两个n位数的乘法可以在O(log n)电路深度中完成,就像加法一样.

另外在O(log n)的被对半分割的数目和(递归)将两个部分进行平行,其中,所述上半部分解决了两个中的"0-进位"和"1进位"的情况.一旦添加下半部分,就检查进位,其值用于在0进位和1进位情况之间进行选择.

O(log n)深度的乘法也是通过并行化完成的,其中3个数字的每个和被减少为并行的仅2个数的和,并且总和以如上所述的某种方式完成.
我不会在这里解释它,但你可以通过查找"carry-lookahead"和"carry-save"添加来找到关于快速加法和乘法的阅读材料.

因此从理论的角度来看,由于电路显然是并行的(与软件不同),因此乘法渐近较慢的唯一原因是前面的常数因子,而不是渐近复杂度.

Answer 2

不,他们的速度不一样.谁告诉你的？

Agner Fog的指令表显示,当使用32位整数寄存器时,Haswell的ADD/SUB需要0.25-1个周期(取决于指令的流水线程度),而MUL需要2-4个周期.浮点是另一种方式:ADDSS/SUBSS需要1-3个周期,而MULSS需要0.5-5个周期.

Answer 3

这是一个比简单乘法与加法更复杂的答案.实际上答案很可能永远不会是肯定的.电子方式的乘法是一个复杂得多的电路.大多数原因是,乘法是乘法步骤后跟加法步骤的行为,记住在使用计算器之前乘以十进制数是什么感觉.

要记住的另一件事是,乘法将花费更长或更短的时间,具体取决于您运行它的处理器的体系结构.这可能是也可能不是公司特定的.虽然AMD很可能与英特尔不同,但即使是英特尔i7也可能与核心2(在同一代内)不同,而且几代人之间肯定会有所不同(尤其是后者更远).

在所有的技术性中,如果乘法是你唯一做的事情(没有循环,计数等......),乘法将是2到(如在PPC架构上看到的那样)慢35倍.这更像是了解您的架构和电子设备的练习.

另外: 应该注意的是,可以构建一个处理器,包括乘法的所有操作都需要一个时钟.该处理器必须做的是,摆脱所有流水线操作,并减慢时钟速度,以便任何OP电路的硬件延迟小于或等于时钟时序提供的延迟.

要做到这一点,可以摆脱我们在将流水线添加到处理器时能够获得的固有性能提升.流水线技术是将任务分解为更小的子任务的想法,这些子任务可以更快地执行.通过在子任务之间存储和转发每个子任务的结果,我们现在可以运行更快的时钟速率,只需要允许子任务的最长延迟,而不是整个总体任务.

通过乘法的时间图片:

| ------------------------------------------------- - | 非流水线

| - 步骤1-- | - 步骤2-- | - 步骤3-- | - 步骤4-- | - 步骤5-- | 流水线

在上图中,非流水线电路需要50个单位时间.在流水线版本中,我们将50个单元分成5个步骤,每个步骤占用10个单位时间,其间有一个存储步骤.值得注意的是,在流水线示例中,每个步骤都可以完全独立工作.对于要完成的操作,它必须按顺序遍历所有5个步骤,但是对于操作数的另一个操作可以在步骤2中,如在步骤1,3,4和5中.

尽管如此,这种流水线方法允许我们在每个时钟周期内连续填充操作员,并在每个时钟周期得到结果如果我们能够订购我们的操作,以便我们可以在切换之前执行所有操作对于另一个操作,我们所做的所有时间命中都是将FIRST操作从管道中取出所需的原始时钟量.

神秘提出了另一个好点.从更系统的角度来看这个架构也很重要.确实,较新的Haswell架构是为了提高处理器内的浮点乘法性能而构建的.由于这个原因,作为系统级别,它被设计为允许多个乘法同时发生,而添加只能在每个系统时钟发生一次.

所有这些可以总结如下:

1. 每个体系结构都不同于较低级别的HW透视图以及系统透视图
2. 功能性,乘法将总是比添加花费更多的时间,因为它结合了真正的乘法和真正的加法步骤.
3. 了解您尝试运行代码的体系结构,并在可读性和从该体系结构中获得真正最佳性能之间找到适当的平衡点.

Answer 4

我来到这个线程是为了了解现代处理器在整数数学方面正在做什么以及执行它们所需的周期数。我在 1990 年代研究了在 65c816 处理器上加速 32 位整数乘法和除法的问题。使用下面的方法，我能够将当时 ORCA/M 编译器中可用的标准数学库的速度提高三倍。

因此，乘法比加法快的想法并非如此（除非很少），但正如人们所说，这取决于架构的实现方式。如果在时钟周期之间执行足够多的步骤，是的，乘法可以有效地与基于时钟的加法具有相同的速度，但是会浪费很多时间。在这种情况下，如果给定一条指令和多个值，那么有一条指令可以执行多次（相关）加/减运算。一个人可以做梦。

在 65c816 处理器上，没有乘法或除法指令。Mult 和 Div 完成了轮班和加法。
要执行 16 位加法，您将执行以下操作：

LDA $0000 - loaded a value into the Accumulator (5 cycles)
ADC $0002 - add with carry  (5 cycles)
STA $0004 - store the value in the Accumulator back to memory (5 cycles)
15 cycles total for an add

如果处理来自 C 的调用，您将有额外的开销来处理从堆栈中推入和拉出值。例如，创建一次执行两个倍数的例程将节省开销。

传统的乘法方法是对一个数的整个值进行移位和相加。每次向左移动时进位变为 1 就意味着您需要再次添加该值。这需要对每一位进行测试并对结果进行移位。

我用一个包含 256 个项目的查找表替换了它，这样就不需要检查进位位了。还可以在进行乘法运算之前确定溢出，以免浪费时间。（在现代处理器上，这可以并行完成，但我不知道他们是否在硬件中执行此操作）。给定两个 32 位数字和预筛选溢出，其中一个乘法器始终为 16 位或更少，因此只需运行一次或两次 8 位乘法即可执行整个 32 位乘法。这样做的结果是乘法速度提高了 3 倍。

16位乘法的速度从12个周期到大约37个周期不等

multiply by 2  (0000 0010)
LDA $0000 - loaded a value into the Accumulator  (5 cycles).
ASL  - shift left (2 cycles).
STA $0004 - store the value in the Accumulator back to memory (5 cycles).
12 cycles plus call overhead.

multiply by (0101 1010)
LDA $0000 - loaded a value into the Accumulator  (5 cycles) 
ASL  - shift left (2 cycles) 
ASL  - shift left (2 cycles) 
ADC $0000 - add with carry for next bit (5 cycles) 
ASL  - shift left (2 cycles) 
ADC $0000 - add with carry for next bit (5 cycles) 
ASL  - shift left (2 cycles) 
ASL  - shift left (2 cycles) 
ADC $0000 - add with carry for next bit (5 cycles) 
ASL  - shift left (2 cycles) 
STA $0004 - store the value in the Accumulator back to memory (5 cycles)
37 cycles plus call overhead

由于 AppleIIgs 的数据总线只有 8 位宽，加载 16 位值需要 5 个周期从内存加载，一个额外周期用于指针，另一个周期用于第二个字节。

LDA 指令（1 个周期，因为它是一个 8 位值） $0000（16 位值需要两个周期来加载） 内存位置（因为 8 位数据总线需要两个周期来加载）

现代处理器能够更快地做到这一点，因为它们在最坏的情况下具有 32 位数据总线。在处理器逻辑本身中，与数据总线延迟相比，门系统根本没有额外的延迟，因为整个值将立即加载。

要进行完整的 32 位乘法，您需要执行上述两次并将结果相加以获得最终答案。现代处理器应该能够并行执行这两项操作，并为答案添加结果。结合并行完成的溢出预检查，它将最大限度地减少乘法所需的时间。

无论如何，很明显乘法比加法需要更多的努力。在 cpu 时钟周期之间处理操作的步骤数将决定需要多少个时钟周期。如果时钟足够慢，那么加法看起来与乘法的速度相同。

问候， 肯

Answer 5

乘法需要最后一步加法，至少是相同大小的数字；所以它比添加需要更长的时间。十进制：

    123
    112
   ----
   +246  ----
   123      | matrix generation  
  123    ----
  -----
  13776 <---------------- Addition

同样适用于二进制，对矩阵进行更精细的缩减。

也就是说，它们可能需要相同时间的原因：

1. 为了简化流水线架构，所有常规指令都可以设计为采用相同数量的周期（例如内存移动除外，这取决于与外部内存通信所需的时间）。
2. 由于乘法器最后一步的加法器就像加法指令的加法器......为什么不通过跳过矩阵生成和减少来使用相同的加法器？如果他们使用相同的加法器，那么显然他们将花费相同的时间。

当然，在更复杂的架构中，情况并非如此，您可能会获得完全不同的值。您还有一些体系结构，当它们不相互依赖时，可以并行执行多条指令，然后您就有点受编译器和操作系统的支配。

严格运行此测试的唯一方法必须在没有操作系统的情况下在汇编中运行 - 否则变量太多。

Answer 6

自Haswell以来的英特尔

• add4 /时钟吞吐量的性能，1个周期的延迟。（任何操作数大小）
• imul1时钟吞吐量的性能，3周期延迟。（任何操作数大小）

Ryzen与此类似。推土机系列的整数吞吐量低得多，并且乘法没有完全流水线化，对于64位操作数大小的乘法，速度特别慢。见https://agner.org/optimize/和其他环节https://stackoverflow.com/tags/x86/info

但是好的编译器可以自动向量化循环。（SIMD整数乘以吞吐量和延迟都比SIMD整数加法要差）。或者只是通过它们不断传播以打印出答案！Clang确实知道封闭形式的高斯公式，sum(i=0..n)并且可以识别出执行此操作的某些循环。

您忘了启用优化，因此这两个循环都会在ALU +的存储延迟和重新加载延迟中出现瓶颈，并且sum在sum += independent stuff和之间保持内存sum++。请参阅为什么clang用-O0产生效率低的asm（对于这个简单的浮点数之和）？详细了解生成的asm有多严重，以及为什么会这样。 clang++默认为-O0（调试模式：将变量保留在内存中，调试器可以在其中在任何C ++语句之间修改变量）。

在类似Sandybridge系列（包括Haswell和Skylake）的现代x86上，存储转发延迟大约为3到5个周期，具体取决于重新加载的时间。因此，add在其中还存在一个1周期延迟的ALU ，您正在此循环的关键路径中查看大约两个6周期延迟的步骤。（大量隐藏所有基于的存储/重新加载和计算i，以及循环计数器更新）。

另请参见添加冗余分配可以加快代码的编译速度，而无需进行优化即可针对另一个无优化基准进行编译。在这种情况下，实际上，通过在循环中进行更多独立的工作来减少存储转发延迟，从而延迟了重新加载的尝试。

现代的x86 CPU具有1 / clock的倍增吞吐量，因此即使进行了优化，您也不会看到吞吐量瓶颈。或在Bulldozer系列上，每2时钟吞吐量中没有1个完全流水线化。

您更有可能在前端工作上遇到瓶颈，因为每个周期都要发布所有工作。

尽管lea确实允许非常有效的复制和添加，并且只i + i + 1用一条指令即可。尽管确实是一个好的编译器，但是该循环仅使用2*i并优化以增加2。即降低强度以重复执行2的加法，而不必在循环内移动。

当然与优化的额外sum++只需折叠成sum += stuff，其中stuff已经包含了一个常数。乘法则不是这样。