大数运算基选择测试

liangbch

在38楼给出几个 以$2^32$为基，使用 MMX寄存器，可计算480bit ×480bit　的函数。其中 UInt480x480_MMX是一个使用完全循环展开，仅能计算480bit的数的版本；而UIntMul_basecase_MMX2是一个不使用循环展开，可计算任意长度的数的版本。 现在，楼主又给出一个使用4路循环展开的版本，理论上这个版本在　计算480bit × 480 bit，应该比 UIntMul_basecase_MMX2 快一些，但慢于UInt480x480_MMX 38#给出的这两个函数的原型是： void UInt480x480_MMX( unsigned long * result, const unsigned long * left, const unsigned long * right ); void UIntMul_basecase_MMX2( unsigned long * result, const unsigned long * left, const unsigned long * right, unsigned long leftLen, unsigned long rightLen );

无心人

对， 你的分析很对 看并行4路的效率了 在加法是1/6的增幅 乘法估计要更多

liangbch

乘法肯定是比1/6少。 循环展开能够提高速度的原因在于： 1.减少了数组指针的递增指令的执行次数，如下面代码中的“lea edi, [edi+4]”，“lea ebx, [ebx+4]”， 2.减少了比较和条件跳转指令的执行次数。如下面代码中的“sub ecx, 1“，"jnz mbinmul3". 而其他用来工作的指令则无法减少，另一个好处是，循环展开便于合适的安排指令，使指令间的依赖很小，但这种影响一般很小。 如果循环体很小，其中几条指令不是很耗时，则减少的这些指令占用的时间比例较大，提速明显。反之则提速不明显。对于加法，真正干活的指令占用时间少，故提升比例较高。而对于乘法，真正用来干活的指令（如pmuludq）占用的时间比例很大。故提升的比例应该很有限。

1. movd mm2, dword ptr [edi]
2. lea edi, [edi+4]
3. movd mm3, dword ptr [ebx]
4. pmuludq mm2, mm1
5. paddq mm0, mm3
6. paddq mm0, mm2
7. movd dword ptr [ebx], mm0
8. psrlq mm0, 32
9. lea ebx, [ebx+4]
10. sub ecx, 1
11. jnz mbinmul3

复制代码

无心人

可是乘法存在延迟长的问题啊 如果单循环，可能造成整个循环都在等乘法结果 而4个一起，只要一个好了 就能做部分工作， 处理完一个 也许剩下的乘法都不会再产生多余的延迟了 所以到底是你说的情况 还是我说的情况 要测试了才说的清

无心人

所以我分析下面的彩色指令都应该不占CPU额外时间 movd mm2, dword ptr [edi] lea edi, [edi+4] movd mm3, dword ptr [ebx] pmuludq mm2, mm1 paddq mm0, mm3 paddq mm0, mm2 movd dword ptr [ebx], mm0 psrlq mm0, 32 lea ebx, [ebx+4] sub ecx, 1 jnz mbinmul3

无心人

执行顺序可能是 1、movd mm2, dword ptr [edi] 1、lea edi, [edi+4] 1、movd mm3, dword ptr [ebx] 2、pmuludq mm2, mm1 2、paddq mm0, mm3 3、paddq mm0, mm2 4、movd dword ptr [ebx], mm0 4、psrlq mm0, 32 4、lea ebx, [ebx+4] 2、sub ecx, 1 5、jnz mbinmul3

liangbch

