karatsuba乘法两种算法比较测试

无心人 · 发表于 2008-4-29 11:46:38

我们都有了SSE4了

P4也是7年前的老爷了

liangbch · 发表于 2008-4-29 11:54:00

我的观点:
1.最合适的解决方案是自动侦测CPU类型，尽量针对每一种CPU使用优化的实现。
2.加减法的优化对整体kara_mul的贡献并不大，估计使用SSE2指令对乘法的整体贡献不超过3%.
3.不支持SSE2的cpu必须考虑。我2004年买的AMD2500+尚不支持SSE2指令。

liangbch · 发表于 2008-4-29 11:59:19

3.不支持SSE2的cpu必须考。我2004年买的AMD2500+尚不支持SSE2指令。

对这点我感到有点疑惑，我用CPU-Z检测的结果是不支持SSE2,但刚才在网上查了一下，有些网页说支持SSE2

gxqcn · 发表于 2008-4-29 12:02:48

“传说”中的64bit版的 HugeCalc，可以默认用户的机器配置已足够高了。

但，在64位操作系统下，128位SIMD指令集似乎对我已没有太大的吸引力了。

liangbch · 发表于 2008-4-29 12:14:11

原帖由 无心人 于 2008-4-29 11:31 发表
GxQ
你没考虑过你的加减法和求负还有内存拷贝都不是最优的

加减存在一次处理4X32位操作的算法
求负，拷贝存在一次处理4X128位操作的算法

不知道无心人说的加减存在一次处理4X32位操作的算法指什么，是指采用循环展开呢？还是指使用SSE2指令优化呢？从http://bbs.emath.ac.cn/thread-269-3-1.html 的22# 的测试结果来看，对于PM, SSE2指令反而更慢，而循环展开却效果非常明显。对于P4电脑，SSE2指令加速效果明显，但速度提升不超过100%

无心人 · 发表于 2008-4-29 13:41:49

SSE2优化是针对你的算法

我的只能是4路并行

另外
SSE4存在4X64位算法

还有，我不推荐自动侦测CPU类型
我觉得，这么做不好

比如HugeCalc完全可以将对老CPU的支持固定在8.0
9.0起点就是SSE2或者干脆是SSE4+64位

：）

另外，128位SIMD运算目前并没有CPU支持的
除了逻辑运算
都是并行64位，一次两个64位

所以说，未来不排除出现128位加和128位乘的SIMD

liangbch · 发表于 2008-4-29 14:55:24

回楼上，即使使用SSE2指令做并行加法，进位的处理仍然只能串行进行，而况做进位处理时，需要将128bit解包。故我认为即使计算以2^30为基的大数加法，SSE2指令亦无多大优势可言。

无心人 · 发表于 2008-4-29 15:00:16

你没考虑每循环的指令延迟问题

账号		自动登录	找回密码
密码			欢迎注册

[讨论] karatsuba乘法两种算法比较测试