找回密码
 欢迎注册
楼主: 无心人

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

[复制链接]
 楼主| 发表于 2008-3-6 15:06:30 | 显示全部楼层
重新翻你们的96Bit帖
原来有个PSHFUD啊


不过通篇不提MMX寄存器
实际上
MMX的32位乘快于SSE
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-6 15:28:27 | 显示全部楼层
可设计五个方案
1、MM积存器操作的
2、XMM寄存器操作的
3、混合寄存器操作的
4、2加双乘的
5、3加双乘的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-6 16:40:41 | 显示全部楼层
谁有最新的指令的周期数据
晚于P4即可
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-6 16:56:02 | 显示全部楼层

回复 33# 的帖子

见我在 http://bbs.emath.ac.cn/viewthrea ... mp;fromuid=8#pid885 发的链接,
那个 2.47MB 的压缩包就有你需要的东西(Instruction tables),它也曾对我有很大的帮助。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-6 17:23:08 | 显示全部楼层
MMX刚写好, 120条, 似乎有点编译问题
(作废!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!)
                mov esi, left
                mov edi, right
                mov ebx, result
        movd mm0, [esi]
                pmuludq mm0, [edi]
                movd [ebx], mm0
                pshrq mm0, 32
                movd mm1, [esi]
                pmuludq mm1, [edi+4]
                movd mm2, [edi]
                pmuludq mm2, [esi+4]
//mm0+mm1+mm2
                paddq mm0, mm1
                movd mm1, mm0
                pshrq mm0, 32
                movd mm3, mm2
                pshrq mm2, 32
                paddq mm1, mm3
                paddq mm0, mm2
                movd [ebx+4], mm1
                pshrq mm1, 32
                paddq mm0, mm1
                movd mm1, [esi+4]
                pmuludq mm1, [edi+4]
                movd mm2, [esi]
                pmuludq mm2, [edi+8]
                movd mm3, [edi]
                pmuludq mm3, [esi+8]
//mm0+mm1+mm2+mm3
                movd mm6, mm0
                pshrq mm0, 32
                movd mm7, mm1
                pshrq mm1, 32
                paddq mm6, mm7
                movd mm7, mm2
                pshrq mm2, 32
                paddq mm6, mm7
                movd mm7, mm3
                pshrq mm3, 32
                paddq mm6, mm7
                paddq mm0, mm1
                paddq mm0, mm2
                paddq mm0, mm3
                movd [ebx+8], mm6
                pshrq mm6, 32
                paddq mm0, mm6
                movd mm1, [esi]
                pmuludq mm1, [edi+12]
                movd mm2, [esi+4]
                pmuludq mm2, [edi+8]
                movd mm3, [esi+8]
        pmuludq mm3, [edi+4]
                movd mm4, [esi+12]
                pmuludq mm4, [edi]
//mm0+mm1+mm2+mm3+mm4
                movd mm5, mm1
                paddq mm0, mm5
                pshrq mm1, 32
                movd mm6, mm2
                paddq mm0, mm6
                pshrq mm2, 32
                movd mm7, mm3
                paddq mm0, mm7
                pshrq mm3, 32
                movd mm5, mm4
                paddq mm0, mm5
                psrq mm4, 32
                paddq mm1, mm2
                movd [ebx+12], mm0
                paddq mm1, mm3
                psrq mm0, 32
                paddq mm1, mm4
                paddq mm0, mm1
                movd mm2, [esi+4]
                pmuludq mm2, [edi+12]
                movd mm1, [esi+8]
                pmuludq mm1, [edi+8]
                movd mm3, [esi+12]
                pmuludq mm3, [edi+4]
//mm0+mm1+mm2+mm3
                movd mm6, mm0
                pshrq mm0, 32
                movd mm7, mm1
                pshrq mm1, 32
                paddq mm6, mm7
                movd mm7, mm2
                pshrq mm2, 32
                paddq mm6, mm7
                movd mm7, mm3
                pshrq mm3, 32
                paddq mm6, mm7
                paddq mm0, mm1
                paddq mm0, mm2
                paddq mm0, mm3
                movd [ebx+16], mm6
                pshrq mm6, 32
                paddq mm0, mm6
                mov mm1, [esi+8]
                pmuludq mm1, [edi+12]
                mov mm2, [esi+12]
                pmuludq, [edi+8]
