多核时代下的大数乘法

gxqcn

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

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

在本贴中，希望就此话题深入探讨，
这也将是我重启大整数算法开发的技术储备之一，并将影响到整体框架的架构。。。

gxqcn

众所周知，当前最快的大整数乘法，基本上都是 FFT，或其变种，如 NTT 等。

若讲到核数之多，莫过于 GPU，而 cuFFT 即是运行在 GPU 上的 FFT
我对之感兴趣的地方是：对于可以表示为 \(N = 2^a \times 3^b \times 5^c \times 7^d\) 的输入规模，CUFFT会自动采用一些优化算法来达到最佳的运算性能
不知其实现原理是什么？若有 cuFFT 源码或文档可拜读一下就好了。

wayne

１）cuFFT是CUDA的闭源商用包的子集功能，应该都是些GPU操控的指令集，想拿源码估计不可能了．而且对CPU上编程的我们的参考意义可能还不如看看FFTW更实在吧．FFTW文档有关于FFTW的多线程支持
２）至于算法原理，查到官网说用的是 Cooley-Tukey 和 Bluestein算法．https://developer.nvidia.com/cufft，你给的链接内容其实更详细呢．
３）据说facebook搞的一个fbFFT比cuFFT强https://arxiv.org/abs/1412.7580

gxqcn

刚从其官网上下载了 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\) 核并行处理，岂不妙哉？

gxqcn

其收益不仅仅是可以让尽可能多的核高度并行，某些情形下还可以节省内存，减少补零的段数。
比如：在 \(1024\) 以内，\(2^{10}*3^6*5^4*7^2\) 的正因子数多达 \(141\) 个；若仅局限于 \(2\) 的整数次幂，则仅有 \( 2^r(0\leqslant r\leqslant 10) \) 这 \(11\) 个正因子了。

相关帖子： 千万以内因数数目最多的是哪个？

282842712474

完全不懂这一块～～嘴上支持一下，哈哈。

zeroieme

郭老板终于向并行迈进了

gxqcn

其实，十年前我已用线程池并行计算了，
只是感觉当前算法在更多核（比如 18 个）情形下还不方便充分发挥 CPU 的作用。

Ickiverar

其实，长度为N*M的FT，可以分解成N个长度为M的FT之后再做M个长度为N的FT。
所以这样至少就是 N 核与M 核并行。
在我的大数库里，对N=2^6以上的输入规模，就分解成 N=2^k1 * 2^k2，如果我想的话可以立即把它们弄成8核并行（虽然实际上我的库还是单线程的）。
对极大规模的输入 N>2^12，就可以轻易地64核并行。这只是使用基2的结果。
如果用 基2 3 5 7的混合基FFT，那就会有你说的节省内存的效果。

gxqcn

Ickiverar 发表于 2018-2-27 13:44
其实，长度为N*M的FT，可以分解成N个长度为M的FT之后再做M个长度为N的FT。
所以这样至少就是 N 核与M 核并 ...

第一行就没看明白。

楼上开发的大数库，可有提供下载测试？很想体验一下。。。