大数运算基选择测试

无心人

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: