数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 算法交流 › B计划之长加法最佳算法讨论
123456下一页
返回列表 发新帖
楼主: 无心人

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

[复制链接]
无心人
 楼主| 发表于 2008-4-16 17:10:58 | 显示全部楼层
哦

知道了
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

liangbch
发表于 2008-5-4 15:40:57 | 显示全部楼层
增加了2个版本，先给出在PIV 2.6上的测试结果

说明：
   binAdd_base30_ALU_4way_unroll2 为 binAdd_base30_ALU_4way_unroll的改进版，指令数更少，速度更快些。
     binAdd_base30_ALU_8way_unroll2 为 binAdd_base30_ALU_8way_unroll的改进版，指令数更少，速度更快些，但基本与binAdd_base30_ALU_4way_unroll2 持平。




Test function: binAdd_ALU(..) 100000 times...
Elapsed time: 1904.675 ms

Test function: binAdd_GMP_ALU_8way_unroll(..) 100000 times...
Elapsed time: 1357.660 ms

Test function: binAdd_Yaos_MMX_4way_unroll(..) 100000 times...
Elapsed time: 772.390 ms

Test function: binAdd_base30_ALU(..) 100000 times...
Elapsed time: 1203.820 ms

Test function: binAdd_base30_ALU_4way_unroll(..) 100000 times...
Elapsed time: 1225.580 ms

Test function: binAdd_base30_ALU_4way_unroll2(..) 100000 times...
Elapsed time: 1190.035 ms

Test function: binAdd_base30_ALU_8way_unroll(..) 100000 times...
Elapsed time: 1213.810 ms

Test function: binAdd_base30_ALU_8way_unroll2(..) 100000 times...
Elapsed time: 1189.320 ms

Test function: binAdd_Base30_MMX_4way_unroll(..) 100000 times...
Elapsed time: 903.745 ms

再给出测试代码：
//基为2^30的版本另一个版本，采用4路循环展开
  1. _declspec(naked)
  2. DWORD binAdd_base30_ALU_4way_unroll2(DWORD *dst,
  3. const DWORD *src1,
  4. const DWORD *src2,
  5. int   size)
  6. {
  7. #undef  BASE30_MASK
  8. #define BASE30_MASK 0x3fffffff
  9. _asm
  10. {
  11. push edi
  12. push esi
  13. push ebx
  14. sub  esp,4

  16. mov ebx,[esp+16+PARAM_DST]
  17. mov esi,[esp+16+PARAM_SRC1]
  18. mov edi,[esp+16+PARAM_SRC2]
  19. mov edx,[esp+16+PARAM_SIZE]

  21. lea eax,[esi+edx*4]
  22. mov [esp],eax

  24. xor ecx,ecx //clear carry
  25. and edx,3
  26. jz  a10

  28. loop00:
  29. add ecx,[esi]
  30. add ecx,[edi]
  31. mov ecx,eax
  32. and eax,BASE30_MASK
  33. shr ecx,30
  34. mov [ebx],eax
  35. lea esi,[esi+4]
  36. lea edi,[edi+4]
  37. lea ebx,[ebx+4]
  38. dec edx
  39. jnz loop00
  40. a10:
  41. jmp cmp00

  43. ALIGN 8
  44. loop01:
  45. add ecx, [esi]
  46. add ecx, [edi]
  47. mov eax, ecx
  48. and eax,BASE30_MASK
  49. shr ecx,30
  50. mov [ebx],eax

  52. add ecx, [esi+4]
  53. add ecx, [edi+4]
  54. mov edx, ecx
  55. and edx,BASE30_MASK
  56. shr ecx,30
  57. mov [ebx+4],edx


  60. add ecx, [esi+8]
  61. add ecx, [edi+8]
  62. mov eax, ecx
  63. and eax,BASE30_MASK
  64. shr ecx,30
  65. mov [ebx+8],eax


  68. add ecx, [esi+12]
  69. add ecx, [edi+12]
  70. mov edx, ecx
  71. and edx,BASE30_MASK
  72. shr ecx,30
  73. mov [ebx+12],edx


  76. lea esi,[esi+16]
  77. lea edi,[edi+16]
  78. lea ebx,[ebx+16]
  79. cmp00:
  80. cmp esi,[esp]
  81. jb loop01

  83. thisExit:
  84. add esp,4

  86. pop ebx
  87. pop esi
  88. pop edi
  89. mov eax,0
  90. adc eax,0
  91. ret
  92. }
  93. }
复制代码
//基为2^30的版本另一个版本，指令数更少，采用8路循环展开
  1. _declspec(naked)
  2. DWORD binAdd_base30_ALU_8way_unroll2(DWORD *dst,
  3. const DWORD *src1,
  4. const DWORD *src2,
  5. int   size)
  6. {
  7. #undef  BASE30_MASK
  8. #define BASE30_MASK 0x3fffffff
  9. _asm
  10. {
  11. push edi
  12. push esi
  13. push ebx
  14. sub  esp,4

  16. mov ebx,[esp+16+PARAM_DST]
  17. mov esi,[esp+16+PARAM_SRC1]
  18. mov edi,[esp+16+PARAM_SRC2]
  19. mov edx,[esp+16+PARAM_SIZE]

  21. lea eax,[esi+edx*4]
  22. mov [esp],eax

  24. xor ecx,ecx
  25. and edx,7
  26. jz  a10

  28. loop00:
  29. add ecx,[esi]
  30. add ecx,[edi]
  31. mov eax,ecx
  32. and eax,BASE30_MASK
  33. shr ecx,30
  34. mov [ebx],eax
  35. lea esi,[esi+4]
  36. lea edi,[edi+4]
  37. lea ebx,[ebx+4]
  38. dec edx
  39. jnz loop00
  40. a10:
  41. jmp cmp00

  43. ALIGN 8
  44. loop01:
  45. add ecx,[esi]
  46. add ecx,[edi]
  47. mov eax,ecx
  48. and eax,BASE30_MASK
  49. shr ecx,30
  50. mov [ebx],eax


  53. add ecx,[esi+4]
  54. add ecx,[edi+4]
  55. mov edx,ecx
  56. and edx,BASE30_MASK
  57. shr ecx,30
  58. mov [ebx+4],edx


  61. add ecx,[esi+8]
  62. add ecx,[edi+8]
  63. mov eax,ecx
  64. and eax,BASE30_MASK
  65. shr ecx,30
  66. mov [ebx+8],eax


  69. add ecx,[esi+12]
  70. add ecx,[edi+12]
  71. mov edx,ecx
  72. and edx,BASE30_MASK
  73. shr ecx,30
  74. mov [ebx+12],edx


  77. add ecx,[esi+16]
  78. add ecx,[edi+16]
  79. mov eax,ecx
  80. and eax,BASE30_MASK
  81. shr ecx,30
  82. mov [ebx+16],eax


  85. add ecx,[esi+20]
  86. add ecx,[edi+20]
  87. mov edx,ecx
  88. and edx,BASE30_MASK
  89. shr ecx,30
  90. mov [ebx+20],edx


  93. add ecx,[esi+24]
  94. add ecx,[edi+24]
  95. mov eax,ecx
  96. and eax,BASE30_MASK
  97. shr ecx,30
  98. mov [ebx+24],eax


  101. add ecx,[esi+28]
  102. add ecx,[edi+28]
  103. mov edx,ecx
  104. and edx,BASE30_MASK
  105. shr ecx,30
  106. mov [ebx+28],edx


  109. lea esi,[esi+32]
  110. lea edi,[edi+32]
  111. lea ebx,[ebx+32]
  112. cmp00:
  113. cmp esi,[esp]
  114. jb loop01

  116. thisExit:
  117. add esp,4
  118. pop ebx
  119. pop esi
  120. pop edi
  121. mov eax,0
  122. adc eax,0
  123. ret
  124. }
  125. }
复制代码


毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2008-5-8 16:56:16 | 显示全部楼层


刚把加法的SSE2加4路展开给通用化了
并顺便实现了8路展开

1024双字加，重复100万次
4路SSE2加: 2547.029
8路SSE2加: 2456.956

8路的仅提高3.5%时间
所以4路的为最佳形式了

附四路八路通用加法代码

DWORD longAdd4p(DWORD result[], DWORD left[], DWORD right[], DWORD len)
{
    __asm
  {
  mov esi, [left]
  mov edi, [right]
  mov ebx, [result]
  mov ecx, [len]
  mov edx, ecx
  pxor mm0, mm0
  shr ecx, 2
  je  loop20
  loop1:
  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 mm3, [edi+12]
  paddq mm7, mm3
  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 loop1
loop20:
  mov ecx, edx
  and ecx, 3
  jz exit1
loop2:
  movd mm1, [esi]
  movd mm2, [edi]
  paddq mm0, mm1
  paddq mm0, mm2
  movd [ebx], mm0
  psrlq mm0, 32
  add esi, 4
  add edi, 4
  add ebx, 4
  sub ecx, 1
  jne loop2
exit1:
  movd eax, mm0
  emms
  }
}

DWORD longAdd8p(DWORD result[], DWORD left[], DWORD right[], DWORD len)
{
    __asm
  {
  mov esi, [left]
  mov edi, [right]
  mov ebx, [result]
  mov ecx, [len]
  mov edx, ecx
  pxor mm0, mm0
  shr ecx, 3
  je  loop20
  loop1:
  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 mm3, [edi+12]
  paddq mm7, mm3
  movd mm2, [esi+16]
  movd mm4, [edi+16]
  paddq mm2, mm4
  paddq mm0, mm1
  movd [ebx], mm0
  psrlq mm0, 32
  movd mm6, [esi+20]
  movd mm1, [edi+20]
  paddq mm6, mm1
  paddq mm0, mm3
  movd [ebx+4], mm0
  psrlq mm0, 32
  paddq mm0, mm5
  movd [ebx+8], mm0
  psrlq mm0, 32
  movd mm4, [esi+24]
  movd mm5, [edi+24]
  paddq mm4, mm5
  paddq mm0, mm7
  movd [ebx+12], mm0
  psrlq mm0, 32
  movd mm1, [esi+28]
  movd mm3, [edi+28]
  paddq mm1, mm3
  paddq mm0, mm2
  movd [ebx+16], mm0
  psrlq mm0, 32
  paddq mm0, mm6
  movd [ebx+20], mm0
  psrlq mm0, 32
  paddq mm0, mm4
  movd [ebx+24], mm0
  psrlq mm0, 32
  paddq mm0, mm1
  movd [ebx+28], mm0
  psrlq mm0, 32
  add esi, 32
  add edi, 32
  add ebx, 32
  sub ecx, 1
  jne loop1
loop20:
  mov ecx, edx
  and ecx, 7
  jz exit1
loop2:
  movd mm1, [esi]
  movd mm2, [edi]
  paddq mm0, mm1
  paddq mm0, mm2
  movd [ebx], mm0
  psrlq mm0, 32
  add esi, 4
  add edi, 4
  add ebx, 4
  sub ecx, 1
  jne loop2
exit1:
  movd eax, mm0
  emms
  }
}
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

liangbch
发表于 2008-5-8 17:08:55 | 显示全部楼层
原帖由 liangbch 于 2008-4-8 18:05 发表
对于编写高性能的程序，常常需要权衡程序效率和复杂度之间的平衡。1路->4路，性能提高明显， 4路 -〉8路 则性能提高的就很有限了。从GMP的源代码可以看出，他使用的循环展开一般为4-6路。个人觉得4路循环展开应该是一 ...


看来我在16#的断言没有错。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2008-5-8 17:30:44 | 显示全部楼层
如果实现求圆周率程序
8路展开也许还有用处的
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

liangbch
发表于 2008-5-9 10:45:16 | 显示全部楼层
8路循环展开也不是没有用武之地，对于循环体内代码很少的情况下，8路循环展开还是有优势的，如内存清0，内存复制。memcpy 源代码就使用了8路循环展开。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2008-5-9 10:55:52 | 显示全部楼层


那可以考虑和16路展开比较
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

liangbch
发表于 2008-5-9 11:50:49 | 显示全部楼层
可以预计16路循环展开对性能的提升极为有限。

哈哈，我还是想说一句，我的原则是有所为，有所不为，为了1%的性能提高，而花费%20的时间和精力，我一般不会去做。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2008-5-9 14:36:58 | 显示全部楼层
我做4路加法消耗20-30分钟
4路改8路仅修改了10分钟

所以如果你改16路不划算
证明你代码存在难修改的问题
结构化不好

毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

liangbch
发表于 2008-5-9 15:48:20 | 显示全部楼层
哈哈，上面只是一个比方，我也不知道改一个函数需要耗费多少成本。
  不过8路改16路应该很简单，逻辑上应该没有多大变化，但相应的也需要写一堆测试代码。
8路改为16路，提速效果应该不大，我不想尝试了。我下一步想要做的是，实现$2^30$的basecase乘法。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

123456下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-5-3 12:59 , Processed in 0.042939 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表