理论上，CPU存在多个执行单元，调整指令顺序，减少指令依赖可以提升速度。然而我之前的种种实验表明，这种调整指令顺序，提高并行度的做法并无多大效果，不知何故。 另一种行之有效的优化循环的办法是减少控制指令，这种做法在某些CPU效果相当明显，我们以本贴子中出现过的程序为例给予说明。 UInt480x480_yaos,UInt480x480_MMX2,UInt480x480_MMX3 这三个函数均为以普通方式计算大数乘法的函数， 程序的逻辑也相同，不过 UInt480x480_yaos多做了一些额外的工作，即需要先将目标buffer清零。 先看看他们在2种CPU的速度表现,计算2个长为15个DWORD的乘积，运行100万次 PIV 2.6 PM1.7 UInt480x480_yaos 698.655 ms 1053.610 ms UInt480x480_MMX2 671.515 ms 863.055 ms UInt480x480_MMX3 585.015 ms 798.775 ms 再分析一下这几个程序的差异，这几个程序均为2重循环，在循环体中，包括真正干活的指令和循环控制的指令，循环控制的指令又分调整数组指针或计数器的指令 和 比较/跳转指令.这3个程序中内循环指令条数分别为11，10，9，其中循环控制指令分别为4，3，2条。 第一个程序，循环控制指令是 “lea edi, [edi+4]”，“lea ebx, [ebx+4]”，“sub ecx, 1”，“jnz mbinmul3”，共4条。第一个程序，循环控制指令是“inc eax”，“cmp eax,dword ptr [esp + 16+STACK_BASE]”，“jb innerLoop”。第三个程序循环控制指令是“inc eax”，“jnz innerLoop”。 第三个程序的速度已经非常逼近完全循环展开的版本，尤其是在PM CPU。在PIV/PM,速度分别达到完全循环展开程序的82%/%95. 下面给出这三个程序调用到的子程序的完整的代码。

1. 程序UInt480x480_yaos 调用到的子程序的代码
2. void lMul_yaos(uint32 *result,
3. const uint32 *left,
4. const uint32 *right,
5. uint32 sLeft,
6. uint32 sRight)
7. {
8. __asm {
9. mov edx, sLeft
10. mov esi, dword ptr [left]
11. mov edi, dword ptr [right]
12. mov ebx, dword ptr [result]
13. mbinmul2:
14. mov eax, ebx
15. pxor mm0, mm0
16. mov ecx, sRight
17. movd mm1, dword ptr [esi]
18. movd mm4, edi
19. mbinmul3:
20. movd mm2, dword ptr [edi]
21. lea edi, [edi+4]
22. movd mm3, dword ptr [ebx]
23. pmuludq mm2, mm1
24. paddq mm0, mm3
25. paddq mm0, mm2
26. movd dword ptr [ebx], mm0
27. psrlq mm0, 32
28. lea ebx, [ebx+4]
29. sub ecx, 1
30. jnz mbinmul3
32. movd edi, mm4
33. movd dword ptr [ebx], mm0
34. mov ebx, eax
35. lea esi, [esi+4]
36. lea ebx, [ebx+4]
37. sub edx, 1
38. jnz mbinmul2
39. emms
40. }
41. }

复制代码

1. 程序UInt480x480_MMX2 调用到的子程序的代码
3. _declspec(naked)
4. void UIntMul_basecase_MMX2( unsigned long * result,
5. const unsigned long * left,
6. const unsigned long * right,
7. unsigned long leftLen,
8. unsigned long rightLen )
9. {
10. #define STACK_BASE 12
11. __asm
12. {
13. push esi
14. push edi
15. push ebp
17. mov ebp, dword ptr [esp + 4+STACK_BASE] ; result
18. mov esi, dword ptr [esp + 8+STACK_BASE] ; left
19. mov edi, dword ptr [esp + 12+STACK_BASE] ; right
20. mov ecx, dword ptr [esp + 20+STACK_BASE] ; rightLen
22. //next10:
23. cmp ecx,0
24. jz thisExit
26. //loop1_Init:
27. xor eax,eax // j=0;i<leftLen
28. pxor mm0,mm0
29. movd mm2,[edi]
30. jmp loop1_Cmp
32. loop1:
33. movd mm1,[esi+eax*4]
34. pmuludq mm1,mm2
35. paddq mm0, mm1
36. movd [ebp+eax*4],mm0
37. inc eax
38. psrlq mm0, 32 //carry
40. loop1_Cmp:
41. cmp eax,dword ptr [esp + 16+STACK_BASE] //leftLen
42. jb loop1
43. movd [ebp+eax*4],mm0
45. //outLoopInit:
46. mov ecx,1 // i=1;i<rightLen
47. jmp outLoopCmp
49. outLoop:
50. add ebp,4
51. pxor mm0,mm0
52. movd mm2,[edi+ecx*4]
53. xor eax,eax
54. jmp innerLoopCmp
56. innerLoop:
57. movd mm1,[esi+eax*4]
58. movd mm3,[ebp+eax*4]
59. pmuludq mm1,mm2
60. paddq mm0, mm1
61. paddq mm0, mm3
62. movd [ebp+eax*4],mm0
63. inc eax
64. psrlq mm0, 32 //carry
66. innerLoopCmp:
67. cmp eax,dword ptr [esp + 16+STACK_BASE] //leftLen
68. jb innerLoop
69. movd [ebp+eax*4],mm0
70. inc ecx
71. outLoopCmp:
72. cmp ecx,dword ptr [esp + 20+STACK_BASE] //rightLen
73. jb outLoop
75. thisExit:
77. pop ebp
78. pop edi
79. pop esi
81. emms
82. ret
83. }
84. }

