程序集8086 - 在没有MUL和DIV指令的情况下实现任何乘法和除法

Question

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

Answer 1

就像汇编中的其他所有东西一样,有许多方法可以进行乘法和除法.

1. 通过乘以倒数值来划分.
2. 使用shift并添加/ subs而不是乘法.
3. 使用lea(仅乘法)的地址计算选项.

神话破灭

因为它们需要大量的CPU周期

MUL并且IMUL是极快的现代CPU的,请参阅:http://www.agner.org/optimize/instruction_tables.pdf
DIV和IDIV是一直以来均非常缓慢.

英特尔Skylake的示例(第217页):

MUL,IMUL r64:延迟3个周期,相互吞吐量1个周期.

请注意,这是乘以两个64 的最大延迟!位值.
如果它所做的全部是乘法,CPU可以在每个CPU周期完成这些乘法之一.
如果你认为上面的例子使用shift并且加上乘以7有一个4个周期的延迟(3个使用lea).在现代CPU上没有真正的方法可以击败普通的倍数.

乘以相互的乘法

根据Agner Fog的asm lib指令第12页:

大多数微处理器的分工都很慢.在浮点计算中,我们可以通过乘以倒数来更快地执行具有相同除数的多个除法,例如:

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

可以改为:

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

如果我们想要用整数做类似的事情,那么我们必须将倒数除数除以2n,然后在乘法后将n位移到右边.

当你需要除以一个常数或者你连续多次除以同一个变量时,乘以倒数的效果很好.
你可以在Agner Fog的装配库中找到非常酷的装配代码来展示这个概念.

移位和加/右移位是两除shr- (R educe).
向左移动是乘以2 shl- (L arger).
您可以添加和减去以一路纠正两个非幂.

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

使用这种方法除2的幂以外的除法很快变得复杂.
您可能想知道为什么我以奇怪的顺序执行操作,但我正在尝试使依赖链尽可能短,以最大化可以并行执行的指令数.

使用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乘法器(比例因子)被认为是AMD CPU从K10到Zen的"复杂"指令,延迟时间为2个CPU周期.在早期的AMD CPU(k8)上,lea即使使用简单[reg+reg]或[reg+disp8]寻址模式,也始终具有2个周期的延迟.

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 更快,不像英特尔那样将结果截断为32位是免费的.

使用*4和*8可以更快地完成,shl因为简单的移位只需要一个周期.

在正面,lea不会改变标志,它允许自由移动到另一个目的地寄存器.因为lea只能向左移动0,1,2或3位(也就是乘以1,2,4或8),所以这是你得到的唯一中断.

英特尔
在Intel CPU(Sandybridge系列)上,任何双组件LEA(仅一个+)都具有单周期延迟.因此lea edx, [rax + rax*4]具有单周期延迟,但lea edx, [rax + rax + 12]具有3个周期延迟(和更差的吞吐量).在C++代码中详细讨论了这种权衡的一个例子, 用于比手写汇编更快地测试Collat​​z猜想 - 为什么？.

Answer 2

如果您还记得的话，实现乘法会更容易，shl 操作执行与将指定操作数乘以 2 相同的操作。向左移动两位位置会将操作数乘以四。左移三位位置会将操作数乘以八。一般来说，将操作数左移 n 位会将其乘以 2n。任何值都可以使用一系列移位和加法或移位和减法乘以某个常数。例如，要将 ax 寄存器乘以 10，只需将其乘以 8，然后加上原始值的两倍即可。即，10*ax = 8*ax + 2*ax。完成此操作的代码是

            shl     ax, 1           ;Multiply AX by two
            mov     bx, ax          ;Save 2*AX for later
            shl     ax, 1           ;Multiply AX by four
            shl     ax, 1           ;Multiply AX by eight
            add     ax, bx          ;Add in 2*AX to get 10*AX

使用 shl 可以比使用 mul 指令更快地将 ax 寄存器（或任何寄存器）乘以大多数常量值。这似乎令人难以置信，因为计算该乘积只需要两条指令：

            mov     bx, 10
            mul     bx

但是，如果查看时序，就会发现在 80x86 系列的大多数处理器上，上面的移位和加法示例所需的时钟周期比 mul 指令要少。当然，代码会稍大一些（几个字节），但性能的提高通常是值得的。当然，在后来的 80x86 处理器上，mul 指令比早期的处理器要快很多，但移位和加法方案在这些处理器上通常也更快。

您还可以使用带移位的减法来执行乘法运算。考虑以下乘以七：

            mov     bx, ax          ;Save AX*1
            shl     ax, 1           ;AX := AX*2
            shl     ax, 1           ;AX := AX*4
            shl     ax, 1           ;AX := AX*8
            sub     ax, bx          ;AX := AX*7

这直接由 ax*7 = (ax*8)-ax 这一事实得出。

初学汇编语言的学生常犯的一个错误是减或加一或二，而不是 ax*1 或 ax*2。以下不计算 ax*7：

            shl     ax, 1
            shl     ax, 1
            shl     ax, 1
            sub     ax, 1

它计算 (8*ax)-1，完全不同的东西（当然，除非 ax = 1）。使用移位、加法和减法执行乘法运算时要小心这个陷阱。

除法有点难，需要思考......