optimization - 优化x64汇编程序MUL循环

Question

我正在写数学代码，需要快速将大量数字相乘。它分解为整数数组与单个整数的乘法。在C++中，这看起来像这样(在无符号的情况下):

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单元比(较旧的)英特尔芯片要快。

Answer 1

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

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

如果使用gcc，请在汇编器中使用函数__builtin_prefetch()或PREFETCHT0指令

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

当这项工作奏效时，结果可能是惊人的。只要循环长约一千次迭代，就可以预取a [i + 64]和r [i + 64]作为起点，并查看它对CPU的影响。您可能需要尝试更大的预取距离。