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

无心人

那必须保证数字bit长度是128倍数

liangbch

No,循环展开可处理任意长度，加上一个 收尾处理部分 即可。
  如长度为  103，使用4路循环展开，则
  第1部分：循环步：25，每步 处理 4DWORD， 总共处理 25×4=100 DWORD
  第2部分（收尾部分)：循环步：3， 每步处理 1 DWORD， 总共处理 3×1=3 DWORD
  二者合计，共处理了 103 DWORD。

无心人

movd mm1, [esi]
movd mm2, [edi]
paddq mm1,  mm2
movd mm3, [esi+4]
movd mm4, [edi+4]
paddq mm3, mm4
movd mm5, [esi+8]
movd mm6, [edi+8]
paddq mm5, mm6
movd mm7, [esi+12]
movd mm2, [edi+12]
paddq mm7, mm2
paddq mm0, mm1
movd [ebx], mm0
psrlq mm0, 32
paddq mm0, mm3
movd [ebx+4], mm0
psrlq mm0, 32
paddq mm0, mm5
movd [ebx+8], mm0
psrlq mm0, 32
paddq mm0, mm7
movd [ebx+12], mm0
psrlq mm0, 32
add esi, 16
add edi, 16
add ebx, 16
sub ecx, 1
jne label
29条， 如果使用ecx做地址参数，可到27条
原4次循环是最低36条， 节约的有限，
主要看并行度

[ 本帖最后由 无心人 于 2008-4-16 11:30 编辑 ]

无心人

确实能提高速度
原始的3220ms/100万次*1024DWORD
4个一起2588ms/100万次*1024DWORD

不过这个128bit长度的倍数要提前做好限定
否则只能考虑在程序里处理剩余部分！！

无心人

收尾倒好做
mov ecx, [len]
mov edx, ecx
shr ecx, 2 //ecx 为128单位的数量
je  label收尾 //肯定长度不够128
。。。
。。。
//收尾
mov ecx, edx
and ecx, 3 //ecx = 尾部双字个数
je  退出 //没有尾部
。。。
。。。
//退出


如果考虑并行，还一个问题，一次加多少合适，最多加的数字是很大的
7个寄存器轮流来，可以无限并行下去， 我想合适的数字在下面中选
2, 4, 8, 16个双字一起加


===================================
刚计算了，4个一起加， 每个双字消耗约等于5时钟
一个的大概是6， 呵呵，基数太小了
改进1个时钟就造成程序复杂很多啊

liangbch

对于编写高性能的程序，常常需要权衡程序效率和复杂度之间的平衡。1路->4路，性能提高明显， 4路 -〉8路 则性能提高的就很有限了。从GMP的源代码可以看出，他使用的循环展开一般为4-6路。个人觉得4路循环展开应该是一个不错的选择，兼顾了复杂性和性能。

无心人

恩
回家路上也想了
就在四个加上最合适了
不过，29条指令消耗了大约20个时钟
不知道算不算好

=====================================
另外，似乎乘法也能一次乘四个吧

liangbch

我觉得，如果采用基为 $2^30$,使用ALU指令来做，速度应该也很快。有空我给出一个实现。

无心人

你是说加法么？
加法用2^30多一个and操作

liangbch

这次你说对了。但是，AND指令很快，相对于使用$2^32$必须使用ADC 指令，速度也应该快不少，另外使用一些快速的ALU指令，也许比64bit的SSE2加法指令更快。