CUDA和大数计算

liangbch

Nvidia 提供了一个CPU和GPU统计计算的编程框架CUDA，利用这个开发工具，可充分利用GPU运算单元多，并行执行能力强的优势。可大大加速科学计算类软件的运行效率。 以下内容摘自HugeCalc vs. GMP(http://bbs.emath.ac.cn/viewthrea ... fromuid=25#pid28947) 我们大家都知道，当数的规模很大时，最有效的大数乘法算法是FFT或者FFT的变种。 著名的圆周率计算程序super-pi，用的就是纯粹的浮点FFT. 另外，一个ooura FFT例子程序也给出了用FFT计算圆周率的代码，由于该FFT的效率很高，用它的这个程序计算圆周率比super-pi更快。可从7种FFT代码和测试程序（http://download.chinaprj.cn/detail/iDiTbqBB） 下载到ooura的的源码和计算圆周率的程序。 当前，显示卡的 GPU 浮点运算单元有越来越多的趋势，其频率也越来高。用GPGPU是做大规模科学计算不但成为可能，而且速度比传统的CPU快得多。大概在2008年，nvidia 推出一个开发工具包cuda,利用这个开发工具包，工程师能够利用Nvidia的显示卡做科学计算，该开发包提供了预编译的FFT和BLAS库。我想，利用它的cuda FFT,来做大数乘法，速度应该比使用CPU快上很多。 我想，我们可以尝试使用CUDA来做大数计算。 关于cuda的减少，请参阅：http://en.wikipedia.org/wiki/CUDA,可从http://www.nvidia.cn/object/cuda_get_cn.html下载开发工具包 支持cuda的显卡应该是从GeForce 8 系列开始，我查了一下，GeForce 8 Series 发布于2007 年夏天。 值得注意的是，早期的Geforece 显示卡和个别GeForce_200_Series 不支持双精度浮点计算，关于Geforce显卡的技术指标，可在wiki上查找，例如 Geforce 2系列的资料可从http://en.wikipedia.org/wiki/GeForce_200_Series. CUDA 开发包包含以下组件 C/C++ compiler CUDA Visual Profiler OpenCL Visual Profiler GPU-accelerated BLAS library GPU-accelerated FFT library Additional tools and documentation

liangbch

附上一篇论文，该文通过几个典型应用，给出的CUDA计算的优势和性能数据，文章指出采用Geforce 8800GT显示芯片，CU FFT的效率是 WFFT的15倍多。

liangbch

值得注意的是，楼上的FFT测试是 单精度浮点型1维FFT。由于双精度浮点型运算的速度比单精度慢的多，而基于FFT的大数乘法需要使用双精度浮点类型，所以是用CUDA做大数运算可能不是很乐观。 以下的内容（摘自NVIDIA CUDA FAT version 2.1）指出，双精度浮点的速度仅为单精度浮点的1/8. What are the technical specifications of the NVIDIA Tesla C1060 Processor ? The Tesla C1060 consists of 30 multiprocessors, each of which is comprised of 8 scalar processor cores, for a total of 240 processors. There is 16KB of shared memory per multiprocessor. Each processor has a floating point unit which is capable of performing a scalar multiply-add operation per clock cycle. Each multiprocessor also includes two special function units which execute operations such as rsqrt, rcp, log, exp and sin/cos. The processors are clocked at 1.296 GHz. The peak computation rate accessible from CUDA is therefore around 933 GFLOPS (240 * 3 * 1.296). If you include the graphics functionality that is accessible from CUDA (such as texture interpolation), the FLOPs rate is much higher. Each multiprocessor includes a single double precision multiply-add unit, so the double precision floating point performance is around 78 GFLOPS (30 * 2 * 1.296). The card includes 4 GB of device memory. The maximum observed bandwidth between system and device memory is about 6GB/second with a PCI-Express 2.0 compatible motherboard. Other GPUs in the Tesla series have the same basic architecture, but vary in the number of multiprocessors, clock speed, memory bus width and amount of memory. See the programming guide for more details.

gxqcn

FFT大数乘法也可用单精度的。 但由于累计误差的问题，直接支持的规模不能太大， 可以先切分成适当长度的段，先用类似Karatsuba及Toom等算法降低单个乘法的规模， 采用上述算法一是变得复杂了，二是内存耗用变大了，三是计算总次数增大了。

gxqcn

更正一下：不是因为“累计误差的问题”，而是受限于卷积后可表达对应位上乘积之和的最大值。

liangbch

5# gxqcn 就大数计算而言，短序列的FFT没有任何性能上的优势，故我说“而基于FFT的大数乘法需要使用双精度浮点类型”。 关于CUDA的整数运算和位宽问题 当前，CUDA提供了一个24bit整数乘法的函数， __mul24 和 __umul24，这2个函数可以计算2个24bit整数的乘法，结果保留最低32bit，它的速度很快，对于每一个multiprocessor, 每个周期可执行8次乘法运算，和单精度浮点乘法一样快。 说明，低端的GT 220有6个multiprocessor，而高端的GTX 275则有30个multiprocessor.

gxqcn

我曾帮人家做的那套RSA，其DSP好像也是24bit的整数，但它支持标准C的64位整数，内部调用函数实现。 过低的位宽将给算法的设计带来很大的限制。

无心人

8系列已经是老黄历啦 诸位看看Fermi的规格，似乎支持32位整数乘法了 仅仅是超并行的架构就可以获益了

gxqcn

还真想多了解了解这个不是新生事物的新生事物， 大家把自己知道的信息多共享共享啊。。。

liangbch

Fermi架构的400系列，最便宜的也得2500+米。