大数运算基选择测试

无心人

25结论似乎是错误的 抱歉！

无心人

指出你的一个错误吧 你似乎480bit乘都是循环展开的 但我们需要的是可以处理任何输入的通用函数 不要说循环展开等于通用的比较结果 考虑展开情况下你可以充分的隔离依赖指令 使指令延迟的副作用最小 而且还能动用最大化的mm寄存器 所以很多优化在循环情况下是不能使用的 所以必须使用循环版本 最简单的，乘法延迟>=6，要在6个时钟后才能用 所以循环情况下，最小的每双字的消耗就是6 而展开情况下，可充分利用每时钟能发送一条乘法的优势 使乘法延迟的损耗最小化 循环时的时间你算过么？ 我想你的P4 2.6应该在590ms左右

liangbch

遇到麻烦了！！！ 将yaos写的代码添加到测试环境，这样一来，总共被测函数达到7个，奇怪的是，但打开这些函数的其中几个，会对基为 $2^30 $SSE2版本的性能造成影响。 比如 UInt480x480_MMX 和 UInt480x480_yaos（yaos写的代码，稍加封装）测试其中的一个或者几个，竟然对 UInt480x480_base30_MMX 性能造成明些的影响。 UInt480x480_MMX UInt480x480_yaos UInt480x480_base30_MMX 用时间 关闭（不测试） 关闭（不测试） 394ms 关闭（不测试） 打开（测试） 394ms 打开（测试） 关闭（不测试） 396ms 打开（测试） 打开（测试） 575ms 另外，打开或者 UInt480x480_ALU2 或 UInt480x480_ALU 也会对最后2个基为$2^30$ SSE2版本造成影响。测试发现，关闭UInt480x480_ALU2 会造成 基为 $2^30 $SSE2版本变慢。 还有一点，我的完全 使用循环展开 的版本（基同为为$2^32$) 竟比 yaos的慢，我也不能给出合理的解释。 下面为在PIV2.6G下的测试结果. 关闭最后3个基为 2^30 的函数后的测试结果。 Test function: UInt480x480_ALU(..) 1000000 times... Elapsed time: 1287.924 ms Test function: UInt480x480_ALU2(..) 1000000 times... Elapsed time: 1244.897 ms Test function: UInt480x480_MMX(..) 1000000 times... Elapsed time: 996.383 ms Test function: UInt480x480_yaos(..) 1000000 times... Elapsed time: 752.210 ms 关闭最后UInt480x480_MMX和 UInt480x480_yaos 后的测试结果。 Test function: UInt480x480_ALU(..) 1000000 times... Elapsed time: 1282.592 ms Test function: UInt480x480_ALU2(..) 1000000 times... Elapsed time: 1243.553 ms Test function: UInt480x480_base30_ALU(..) 1000000 times... Elapsed time: 1252.155 ms Test function: UInt480x480_base30_MMX(..) 1000000 times... Elapsed time: 397.942 ms Test function: UInt480x480_base30_SSE2(..) 1000000 times... Elapsed time: 533.329 ms 代码暂缓公布，回去写几个通用版本，可以在参数中指定被乘数和乘数的长度。将使用部分循环展开技术。接口类似为： void Mul_func(DWORD *result,const DWORD *left, const DWORD *right, DWORD sLeft,DWORD sRight);

无心人

呵呵 我说快也快不了多少么 循环版是一个乘两个加 极端有规律的 你线程最大化优先级了么？ ====================== 部分循环展开 就是一次乘4个吧 要处理非4倍数的部分

liangbch

原帖由 无心人 于 2008-4-9 20:46 发表 部分循环展开 就是一次乘4个吧 要处理非4倍数的部分

回楼上，不是的，因为我使用的循环结构和你的不同，所以不能使用 4路循环展开。

无心人

那我想做4路展开 如果你的代码时间不能达到我时间的80%以内 你的代码是很没效率的， 因为加法是肯定慢的 加法不可能快于2^32的基

liangbch

33# 楼提到，“还有一点，我的完全 使用循环展开 的版本（基同为为232) 竟比 yaos的慢，我也不能给出合理的解释。” 现在终于找到原因了，我写的那个UInt480x480_MMX有冗余指令，稍作优化后，速度迅速提升，从之前的989.54ms提升到 481.540 ms，竟快了1倍多，提速太多了。我无法给出合理的解释。 将现在的基为$2^32$的函数 Int480x480_MMX 和 基为$2^30$的函数UInt480x480_base30_MMX做一个对比，则后者比前者快了25%。 我也写了一个可类似yaos的非循环展开的版本，速度比yaos的那个版本快了8%左右。可参考楼下给出的源代码。 这个数据（提速到125%）可比以前的250%更合理一点，但单从指令条数分析，速度应该提升到200%以上才对。但MMX指令的版本怪就怪在 速度的变化无法琢磨，无法用理论的方法给出合理的解释。无论如何，让我们见识了一个可以大幅提高大数乘法运行速度的新途径，提高的幅度太大了，太出人所料了。 6个版本的速度对比。 Test function: UInt480x480_ALU(..) 1000000 times... Elapsed time: 1244.770 ms Test function: UInt480x480_ALU2(..) 1000000 times... Elapsed time: 1216.745 ms Test function: UInt480x480_MMX(..) 1000000 times... Elapsed time: 481.540 ms Test function: UInt480x480_base30_ALU(..) 1000000 times... Elapsed time: 1222.405 ms Test function: UInt480x480_base30_MMX(..) 1000000 times... Elapsed time: 385.115 ms Test function: UInt480x480_base30_SSE2(..) 1000000 times... Elapsed time: 527.090 ms 5个基同为$2^32$的版本的速度对比： Test function: UInt480x480_ALU(..) 1000000 times... Elapsed time: 1248.710 ms Test function: UInt480x480_ALU2(..) 1000000 times... Elapsed time: 1219.125 ms Test function: UInt480x480_MMX(..) 1000000 times... Elapsed time: 482.380 ms Test function: UInt480x480_MMX2(..) 1000000 times... Elapsed time: 693.360 ms Test function: UInt480x480_yaos(..) 1000000 times... Elapsed time: 725.490 ms

