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

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

[复制链接]
 楼主| 发表于 2008-3-6 11:08:51 | 显示全部楼层
我想这么写
xmm0=r0:1:2:3
xmm1=l0:1:2:3
xmm0=xmm0*xmm1
则xmm0 = (0:0) /2:2
但其他组合,并无好方式处理
如果越界
xmm0=r1:2:3:X
恐怕出现非法读错误吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-6 11:10:36 | 显示全部楼层
除了movd movq pmuludq movdq2q movq2dq外
还下面的指令似乎有用
pack的似乎无处理DWORD的好指令
PUNPCKHDQ instruction with 128-bit operands:
DEST[31:0] ← DEST[95:64];
DEST[63:32] ← SRC[95:64];
DEST[95:64] ← DEST[127:96];
DEST[127:96] ← SRC[127:96];
PUNPCKHQDQ instruction:
DEST[63:0] ← DEST[127:64];
DEST[127:64] ← SRC[127:64];

PUNPCKLDQ instruction with 128-bit operands:
DEST[31:0] ← DEST[31:0];
DEST[63:32] ← SRC[31:0];
DEST[95:64] ← DEST[63:32];
DEST[127:96] ← SRC[63:32];
PUNPCKLQDQ
DEST[63:0] ← DEST[63:0];
DEST[127:64] ← SRC[63:0];

MOVDDUP—Move One Double-FP and Duplicate
dest[0:63] = src[0:63]
dest[127:64]=src[0:63]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-6 11:13:02 | 显示全部楼层
另外
乘法得到的寄存器结果
必须要照顾后来的加操作

加必须要解开64位乘结果为两个32位数字
否则加会溢出
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-6 11:15:49 | 显示全部楼层
我先在的想法是, 掉用 pmuludq 6次, 调用mul指令4次,完成乘法计算,至于进位,使用xmm 128bit寄存器计算。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-6 11:19:39 | 显示全部楼层
确如无心人所言,解包很麻烦,从而引起指令数增加。不过,我想试试,到底是直接的方法(一次只计算32bit * 32bit)快呢,还是使用复杂的方法(一次 计算2 个32bit * 32bit )快呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-6 11:28:41 | 显示全部楼层
http://topic.csdn.net/t/20040713/08/3168983.html
这里有我老帖
是我说MMX寄存器乘法快的证据

=============================
另外我刚想到一个好办法
能得到双乘法效果
且能得到全部16个乘
下午看看

不过可惜这么做
SSE寄存器不够用

64位好了
有16个
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-6 12:22:16 | 显示全部楼层
我还是找不到打包乘,然后解包并处理进位的有效手段,指令增加的太厉害了,决定放弃这个方案。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-6 12:46:34 | 显示全部楼层
原帖由 无心人 于 2008-3-6 11:28 发表
不过可惜这么做
SSE寄存器不够用

64位好了
有16个


寄存器不够可以在汇编中使用栈嘛


推荐大家用我在 6# 发的附件,因为它实现了:
1、CPU指令集的自动识别;
2、高精度计时器;
3、一个高效且可靠的对比函数,以方便大家检验自己算法的正确与否;
4、一个统一的测试接口。


为了大家有个公平的擂台环境,我想补充几条规定:
1、允许使用C语言以及ALU、MMX、SSE、SSE2汇编,SSE3/SSE4及未来的SSE5暂不予考虑;
2、编译器及版本不限;
3、OS暂限定于32位平台;
4、测试程序中不允许多线程(比如说将1000万次测试分拆成两个500万次并行线程);
5、提交的最终代码,应保证函数级完整,以方便他人测试(普通交流,允许发代码片断);
6、提交的函数名推荐以 6# 描述的那样:“UInt128x128To256_{1}_{2}(...) ”,
 其中{1}代表用到的最高级指令集;
   {2}代表发帖楼层,如果写错了可以自行修订或请管理员帮助修改。

对于最后的优胜者,可以考虑一定的奖励;
只是还没想好具体方式(主要以论坛积分等形式),欢迎大家讨论。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-6 13:38:33 | 显示全部楼层
奖励什么就免了
除非你有权把CSDN社区银行的书换成我感兴趣的
哈哈

SSE4也无法分解64位
所以分解还得movd加移位
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-6 13:42:29 | 显示全部楼层
使用堆栈并不比分步乘简单
所以使用堆栈方案我觉得可以Cancel

如果有简单方法能做到循环移位
我有很少指令做16个乘法的方案

以下四行一组, 第一行为left, 第二行为right, 数字为双字编号,
第三四行为双乘结果对应编号 X:Y 代表leftX*rightY
前4个能通过简单移位得到, 后四个要看Movd xmm, mem32是否冲掉xmm的高96位!!
如果否, 则简单, 如果是, 则需要POR指令还加一个额外积存器
0 1 2 3
0 1 2 3
0:0
2:2

1 2 3 0
1 2 3 0
1:1
3:3

0 1 2 3
1 2 3 0
0:1
2:3

1 2 3 0
0 1 2 3
1:0
3:2

3 0 1 2
0 1 2 3
3:0
1:2

0 1 2 3
3 0 1 2
0:3
2:1

0 1 2 3
2 3 0 1
0:2
2:0

1 2 3 0
3 0 1 2
1:3
3:1
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 19:33 , Processed in 0.164140 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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