//mm0+mm1+mm2
                paddq mm0, mm1
                movd mm1, mm0
                pshrq mm0, 32
                movd mm3, mm2
                pshrq mm2, 32
                paddq mm1, mm3
                paddq mm0, mm2
                movd [ebx+20], mm1
                pshrq mm1, 32
                paddq mm0, mm1
                mov mm1, [esi+12]
                pmuludq, [edi+12]
//mm0+mm1
        movd mm6, mm0
                pshrq mm0, 32
                movd mm7, mm0
                pshrq mm1, 32
                paddq mm6, mm7
                movd [ebx+24], mm6
                pshrq mm6, 32
                paddq mm0, mm1
                paddq mm0, mm6
                movd [ebx+28], mm0
                emms
                ret;
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-6 17:25:14 | 显示全部楼层
版本太老
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-6 20:18:09 | 显示全部楼层
指令PSHUFW类似PSHUFD, 但针对mmx

又仔细搜索了文档, 还是找不到解四字或者双字组的方法
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-7 07:47:53 | 显示全部楼层
找到解决解开包装的方法
共4条相关的
分别能解开高低64位, 高低32位到低位

如果解一个双乘128位结果
需14条指令
涉及除XMM结果寄存器外, 2个XMM, 4个MMX寄存器
故指令条数应>(14 + 3(乘法)) * 8 + 8(保守估计加需要, 肯定更多) * 8 > 200条
=======================================
上面作废的MMX代码
修改下, 估计在140条内能解决

如果估计没错误, MMX乘是3个周期, SSE2双乘是5个, 此乃流水线周期
========================================
谁有更好方案?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-18 09:58:25 | 显示全部楼层
MMX寄存器使用SSE2指令的写出来了
但存在点错误在调试

