优化x64汇编器MUL循环

我正在写数学代码，它需要快速乘以大数。 它分解为整数数组与单个整数的乘法运算。 在C ++中，它看起来像这样（在unsigned的）：

void muladd(unsigned* r, const unsigned* a, unsigned len, unsigned b) {
   unsigned __int64 of = 0;  // overflow
   unsigned i = 0;  // loop variable
   while (i < len) {
      of += (unsigned __int64)a[i] * b + r[i];
      r[i] = (unsigned)of;
      of >>= 32;
      ++i;
   }
   r[i] = (unsigned)of;  // save overflow
}

我手动展开了这个循环，将其转换为64位并在.asm编译器输出上工作以进一步优化它。 主.asm循环现在看起来像这样：

mov   rax, rdi                             ; rdi = b
mul   QWORD PTR [rbx+r10*8-64]             ; rdx:rax = a[i] * b; r10 = i
mov   rsi, QWORD PTR [r14+r10*8-64]        ; r14 = r; rsi = r[i]
add   rax, rsi
adc   rdx, 0
add   rax, r11                             ; r11 = of (low part)
adc   rdx, 0
mov   QWORD PTR [r14+r10*8-64], rax        ; save result
mov   r11, rdx

; this repeats itself 8 times with different offsets

当我对此进行基准测试时，发现我的Core2 Quad上的每乘法平均需要大约6.3个周期。

我的问题是：我能以某种方式加快速度吗？ 不幸的是，我看不到任何方法来避免其中的一个增加，并且乘法总是需要RDX：RAX，所以我需要移动数据并且不能排序“并行乘法”。

任何想法的人？

更新：经过一些更多的测试后，我设法将速度提高到每个64位MUL约5.4个周期（包括所有添加，移动和循环开销）。 我想这是关于Core2的最佳选择，因为Core2没有非常快速的MUL指令：吞吐量为3，延迟为6（7）个周期。 吞吐量为1，等待时间为3（4）个周期，桑迪桥将会更好。

关于GMP的少得多：我从他们的源代码中得到了这个数字，在我看来这是一个理论数字。 但可以肯定的是，这是一个计算AMD K9 CPU的数字。 从我读过的内容来看，AMD收集的MUL单元比（旧的）英特尔芯片更快。

---

我曾经写过一个看起来很像这样的循环，对很多数据进行最少量的处理，结果是循环受到内存速度的限制。

我会尝试预取[i]和r [i]

如果使用gcc，则在汇编器中使用函数__builtin_prefetch（）或PREFETCHT0指令

http://gcc.gnu.org/onlinedocs/gcc-3.3.6/gcc/Other-Builtins.html

当这项工作结果可以是戏剧性的。 只要循环长达一千次左右，我就会预取[i + 64]和r [i + 64]作为起点，看看它在CPU上的差异。 您可能需要尝试更大的预取距离。

---

看起来你的例程可以从SSE中受益。 PMULLD和PADDD看起来像是相关的说明。 不知道为什么你的编译器不能从中产生SSE。

---

我只想指出，循环计数是毫无用处的，因为您的指令将被转换为微码，该微码将根据cpu正在执行的所有内容按顺序执行或暂停执行。 如果你有一个快速的例程，你可以尝试去除一个理论循环，除非你知道你的例程总是完全独立运行。

链接地址: http://www.djcxy.com/p/65005.html

上一篇: Optimizing x64 assembler MUL loop

下一篇: NSPredicate for property of object in NSArray of NSArray