加速x64汇编器ADD循环-Java 学习之路

我正在研究很长整数的乘法运算（大约100,000个十进制数字） . 作为我的图书馆的一部分，我要添加两个长数字 .

分析表明我的代码在add（）和sub（）例程中运行的时间高达25％，因此尽可能快地运行它们非常重要 . 但我还没有看到太大的潜力 . 也许你可以给我一些帮助，建议，见解或想法 . 我会测试它们然后再回复你 .

到目前为止，我的添加例程进行了一些设置，然后使用了8次展开的循环：

mov rax, QWORD PTR [rdx+r11*8-64]
mov r10, QWORD PTR [r8+r11*8-64]
adc rax, r10
mov QWORD PTR [rcx+r11*8-64], rax

然后是7个具有不同偏移的块然后循环 .

我之前尝试从内存中加载值，但这没有帮助 . 我想那是因为好的预取 . 我使用Intel i7-3770 Ivy Bridge 4核CPU . 但我想编写适用于任何现代CPU的代码 .

Edit ：我做了一些时间：它在大约2.25个周期/单词中增加了1k个单词 . 如果我移除ADC，那么只剩下MOV，它仍然需要大约1.95个周期/字 . 所以主要的瓶颈似乎是内存访问 . 库 memcpy() 工作在大约0.65个周期/字，但只有一个输入，而不是两个 . 我猜，因为它使用了SSE寄存器，所以速度要快得多 .

一些问题：

使用"load, load, add, store"结构或"load, add-to-memory"帮助有用吗？到目前为止，我的测试没有显示出任何优势 .
像往常一样，没有SSE（2,3,4）的帮助预期？
寻址（缩放索引加基数加偏移）是否会严重影响？我可以改用 ADD r11, 8 .
循环展开怎么样？我读到展开对Sandy Bridge架构很糟糕（Agner Fog http://www.agner.org/optimize/） . 它是首选还是避免？
(Edit) 我可以使用SSE寄存器从存储器加载和存储更大块的字，并有效地与通用寄存器和SSE寄存器交换字吗？

我非常感谢任何评论 .

3 回答

3
我非常确定memcpy更快，因为它在执行下一个操作之前不依赖于正在获取的数据 .

如果您可以安排代码，以便它执行以下操作：
```
mov rax, QWORD PTR [rdx+r11*8-64]
mov rbx, QWORD PTR [rdx+r11*8-56]
mov r10, QWORD PTR [r8+r11*8-64]
mov r12, QWORD PTR [r8+r11*8-56]
adc rax, r10
adc rbx, r12
mov QWORD PTR [rcx+r11*8-64], rax
mov QWORD PTR [rcx+r11*8-56], rbx
```
我不是100％确定-56的偏移是适合您的代码，但概念是“正确的” .

我还会考虑缓存命中/缓存冲突 . 例如 . 如果你有三个数据块[你可能会这样做]，你要确保它们没有与缓存中的相同偏移对齐 . 一个不好的例子是，如果您从缓存中的同一位置分配所有块的缓存大小的倍数 . 过度分配并确保您的不同数据块至少偏移512字节[因此分配4K超大，并向上舍入到4K边界起始地址，然后将512添加到第二个缓冲区，将1024添加到第三个缓冲区]

如果您的数据足够大（大于L2缓存），您可能需要使用MOVNT来获取/存储数据 . 这将避免读入缓存 - 当你拥有非常大的数据时，这只会带来好处，下一次读取只会导致你可能发现“有用”的其他内容被踢出缓存，你将无法获得在你将它从缓存中踢出之前回到它 - 所以将值存储在缓存中实际上并没有帮助......

编辑：使用SSE或类似功能无济于事，如下所述：Can long integer routines benefit from SSE?
回复于 2024-05-05T02:22:51+08:00
2
最困难的依赖是每个存储块之间的进位传播;我试着先设备一种处理它的方法 .

以下片段模拟进位传播，但"benefit"不使用进位标志 . 这可以并行化为三个或四个单独的线程，每个线程产生一半携带大约25000个十进制数字（或10000字节） . 然后，那些只影响一个字节，字，双字等的载荷的概率将渐近地达到零 .
```
long long carry=0;
 for (int i=0;i<N;i++) {
     carry += (long long)*a++ + (long long)*b++;
     *c++ = carry; carry>>=32;
 }
```
根据我的分析，使用xmm的无进位加法需要~550ms（1e9个字），模拟进位需要~1020ms，4路并行化版本需要~820ms（没有任何汇编器优化） .

架构优化可以包括使用冗余数字系统，其中进位不必一直传播，并且进位的评估几乎可以无限延迟 .
回复于 2024-05-05T02:22:51+08:00
1
首先尝试预取数据（您可以先尝试将更多数据块读取到x64寄存器然后进行计算），检查数据是否在内存中正确对齐，将循环代码放在标签对齐的16处，尝试删除SIB寻址

你也可以尝试将您的代码缩短为：
```
mov rax, QWORD PTR [rdx+r11*8-64]
adc rax, QWORD PTR [r8+r11*8-64]
mov QWORD PTR [rcx+r11*8-64], rax
```
回复于 2024-05-05T02:22:51+08:00

加速x64汇编器ADD循环

3 回答

相关问题