初步测试时间是C写法的1/3
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-18 11:16:32 | 显示全部楼层
第一个可用代码,此问题MMX指令完全不可用
void UInt128x128To256_SSE2_40F( UINT32 * const result,
          const UINT32 * const left,
          const UINT32 * const right )
{
//使用MMX寄存器, 但用SSE2指令
__asm
{
  mov esi, left
  mov edi, right
  mov ebx, result
//0:0
        movd mm0, [esi]
  pmuludq mm0, [edi]
  movd [ebx], mm0
  psrlq mm0, 32
// 0:1 1:0
  movd mm1, [esi]
  pmuludq mm1, [edi+4]
  movd mm2, [edi]
  pmuludq mm2, [esi+4]
  mov eax, -1
//mm0+mm1+mm2
  paddq mm0, mm1//mm0=mm0+mm1 mm0肯定小于 2^64
  movd mm1, eax
  pand mm1, mm0
  psrlq mm0, 32 //分解mm0 = mm0:mm1
  movd mm3, eax
  pand mm3, mm2
  psrlq mm2, 32 //分解mm2=mm2:mm3
  paddq mm1, mm3 //mm1=mm1+mm3
  paddq mm0, mm2 //mm0=mm0+mm2
  movd [ebx+4], mm1 //mm1低位存储
  psrlq mm1, 32 //mm1高位
  paddq mm0, mm1 //得到进位
//1:1 0:2 2:0
  movd mm1, [esi+4]
  pmuludq mm1, [edi+4]
  movd mm2, [esi]
  pmuludq mm2, [edi+8]
  movd mm3, [edi]
  pmuludq mm3, [esi+8]
//mm0+mm1+mm2+mm3
  movd mm6, eax
  pand mm6, mm0
  psrlq mm0, 32 //分解mm0=mm0:mm6
  movd mm5, eax
  pand mm5, mm1
  psrlq mm1, 32 //分解mm1=mm1:mm5
  paddq mm6, mm5 //mm6=mm6+mm5
  paddq mm0, mm1 //mm0=mm0+mm1
  movd mm4, eax
  pand mm4, mm2
  psrlq mm2, 32 //分解mm2=mm2:mm4
  paddq mm6, mm4 //mm6=mm6+mm4
  paddq mm0, mm2 //mm0=mm0+mm2
  movd mm7, eax
  pand mm7, mm3
  psrlq mm3, 32 //分解mm3=mm3:mm7
  paddq mm6, mm7 //mm6=mm6+mm7
  paddq mm0, mm3 //mm0=mm0+mm3
  movd [ebx+8], mm6 //mm6低位存储
  psrlq mm6, 32  
  paddq mm0, mm6 //得到进位
//0:3 1:2 2:1 3:0
  movd mm1, [esi]
  pmuludq mm1, [edi+12]
  movd mm2, [esi+4]
  pmuludq mm2, [edi+8]
  movd mm3, [esi+8]
        pmuludq mm3, [edi+4]
  movd mm4, [esi+12]
  pmuludq mm4, [edi]
//mm0+mm1+mm2+mm3+mm4
  movd mm5, eax
  pand mm5, mm1
  psrlq mm1, 32 //分解mm1=mm1:mm5
  paddq mm0, mm5 //mm0=mm0+mm5
  movd mm6, eax
  pand mm6, mm2
  psrlq mm2, 32 //分解mm2=mm2:mm6
  paddq mm0, mm6 //mm0=mm0+mm6
  paddq mm1, mm2 //mm1=mm1+mm2
  movd mm7, eax
  pand mm7, mm3
  psrlq mm3, 32 //分解mm3=mm3:mm7
  paddq mm0, mm7 //mm0=mm0+mm7
  paddq mm1, mm3 //mm1=mm1+mm3
  movd mm5, eax
  pand mm5, mm4
  psrlq mm4, 32 //分解mm4=mm4:mm5
  paddq mm0, mm5 //mm0=mm0+mm5
  paddq mm1, mm4 //mm1=mm1+mm4
  movd [ebx+12], mm0 //mm0低位存储
  psrlq mm0, 32
  paddq mm0, mm1 //新进位
//1:3 2:2 3:1
  movd mm2, [esi+4]
  pmuludq mm2, [edi+12]
  movd mm1, [esi+8]
  pmuludq mm1, [edi+8]
  movd mm3, [esi+12]
  pmuludq mm3, [edi+4]
//mm0+mm1+mm2+mm3
  movd mm7, eax
  pand mm7, mm0
  psrlq mm0, 32 //分解mm0=mm0:mm7
  movd mm6, eax
  pand mm6, mm1
  psrlq mm1, 32 //分解mm1=mm1:mm6
  paddq mm7, mm6 //mm7=mm7+mm6
  paddq mm0, mm1 //mm0=mm0+mm1
  movd mm5, eax
  pand mm5, mm2
  psrlq mm2, 32 //分解mm2=mm2:mm5
  paddq mm7, mm5 //mm7=mm7+mm5
  paddq mm0, mm2 //mm0=mm0+mm2
  movd mm4, eax
  pand mm4, mm3
  psrlq mm3, 32 //分解mm3=mm3:mm4
  paddq mm7, mm4 //mm7=mm7+mm4
  paddq mm0, mm3 //mm0=mm0+mm3
  movd [ebx+16], mm7 //mm7低位存储
  psrlq mm7, 32
  paddq mm0, mm7 //得到进位
//2:3 3:2
  movd mm1, [esi+8]
  pmuludq mm1, [edi+12]
  movd mm2, [esi+12]
  pmuludq mm2, [edi+8]
//mm0+mm1+mm2
  movd mm7, eax
  pand mm7, mm0
  psrlq mm0, 32 //分解mm0=mm0:mm7
  movd mm6, eax
  pand mm6, mm1
  psrlq mm1, 32 //分解mm1=mm1:mm6
  paddq mm7, mm6 //mm7=mm7+mm6
  paddq mm0, mm1 //mm0=mm0+mm1
  movd mm5, eax
  pand mm5, mm2
  psrlq mm2, 32 //分解mm2=mm2:mm5
        paddq mm7, mm5 //mm7=mm7+mm5
  paddq mm0, mm2 //mm0=mm0+mm2
  movd [ebx+20], mm7 //mm7低位存储
  psrlq mm7, 32
  paddq mm0, mm7 //得到进位
//3:3
  movd mm1, [esi+12]
  pmuludq mm1, [edi+12]
//mm0+mm1
  movd mm6, eax
        pand mm6, mm0
  psrlq mm0, 32 //分解mm0=mm0:mm6
  movd mm7, eax
  pand mm7, mm1
  psrlq mm1, 32 //分解mm1=mm1:mm7
  paddq mm6, mm7 //mm6=mm6+mm7
  paddq mm0, mm1 //mm0=mm0+mm1
  movd [ebx+24], mm6 //mm6低位存储
  psrlq mm6, 32
  paddq mm0, mm6 //进位
  movd [ebx+28], mm0 //存储
  emms
//  ret
}
}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 14:47 , Processed in 0.058083 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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