B计划之长加法最佳算法讨论

无心人

那你就想错了啊
无论如何进制一旦超过16bit
那就无法避免 adc啊

liangbch

关于采用不同基的2进制大数加法 的性能测试已经完成。下面给出在2台电脑上的测试数据。所有函数均计算4096 * 32 bit 的加法。对于基为$2^32$的版本，长度为4096个DWORD, 对于基为$2^30$的版本，长度为4370个DWORD.测试次数为10万次。

函数	PIV 2.6	PM 1.7
binAdd_ALU	1891.065 ms	3254.955 ms
binAdd_GMP_ALU_8way_unroll	1342.035 ms	1029.400 ms
binAdd_Yaos_MMX_4way_unroll	770.005 ms	1091.425 ms
base30_ALU	1183.230 ms	1456.105 ms
binAdd_base30_ALU_4way_unroll	1211.250 ms	1159.940 ms
binAdd_base30_ALU_8way_unroll	1200.435 ms	1052.400 ms
binAdd_Base30_MMX_4way_unroll	891.210 ms	1414.805 ms

函数说明：
  binAdd_ALU 为基为$2^32$的最普通的版本，未使用循环展开技术。
  binAdd_GMP_ALU_8way_unroll 的代码源于GMP，基为$2^32$的ALU版本，使用8路循环展开技术。
  binAdd_Yaos_MMX_4way_unroll 源于yaos的代码, 基为$2^32$的MMX版本，使用64bit MMX 寄存器进行计算。

  base30_ALU为基为$2^30$的最普通的版本，未使用循环展开技术。
  binAdd_base30_ALU_4way_unroll，为基为$2^30$的ALU版本，使用4路循环展开技术。
  binAdd_base30_ALU_8way_unroll，为基为$2^30$的ALU版本，使用4路循环展开技术。
  binAdd_Base30_MMX_4way_unroll，为基为$2^30$的MMX版本，使用8路循环展开技术。

性能分析：
1. 在PIV 电脑上，不同版本的速度对比
1）MMX 版本明显优于ALU版本，binAdd_Yaos_MMX_4way_unroll 比 binAdd_GMP_ALU_8way_unroll 快了 74%，binAdd_Base30_MMX_4way_unroll 比 binAdd_base30_ALU_4way_unroll 快了36%。

2）循环展开提速不明显。 8路循环展开的版本比binAdd_GMP_ALU_8way_unroll 比 普通版本提速仅 40%， 而另一个8路循环展开的版本仅比4路循环展开的版本提速 0.9%。

3）基为$2^30$的ALU版本比基为$2^32$的版本快11.7%。但MMX 基为$2^30$的版本则比基为$2^32$的版本更慢，binAdd_Base30_MMX_4way_unroll 比binAdd_Yaos_MMX_4way_unroll 慢 15.7%


2. 在PM电脑上，不同版本的速度对比。
1）MMX 版本要比ALU版本差或者大体持平binAdd_Yaos_MMX_4way_unroll 与add_GMP_ALU_8way_unroll 大体持平，binAdd_Base30_MMX_4way_unroll 比 binAdd_base30_ALU_4way_unroll 慢了21.9%。

2）循环展开提速非常明显。 8路循环展开的版本比binAdd_GMP_ALU_8way_unroll 竟达普通版本的316%， 而另一个8路循环展开的版本仅比4路循环展开的版本提速 10.2%。

3）基为$2^30$的ALU版本和基为$2^32$的版本基本持平。但MMX 基为$2^30$的版本则比基为$2^32$的版本更慢，binAdd_Base30_MMX_4way_unroll 比binAdd_Yaos_MMX_4way_unroll 慢了29.6%。
3） 不论是基为$2^30$的版本还是基为$2^32$的版本，不是用循环展开的版本都是最慢的。
总结，就加法而言，在PIV电脑，基为$2^32$的MMX版本是最好的选择，而对于ALU版本，基为$2^30$的版本则胜过基为$2^32$。而在PM电脑，基为$2^32$的ALU版本，MMX版本和基为$2^30$的ALU版都相差不大。

liangbch

本帖给出 7个不同2进制大数加法函数和测试程序的源代码。

无心人

还好还好
没有出乎意料的问题

你觉得做个8路展开的32Bit MMX能否在PM上超过2^30?

无心人

还有 你的乘法能做4路展开否？

无心人

有疑问

4路展开
你怎么在开头处理剩余部分？

无心人

我觉得有点不符合16字节对齐的精神
因为Cache是以64字节读取的

liangbch

回24#楼，我觉得在PM上，应该可超过，但幅度很小。
  另外，采用$2^30$的进制，还有许多好处。如计算 A=A+B+C+D,如果采用$2^32$进制，需要调用4次大数加法，每次大数加法都需要处理加法和进位，而采用$2^30$的进制，可以分2次做，第1次计算A=A+B+C+D不考虑进位。第2次对结果进行一个规格化，这样比做4次大数加法要更快些。 A=A+B+C+D 这样的计算，会在toom-3中用到。
  回25楼，我到目前为止并没有实现任意长度的2进制大数乘法。但实现过$10^9$的进制的大数乘法，所以可采用同样的思路来做。我的做法不是4路也不是8路循环展开，而类似于16路循环展开。
  回27楼，如果非要16字节对齐，则开头和结尾都要进行额外处理，代码很复杂，开头进行收尾处理的好处是代码很简单。另外16字节对齐并无必要，即使使用SSE2指令，也有movdqu可使用，movdqu 比16进制对齐的指令movdqa快的有限。

[ 本帖最后由 liangbch 于 2008-4-16 15:15 编辑 ]

无心人

a=a+b+c+d要手工写函数
编译器不会做的

无心人

我的那个清零函数就是16字节对齐的
确实复杂