优化x64汇编程序MUL循环

Question

我正在编写需要快速乘以大数的数学代码.它分解为整数数组与单个整数的乘法.在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)个周期.Sandy桥将更好,吞吐量为1,延迟为3(相当于4)个周期.

关于GMP的数量要少得多:我从源代码中得到了它,在我看来它是一个理论数字.但可以肯定的是,它是为AMD K9 CPU计算的数字.从我所读到的内容来看,我认为AMD拥有比(较旧的)英特尔芯片更快的MUL单元.

Answer 1

看来您的日常生活可以从 SSE 中受益。PMULLD 和 PADDD 似乎是相关指令。不知道为什么你的编译器不从中生成 SSE。