11

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

分析表明，我的代码在 add() 和 sub() 例程中运行的时间高达 25%，因此它们尽可能快很重要。但我还没有看到很大的潜力。也许你可以给我一些帮助、建议、见解或想法。我会测试它们并回复你。

到目前为止，我的 add 例程做了一些设置，然后使用了 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 的代码。

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

一些问题：

  • 使用“加载、加载、添加、存储”结构有用还是“加载、添加到内存”有帮助？到目前为止，我的测试没有显示出任何优势。
  • 像往常一样，SSE(2,3,4) 没有帮助？
  • 寻址（缩放索引加基数加偏移量）影响严重吗？我可以ADD r11, 8改用。
  • 循环展开怎么样？我读到展开对 Sandy Bridge 架构不利（Agner Fog http://www.agner.org/optimize/）。是首选还是避免？
  • （编辑）我可以使用 SSE 寄存器从内存中以更大的块加载和存储字，并有效地与通用寄存器和 SSE 寄存器交换字吗？

我非常感谢任何评论。

4

3 回答 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 或类似方法无济于事，如此处所述： 长整数例程可以从 SSE 中受益吗？

于 2012-12-20T15:29:20.293 回答
2

最困难的依赖是每个内存块之间的进位传播；我会尝试首先设计一种处理方法。

以下片段模拟进位传播，但具有不使用进位标志的“好处”。这可以为三个或四个单独的线程并行化，每个线程产生一个半数，相隔约 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 的无进位加法大约需要 550 毫秒（1e9 个字），模拟进位大约需要 1020 毫秒，4 路并行版本需要大约 820 毫秒（没有任何汇编程序优化）。

架构优化可能包括使用冗余数字系统，其中进位不必一直传播，并且可以无限期地推迟对进位的评估。

于 2012-12-20T15:07:46.103 回答
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
于 2012-12-20T14:18:18.060 回答