汇编 8086 - 无需 MUL 和 DIV 指令即可实现任何乘法和除法

Question

我想知道是否有一种方法可以在不使用 MUL 或 DIV 指令的情况下执行乘法或除法，因为它们需要大量 CPU 周期。我可以针对该目标利用 SHL 或 SHR 指令吗？如何实现汇编代码？

Answer 1

就像汇编中的其他事情一样，有很多方法可以进行乘法和除法。

1. 除以multiplying by the reciprocal值(value)。
2. 使用移位和加/减代替乘法。
3. 使用 lea 的地址计算选项(仅限乘法)。

打破神话

because they require a lot of CPU cycles

MUL和IMUL在现代 CPU 上速度极快，请参阅:http://www.agner.org/optimize/instruction_tables.pdf
DIV和IDIV一直以来都非常缓慢。

Intel Skylake 示例(第 217 页):

MUL, IMUL r64: Latency 3 cycles, reciprocal throughput 1 cycle.

请注意，这是乘以两个 64 的最大延迟!位值。
如果 CPU 所做的只是乘法，那么它可以在每个 CPU 周期完成这些乘法之一。
如果您认为上面使用移位和加法乘以 7 的示例有 4 个周期的延迟(使用 lea 为 3 个周期)。在现代 CPU 上，没有真正的方法可以击败简单的乘法。

乘以倒数

根据Agner Fog's asm lib instruction page 12 :

Division is slow on most microprocessors. In floating point calculations, we can do multiple divisions with the same divisor faster by multiplying with the reciprocal, for example:

float a, b, d;  
a /= d; b /= d;   

can be changed to:

float a, b, d, r;   
r = 1.0f / d;   
a *= r; b *= r;   

If we want to do something similar with integers then we have to scale the reciprocal divisor by 2n and then shift n places to the right after the multiplication.

当您需要除以常数或连续多次除以同一变量时，乘以倒数效果很好。
您可以在 Agner Fog's assembly library 中找到演示这一概念的非常酷的汇编代码。 。

切换和添加/替换
右移是除以二 shr -(R减少)。
左移是乘以二 shl -(较大较大)。
在此过程中，您可以通过加法和减法来纠正非 2 的幂。

//Multiply by 7
mov ecx,eax
shl eax,3    //*8
sub eax,ecx  //*7

使用此方法除以 2 的幂以外的除法很快就会变得复杂。
您可能想知道为什么我要以奇怪的顺序执行操作，但我正在尝试制作 dependency chain尽可能短，以最大化可以并行执行的指令数量。

使用 Lea
Lea是一条计算地址偏移量的指令。
它可以在一条指令中计算 2、3、4、5、8 和 9 的倍数。
就像这样:

                      //Latency on AMD CPUs (K10 and later, including Jaguar and Zen)
                      //On Intel all take 1 cycle.
lea eax,[eax+eax]     //*2     1 cycle      
lea eax,[eax*2+eax]   //*3     2 cycles
lea eax,[eax*4]       //*4     2 cycles   more efficient: shl eax,2 (1 cycle)
lea eax,[eax*4+eax]   //*5     2 cycles 
lea eax,[eax*8]       //*8     2 cycles   more efficient: shl eax,3 (1 cycle)
lea eax,[eax*8+eax]   //*9     2 cycles

但请注意 lea带有乘法器(比例因子)的指令在从 K10 到 Zen 的 AMD CPU 上被视为“复杂”指令，并且具有 2 个 CPU 周期的延迟。在早期的 AMD CPU (k8) 上，lea即使使用简单的 [reg+reg] 也总是有 2 个周期的延迟或[reg+disp8]寻址模式。

AMD
Agner Fog 的指令表对于 AMD Zen 来说是错误的:根据 InstLatx64 ( http://instlatx64.atw.hu/ )，3 分量或缩放索引 LEA 在 Zen 上仍然是 2 个周期(每个时钟吞吐量只有 2 个而不是 4 个)。此外，与早期的 CPU 一样，在 64 位模式下 lea r32, [r64 + whatever]有2个周期的延迟。所以使用lea rdx, [rax+rax]实际上更快而不是lea edx, [rax+rax]在 AMD CPU 上，与 Intel 不同，Intel 将结果截断为 32 位是免费的。

使用 shl 可以更快地完成 *4 和 *8因为简单的转变只需要一个周期。

从好的方面来说，lea不改变标志，并且允许自由移动到另一个目标寄存器。因为lea只能左移 0、1、2 或 3 位(也称为乘以 1、2、4 或 8)，这是您获得的唯一中断。

英特尔
在 Intel CPU(Sandybridge 系列)上，任何 2 组件 LEA(只有一个 + )都具有单周期延迟。所以lea edx, [rax + rax*4]具有单周期延迟，但 lea edx, [rax + rax + 12]有 3 个周期延迟(吞吐量更差)。 C++ code for testing the Collatz conjecture faster than hand-written assembly - why? 中详细讨论了这种权衡的示例。 .