无心人 发表于 2008-4-8 16:54:23

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

liangbch 发表于 2008-4-8 17:05:14

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

无心人 发表于 2008-4-8 17:16:03

movd mm1,
movd mm2,
paddq mm1,mm2
movd mm3,
movd mm4,
paddq mm3, mm4
movd mm5,
movd mm6,
paddq mm5, mm6
movd mm7,
movd mm2,
paddq mm7, mm2
paddq mm0, mm1
movd , mm0
psrlq mm0, 32
paddq mm0, mm3
movd , mm0
psrlq mm0, 32
paddq mm0, mm5
movd , mm0
psrlq mm0, 32
paddq mm0, mm7
movd , 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 编辑 ]

无心人 发表于 2008-4-8 17:38:36

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

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

无心人 发表于 2008-4-8 17:46:45

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


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


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

liangbch 发表于 2008-4-8 18:05:22

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

无心人 发表于 2008-4-8 19:46:56


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

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

liangbch 发表于 2008-4-10 19:44:25

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

无心人 发表于 2008-4-10 20:07:42

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

liangbch 发表于 2008-4-10 20:49:51

这次你说对了。但是,AND指令很快,相对于使用2^32必须使用ADC 指令,速度也应该快不少,另外使用一些快速的ALU指令,也许比64bit的SSE2加法指令更快。
页: 1 [2] 3 4 5 6
查看完整版本: B计划之长加法最佳算法讨论