优化x64汇编程序MUL循环-Java 学习之路

我正在编写需要快速乘以大数字的数学代码 . 它分解为整数数组与单个整数的乘法 . 在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，所以我需要移动数据并且不能排序“并行乘法” .

任何人的想法？

Update: 经过多次测试后，我设法将每个64位MUL的速度提高到大约5.4个周期（包括所有添加，移动和循环开销） . 我猜这是关于Core2最好的，因为Core2没有非常快的MUL指令：它的吞吐量为3，延迟为6（相当于7）个周期 . Sandy桥将更好，吞吐量为1，延迟为3（相当于4）个周期 .

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

4 回答

0

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

我试着预取[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有多大的不同 . 您可能需要尝试更大的预取距离 .

回复于 2024-04-27T09:29:47+08:00
-1

我只想指出循环计数相当无用，因为你的指令将被转换为微码，这些微码将按顺序执行或暂停，具体取决于cpu正在做的其他事情 . 如果你有一个快速的例行程序，那么除非你知道你的例程将始终完全隔离，否则尝试削减理论周期并不是很有成效 .

回复于 2024-04-27T09:29:47+08:00
0

在通话之前，r是否包含重要内容？

如果确实如此，并且你正在积累它，那么现在就停止阅读 .

如果它不总是累积到零上，并假设你正在寻找一种方法来消除从r读取的需要并将"save result" MOV 转换为 MOVNT （内在函数中的 _mm_stream_ps ） .

这可以显着提高性能 . 怎么样？目前，您的缓存从a获取缓存行，从r获取缓存行并将缓存行写回r . 通过所谓的流媒体存储，你可以切换到使用高于某个缓存大小相关阈值的流式存储（并使用常规移动运行almost twice as fast作为memcpy） .

回复于 2024-04-27T09:29:47+08:00
1

看起来您的日常工作可以从SSE中受益 . PMULLD和PADDD似乎是相关说明 . 不确定为什么你的编译器不会产生SSE .

回复于 2024-04-27T09:29:47+08:00

优化x64汇编程序MUL循环

4 回答

相关问题