复制代码

1. 程序UInt480x480_MMX3 调用到的子程序的代码:
3. _declspec(naked)
4. void UIntMul_basecase_MMX3( unsigned long * result,
5. const unsigned long * left,
6. const unsigned long * right,
7. unsigned long leftLen,
8. unsigned long rightLen )
9. {
10. #define STACK_BASE 12
11. __asm
12. {
13. push esi
14. push edi
15. push ebp
17. mov ebp, dword ptr [esp + 4+STACK_BASE] ; result
18. mov esi, dword ptr [esp + 8+STACK_BASE] ; left
19. mov edi, dword ptr [esp + 12+STACK_BASE] ; right
20. mov ecx, dword ptr [esp + 20+STACK_BASE] ; rightLen
22. //next10:
23. cmp ecx,0
24. jz thisExit
26. //loop1_Init:
27. xor eax,eax // j=0;i<leftLen
28. pxor mm0,mm0
29. movd mm2,[edi]
30. jmp loop1_Cmp
32. loop1:
33. movd mm1,[esi+eax*4]
34. pmuludq mm1,mm2
35. paddq mm0, mm1
36. movd [ebp+eax*4],mm0
37. inc eax
38. psrlq mm0, 32 //carry
40. loop1_Cmp:
41. cmp eax,dword ptr [esp + 16+STACK_BASE] //leftLen
42. jb loop1
43. movd [ebp+eax*4],mm0
45. //outLoopInit:
46. mov ecx,1 // i=1;i<rightLen
47. mov eax,dword ptr [esp + 16+STACK_BASE] //leftLen
48. lea esi,[esi+eax*4]
49. lea ebp,[ebp+eax*4]
50. jmp outLoopCmp
52. outLoop:
53. add ebp,4
54. pxor mm0,mm0
55. movd mm2,[edi+ecx*4]
56. mov eax,dword ptr [esp + 16+STACK_BASE] //leftLen
57. neg eax
58. jmp innerLoopCmp
60. innerLoop:
61. movd mm1,[esi+eax*4]
62. movd mm3,[ebp+eax*4]
63. pmuludq mm1,mm2
64. paddq mm0, mm1
65. paddq mm0, mm3
66. movd [ebp+eax*4],mm0
67. psrlq mm0, 32 //carry
68. inc eax
69. innerLoopCmp:
70. jnz innerLoop
71. movd [ebp+eax*4],mm0
72. inc ecx
73. outLoopCmp:
74. cmp ecx,dword ptr [esp + 20+STACK_BASE] //rightLen
75. jb outLoop
77. thisExit:
79. pop ebp
80. pop edi
81. pop esi
83. emms
84. ret
85. }
86. }

复制代码

无心人

不起作用的原因是现代CPU乃乱序执行的

liangbch

我有2台电脑，PIV 和 PM，我在优化程序的时候总是要在2台电脑上测试。某些优化手段在一台电脑上效果很明显，但在另外型号的电脑上可能不明显。现在总结一下这2台电脑的差异。 PM ADC指令相对较慢，减少ADC指令，提速效果明显，而PIV 则不明显。 PM 内存子系统相对较慢，减少内存写提速效果明显，而PIV 则不明显。 PM 指令并行执行的较差，减少指令条数提速效果明显，而PIV 则不明显。 PIV SSE2 指令中访问 128bit寄存器的指令速度很快，而PM则非常慢，用128bit寄存器优化大数乘法，速度不升反降。

无心人

PM类似现在Core核心 但属于Core一代 PM的SSE2执行单元少 且其他执行单元少 但解码单元多