数学研发论坛

 找回密码
 欢迎注册
查看: 114|回复: 7

[讨论] 多核时代下的大数乘法

[复制链接]
发表于 2018-2-8 14:48:41 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
一个多精度算法库中,最关键的是,其核心超大整数乘法算法的效率。

当前连手机都已进入多核时代,所以探讨可高度并行的算法具有现实的意义。

在本贴中,希望就此话题深入探讨,
这也将是我重启大整数算法开发的技术储备之一,并将影响到整体框架的架构。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-2-8 14:55:36 | 显示全部楼层
总所周知,当前最快的大整数乘法,基本上都是 FFT,或其变种,如 NTT 等。

若讲到核数之多,莫过于 GPU,而 cuFFT 即是运行在 GPU 上的 FFT
我对之感兴趣的地方是:对于可以表示为 \(N = 2^a \times 3^b \times 5^c \times 7^d\) 的输入规模,CUFFT会自动采用一些优化算法来达到最佳的运算性能
不知其实现原理是什么?若有 cuFFT 源码或文档可拜读一下就好了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-8 15:35:10 | 显示全部楼层
1)cuFFT是CUDA的闭源商用包的子集功能,应该都是些GPU操控的指令集,想拿源码估计不可能了.而且对CPU上编程的我们的参考意义可能还不如看看FFTW更实在吧.FFTW文档有关于FFTW的多线程支持
2)至于算法原理,查到官网说用的是 Cooley-Tukey 和 Bluestein算法.https://developer.nvidia.com/cufft,你给的链接内容其实更详细呢.
3)据说facebook搞的一个fbFFT比cuFFT强https://arxiv.org/abs/1412.7580

评分

参与人数 1威望 +12 贡献 +12 鲜花 +12 收起 理由
gxqcn + 12 + 12 + 12 谢谢提供的参考资料!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-2-8 15:47:53 | 显示全部楼层
刚从其官网上下载了 pdf 档:CUFFT_Library.pdf

P21 有这么一段:
A transform of size \(2^n\) or \(3^n\) will usually be faster than one of size \(2^i \times 3^j\) even if the latter is slightly smaller, due to the composition of specialized paths.
我希望的是可以实现诸如 \(18 \times 2^n\) 类型的输入长度,搞好了,可 \(18\) 核并行处理,岂不妙哉?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-2-8 16:03:38 | 显示全部楼层
其收益不仅仅是可以让尽可能多的核高度并行,某些情形下还可以节省内存,减少补零的段数。
比如:在 \(1024\) 以内,\(2^{10}*3^6*5^4*7^2\) 的正因子数多达 \(141\) 个;若仅局限于 \(2\) 的整数次幂,则仅有 \( 2^r(0\leqslant r\leqslant 10) \) 这 \(11\) 个正因子了。

相关帖子: 千万以内因数数目最多的是哪个?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-8 18:44:18 | 显示全部楼层
完全不懂这一块~~嘴上支持一下,哈哈。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-8 20:43:05 | 显示全部楼层
郭老板终于向并行迈进了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-2-9 07:52:40 | 显示全部楼层
其实,十年前我已用线程池并行计算了,
只是感觉当前算法在更多核(比如 18 个)情形下还不方便充分发挥 CPU 的作用。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2018-2-25 21:55 , Processed in 0.075951 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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