liangbch

本压缩包包含2个工程文件，geneCodes.dsp 和binMulTest.dsp。前者用来生成后者的部分原代码。 运行geneCodes.exe,将生成3个.c文件(本来可生成6个文件的,在上载该压缩包前作了处理,屏蔽了3个基为$2^32$3个函数的输出) 使用后者之前,先运行geneCodes.exe,生成后者所需的3个文件.然后可打开binMulTest.dsp 并编译即可生成用来一个名为 binMulTest.exe,该程序可计算2个480bit的乘积,使用了几种不同的算法,给给出他们的速度.需要注意的是，binMulTest的源代码中并没有包含基为$2^30$的几个函数，而事先编译好的binMulTest.exe 则包含了所有6个函数的速度测试。

无心人

我这里差别也是不大 ALU 1696 ALU2 1668 MMX 646 30_MMX 549 30_SSE2 777

无心人

写了一个四路并行乘法 有时间调试下看效果如何？ mov esi, [left] mov edi, [right] mov ebx, [result] mov ecx, [sLeft] mov edx, [sRight] cmp ecx, edx jbe noExchange xchg esi, [right] xchg edi, [left] xchg ecx, [sRight] xchg edx, [sLeft] noExchange: test ecx, -1 je exit1 //长度0 test edx, -1 je exit1 //长度0 mov ecx, 0 pxor mm0, mm0 movd mm7, [esi] add esi, 4 mov eax, edx shr edx, 2 je firstLoop2 //不足4个 firstLoop1: movd mm1, [edi] pmuludq mm1, mm7 movd mm2, [edi+4] pmuludq mm2, mm7 movd mm3, [edi+8] pmuludq mm3, mm7 movd mm4, [edi+12] pmuludq mm4, mm7 add edi, 16 paddq mm0, mm1 movd [ebx], mm0 psrlq mm0, 32 paddq mm0, mm2 movd [ebx+4], mm0 psrlq mm0, 32 paddq mm0, mm3 movd [ebx+8], mm0 psrlq mm0, 32 paddq mm0, mm4 movd [ebx+12], mm0 psrlq mm0, 32 add ebx, 16 sub edx, 1 jne firstLoop1 firstLoop2: mov edx, eax and edx, 3 je exitFirstLoop firstLoop3: movd mm1, [edi] pmuludq mm1, mm7 add edi, 4 paddq mm0, mm1 movd [ebx], mm0 psrlq mm0, 32 add ebx, 4 sub edx, 1 jne firstLoop3 exitFirstLoop: movd [ebx], mm0 add ecx, 1 cmp ecx, [sLeft] jae exit1 //左操作数就一个双字 add esi, 4 outLoop1: movd mm7, [esi] mov ebx, [result] lea ebx, [ebx+ecx*4] mov edi, [right] mov edx, [sRight] pxor mm0, mm0 mov eax, edx shr edx, 2 je innerLoop2 innerLoop1: movd mm1, [edi] pmuludq mm1, mm7 movd mm5, [ebx] movd mm2, [edi+4] pmuludq mm2, mm7 movd mm6, [ebx+4] movd mm3, [edi+8] pmuludq mm3, mm7 movd mm4, [edi+12] pmuludq mm4, mm7 add edi, 16 paddq mm0, mm1 paddq mm0, mm5 movd [ebx], mm0 movd mm5, [ebx+8] psrlq mm0, 32 paddq mm0, mm2 paddq mm0, mm6 movd [ebx+4], mm0 movd mm6, [ebx+12] psrlq mm0, 32 paddq mm0, mm3 paddq mm0, mm5 movd [ebx+8], mm0 psrlq mm0, 32 paddq mm0, mm4 paddq mm0, mm6 movd [ebx+12], mm0 psrlq mm0, 32 add ebx, 16 sub edx, 1 jne innertLoop1 innerLoop2: mov edx, eax and edx, 3 je outLoop2 innerLoop3: movd mm1, [edi] pmuludq mm1, mm7 movd mm5, [ebx] add edi, 4 paddq mm0, mm1 paddq mm0, mm5 movd [ebx], mm0 psrlq mm0, 32 add ebx, 4 sub edx, 1 jne firstLoop2 outLoop2: movd [ebx], mm0 add ecx, 1 cmp ecx, [sLeft] jb outLoop1 exit1: