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

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 编程擂台 › x86上128位二进制乘法最快速算法征解
1 ...234567891011... 15下一页
返回列表 发新帖
楼主: 无心人

[擂台] x86上128位二进制乘法最快速算法征解

[复制链接]
liangbch
发表于 2008-3-24 12:22:34 | 显示全部楼层
在PIV上运行， UInt128x128To256_SSE2_58F 依然是最快的版本，下面是在PIV 2.6G上运行附件程序的测试结果。 Test function: UInt128x128To256_ANSI_C32(..) 10000000 times... Elapsed time: 1922.926 ms 61E4210A 30360E4B 277E205E 76686B79 * B17E7E8A 5DAC7050 2D821227 A31462E1 = 43DF1983 7F67BDEE F4F9FCCA FF5AE6BD 6ACA3B72 D0384E14 E4ED3A5F 7B5EC759 Test function: UInt128x128To256_SSE2_40F(..) 10000000 times... Elapsed time: 963.448 ms 61E4210A 30360E4B 277E205E 76686B79 * B17E7E8A 5DAC7050 2D821227 A31462E1 = 43DF1983 7F67BDEE F4F9FCCA FF5AE6BD 6ACA3B72 D0384E14 E4ED3A5F 7B5EC759 Test function: UInt128x128To256_SSE2_42F(..) 10000000 times... Elapsed time: 723.966 ms 61E4210A 30360E4B 277E205E 76686B79 * B17E7E8A 5DAC7050 2D821227 A31462E1 = 43DF1983 7F67BDEE F4F9FCCA FF5AE6BD 6ACA3B72 D0384E14 E4ED3A5F 7B5EC759 Test function: UInt128x128To256_SSE2_54F(..) 10000000 times... Elapsed time: 688.926 ms 61E4210A 30360E4B 277E205E 76686B79 * B17E7E8A 5DAC7050 2D821227 A31462E1 = 43DF1983 7F67BDEE F4F9FCCA FF5AE6BD 6ACA3B72 D0384E14 E4ED3A5F 7B5EC759 Test function: UInt128x128To256_SSE2_56F(..) 10000000 times... Elapsed time: 578.551 ms 61E4210A 30360E4B 277E205E 76686B79 * B17E7E8A 5DAC7050 2D821227 A31462E1 = 43DF1983 7F67BDEE F4F9FCCA FF5AE6BD 6ACA3B72 D0384E14 E4ED3A5F 7B5EC759 Test function: UInt128x128To256_SSE2_58F(..) 10000000 times... Elapsed time: 496.951 ms 61E4210A 30360E4B 277E205E 76686B79 * B17E7E8A 5DAC7050 2D821227 A31462E1 = 43DF1983 7F67BDEE F4F9FCCA FF5AE6BD 6ACA3B72 D0384E14 E4ED3A5F 7B5EC759
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
发表于 2008-3-24 12:47:36 | 显示全部楼层
谢谢楼上的测试！ 看来不同机器对指令的处理周期相差很大， 也许在 Core2 上，56F 反超 58F 也是可能的。。。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2008-3-24 13:28:34 | 显示全部楼层
你的P4是31流水线的P4E 俺的是P4 郭的是Althon 差Core 2版 ：）
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2008-3-24 13:33:30 | 显示全部楼层
事情复杂了 我执行GxQcn程序也得到liangbch的结果 但我测试却不是 现在 问题在什么地方？ ICC编译器难道对汇编也动？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2008-3-24 13:46:12 | 显示全部楼层
GxQcn你能不能把存储临时值操作取消掉 那个高延时啊
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
发表于 2008-3-24 13:57:49 | 显示全部楼层
Re: 64# 反正有完整的测试源代码，你不妨将不同编译器编译的程序运行一下，并把结果公布出来，让大家分析分析。。。 Re: 65# 我也不想啊，寄存器那么少，这是权衡之后的下下策啊。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2008-3-24 14:22:17 | 显示全部楼层
疯了疯了 在我VC2008Express上重新编译你代码 结果和你程序一致 也是依次减小 为什么啊
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2008-3-24 16:51:38 | 显示全部楼层
这么做有优势么？ 先乘四个3:3 2:2 1:1 0:0 正好存在结果里 然后依次乘剩下的12个 加在结果上
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
发表于 2008-3-24 19:02:21 | 显示全部楼层

对 58# 再改进

对 58F 再进行指令混排（寄存器名局部有轮换），得到新的版本如下：
  1. _declspec(naked)
  2. void UInt128x128To256_SSE2_69F( UINT32 * const result,
  3. const UINT32 * const left,
  4. const UINT32 * const right )
  5. {
  6. __asm
  7. {
  8. mov ecx, dword ptr[esp + 04h] ; result
  9. mov eax, dword ptr[esp + 08h] ; left
  10. mov edx, dword ptr[esp + 0Ch] ; right
  12. movdqa xmm5, xmmword ptr[eax] ; load left
  13. movdqa xmm4, xmmword ptr[edx] ; load right
  15. mov eax, esp ;
  16. sub esp, 0x4F ;
  17. and esp, -16 ;
  19. pshufd xmm0, xmm5, 00000000b ; xmm0 = L0:L0:L0:L0
  20. pshufd xmm1, xmm5, 01010101b ; xmm1 = L1:L1:L1:L1
  21. pshufd xmm2, xmm5, 10101010b ; xmm2 = L2:L2:L2:L2
  22. pshufd xmm3, xmm5, 11111111b ; xmm3 = L3:L3:L3:L3
  24. movdqa xmmword ptr[ecx+0x00], xmm0 ; xmm0 = L0:L0:L0:L0
  25. movdqa xmmword ptr[ecx+0x10], xmm1 ; xmm1 = L1:L1:L1:L1
  26. movdqa xmm6, xmm2 ; xmm6 = L2:L2:L2:L2
  27. movdqa xmm7, xmm3 ; xmm7 = L3:L3:L3:L3
  29. pmuludq xmm0, xmm4 ; xmm0 = L0*R2:L0*R0
  30. pmuludq xmm1, xmm4 ; xmm1 = L1*R2:L1*R0
  31. pmuludq xmm2, xmm4 ; xmm2 = L2*R2:L2*R0
  32. pmuludq xmm3, xmm4 ; xmm3 = L3*R2:L3*R0
  34. movdqa xmmword ptr[esp+0x00], xmm0 ;
  35. movdqa xmmword ptr[esp+0x10], xmm1 ;
  36. movdqa xmmword ptr[esp+0x20], xmm2 ;
  37. movdqa xmmword ptr[esp+0x30], xmm3 ;
  39. psrldq xmm4, 4 ; xmm4 = 00:R3:R2:R1
  40. movdqa xmm1, xmmword ptr[ecx+0x10] ; xmm1 = L1:L1:L1:L1
  41. movdqa xmm0, xmmword ptr[ecx+0x00] ; xmm0 = L0:L0:L0:L0
  43. pmuludq xmm7, xmm4 ; xmm3 = L3*R3:L3*R1 ->V7-4
  44. pmuludq xmm6, xmm4 ; xmm2 = L2*R3:L2*R1 ->V6-3
  45. pmuludq xmm1, xmm4 ; xmm1 = L1*R3:L1*R1
  46. pmuludq xmm0, xmm4 ; xmm0 = L0*R3:L0*R1
  49. movdqa xmm5, xmm7 ;
  50. movdqa xmm4, xmm6 ;
  51. movdqa xmm3, xmm6 ;
  53. pslldq xmm5, 4 ; xmm5 <<= 32
  54. psrldq xmm4, 4 ; xmm4 >>= 32
  55. pslldq xmm3, 12 ; L3*R3:L3*R1 ->V3-0
  57. paddq xmm7, xmm4 ; L2*R3:L2*R1 ->V7-4
  58. paddq xmm6, xmm5 ; L3*R3:L3*R1 ->V6-3
  61. movdqa xmm2, xmm0 ;
  62. movdqa xmm4, xmm0 ;
  63. movdqa xmm5, xmm1 ;
  65. psrldq xmm0, 8 ; xmm0 >>= 64
  66. psrldq xmm1, 4 ; xmm1 >>= 32
  67. pslldq xmm2, 8 ; L0*R3:L0*R1 ->V2-1H
  68. pslldq xmm4, 4 ; xmm4 <<= 32
  69. pslldq xmm5, 8 ; xmm5 <<= 64
  71. paddq xmm6, xmm0 ; L0*R3:L0*R1 ->V6-3
  72. paddq xmm3, xmm4 ; L0*R3:L0*R1 ->V3-0
  73. paddq xmm6, xmm1 ; L1*R3:L1*R1 ->V6-3
  74. paddq xmm3, xmm5 ; L1*R3:L1*R1 ->V3-0
  76. psrldq xmm0, 4 ; xmm0 >>= 32
  77. psrldq xmm1, 4 ; xmm1 >>= 32
  78. pslldq xmm5, 4 ; xmm5 <<= 32
  80. paddq xmm7, xmm0 ; L0*R3:L0*R1 ->V7-4
  81. paddq xmm2, xmm5 ; L1*R3:L1*R1 ->V2-1H
  82. paddq xmm7, xmm1 ; L1*R3:L1*R1 ->V7-4
  85. movdqa xmm5, xmmword ptr[esp+0x30] ; xmm5 = L3*R2:L3*R0
  86. movdqa xmm4, xmmword ptr[esp+0x20] ; xmm4 = L2*R2:L2*R0
  88. movdqa xmm1, xmm5 ;
  89. movdqa xmm0, xmm4 ;
  90. paddq xmm6, xmm5 ; L3*R2:L3*R0 ->V6-3
  92. psrldq xmm0, 4 ; xmm0 >>= 32
  93. psrldq xmm1, 4 ; xmm1 >>= 32
  94. pslldq xmm4, 8 ; xmm4 <<= 64
  95. pslldq xmm5, 12 ; xmm5 <<= 96
  97. paddq xmm6, xmm0 ; L2*R2:L2*R0 ->V6-3
  98. paddq xmm3, xmm4 ; L2*R2:L2*R0 ->V3-0
  99. paddq xmm7, xmm1 ; L3*R2:L3*R0 ->V7-4
  100. paddq xmm3, xmm5 ; L3*R2:L3*R0 ->V3-0
  102. psrldq xmm0, 4 ; xmm0 >>= 32
  103. pslldq xmm4, 4 ; xmm4 <<= 32
  105. movdqa xmm1, xmmword ptr[esp+0x00] ; xmm1 = L0*R2:L0*R0
  106. movdqa xmm5, xmmword ptr[esp+0x10] ; xmm5 = L1*R2:L1*R0
  108. paddq xmm7, xmm0 ; L2*R2:L2*R0 ->V7-4
  109. paddq xmm2, xmm4 ; L2*R2:L2*R0 ->V2-1H
  110. paddq xmm3, xmm1 ; L0*R2:L0*R0 ->V3-0
  112. movdqa xmm0, xmm1 ;
  113. movdqa xmm4, xmm5 ;
  115. pslldq xmm1, 4 ; xmm1 <<= 32
  116. pslldq xmm5, 4 ; xmm5 <<= 32
  117. psrldq xmm0, 12 ; xmm0 >>= 96
  118. psrldq xmm4, 8 ; xmm4 >>= 64
  120. paddq xmm2, xmm1 ; L0*R2:L0*R0 ->V2-1H
  121. paddq xmm6, xmm0 ; L0*R2:L0*R0 ->V6-3
  122. paddq xmm3, xmm5 ; L1*R2:L1*R0 ->V3-0
  123. paddq xmm6, xmm4 ; L1*R2:L1*R0 ->V6-3
  125. pslldq xmm5, 4 ; xmm5 <<= 32
  126. psrldq xmm4, 4 ; xmm4 >>= 32
  128. paddq xmm2, xmm5 ; L1*R2:L1*R0 ->V2-1H
  129. paddq xmm7, xmm4 ; L1*R2:L1*R0 ->V7-4
  132. mov esp, eax ; now, V[1:0]=xmm3[63:0] ->OK
  134. psrldq xmm2, 4 ; xmm2 >>= 32
  135. movdqa xmm4, xmm3 ;
  136. pcmpeqd xmm0, xmm0 ; xmm0 = FF:FF:FF:FF
  137. pandn xmm4, xmm2 ;
  138. psubd xmm2, xmm3 ; xmm2 -= xmm3
  139. psrldq xmm0, 12 ; xmm0 = 00:00:00:FF
  141. pslldq xmm4, 4 ; xmm4 <<= 32
  142. psrld xmm4, 31 ; CF
  143. pshufd xmm1, xmm0, 01001110b ; xmm1 = 00:FF:00:00
  144. paddd xmm2, xmm4 ;
  145. pand xmm2, xmm1 ;
  146. paddq xmm3, xmm2 ; V[3:0]=xmm3 ->OK
  147. movdqa xmmword ptr[ecx+0x00], xmm3 ; store V[3:0]
  150. psrldq xmm3, 12 ; xmm3 >>= 96
  151. psubd xmm3, xmm6 ; xmm3 -= xmm6
  152. pand xmm3, xmm0 ;
  153. paddq xmm6, xmm3 ; V[4:3]=xmm6[63:0] ->OK
  154. pxor xmm1, xmm0 ; xmm1 = 00:FF:00:FF
  155. psrldq xmm6, 4 ; V[4]=xmm6[31:0] ->OK
  158. movdqa xmm2, xmm6 ; xmm2 = xmm6
  159. psubd xmm6, xmm7 ; xmm6 -= xmm0
  160. pand xmm6, xmm1 ;
  161. paddq xmm7, xmm6 ; now, xmm7[63-0] bits OK!
  163. psubusb xmm2, xmm7 ;
  164. psrlq xmm2, 63 ; CF
  165. pslldq xmm2, 8 ;
  166. paddq xmm7, xmm2 ; xmm7[127-64] += CF
  167. movdqa xmmword ptr[ecx+0x10], xmm7 ; store V[7:4]
  169. ret;
  170. }
  171. }
复制代码
当前所有版本测试源代码及编译好的程序压缩包： UInt128x128To256.zip (32.21 KB, 下载次数: 15)
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2008-3-25 21:50:30 | 显示全部楼层
总感觉你这么安排指令会存在冲突
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-11-21 20:32 , Processed in 0.033321 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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