雷竞技网页版研究和评论——国际期刊雷竞技苹果下载

国际期刊的创新在计算机和通信工程的研究

菜单

ISSN在线(2320 - 9801)打印(2320 - 9798)

所有提交的电磁系统将被重定向到在线手稿提交系统。作者请直接提交文章在线手稿提交系统各自的杂志。

大整数乘法CUDA FFT (cuFFT)图书馆

Hovhannes Bantikyan
计算机系统和信息部门、国家工程大学亚美尼亚、亚美尼亚埃里温
相关文章Pubmed,谷歌学者

访问更多的相关文章国际期刊的创新在计算机和通信工程的研究

国际期刊的创新在计算机和通信工程的研究

文摘

它是公认的计算机代数理论和系统社区快速傅里叶变换(FFT)可用于多项式相乘。理论预测,“足够”是快速的多项式。的基本思想是利用快速多项式乘法执行快速整数乘法。我们真的可以实现快速FFT乘法在GPU并行FFT实现,在这种情况下cuFFT。这里我们提供cuFFT乘法和其与众所周知的快速大整数运算库(先导入BigInteger, . net GMP, IntX)。我们也比较我们的结果与其他论文的结果。实验表明,cuFFT乘法变得比所有其他测试方法,当我们处理2 ^ 15位数的整数。

关键字
快速傅里叶变换;大整数乘法;GPGPU;CUDA编程;cuFFT

我的介绍。
大整数相乘是一个操作,有许多应用程序在计算科学。许多密码算法需要操作非常大的整数数据的子集。一个常见的应用程序是公开密匙加密的算法通常采用算术整数有数百位[1]。高精度计算还用于计算等基础数学常数π百万甚至更多的数字和分析数字字符串的属性或更一般的调查等功能的确切行为黎曼ζ函数在某些问题很难通过分析方法探索。另一个例子是在呈现分形图像具有极高的放大,如发现了曼德尔勃特集合[2]。
三种最流行的大整数乘法算法Karatsuba-Ofman [3], Toom-Cook[4]和FFT乘法[5]算法。经典的乘法操作有O (n2)复杂性,其中n是数字的数量。利用多项式乘法与FFT,时间复杂度O (nlogn),我们可以显著减少乘法运算的时间。这么大的数据量,基于应用程序的图形处理单元(GPU)成本的基础算法可以有效的解决方案。GPU可以并行处理大量数据时工作在单指令多数据(SIMD)模式。2006年11月,统一计算设备架构(CUDA),是专门用于计算密集的高度并行计算是公布的NVIDIA [6]。NVIDIA的CUDA快速傅里叶变换库(cuFFT)提供了一个简单的接口,用于计算fft算法快10倍。通过使用NVIDIA GPU内数百个处理器核心,cuFFT交付floatingA¢€点性能的GPU而无需开发您自己的自定义GPU FFT的实现。cuFFT使用算法基于著名的Cooley-Tukey和Bluestein算法,所以你可以相信你比以往更快地获得准确的结果[8]。

二世。相关工作
首先让我们讨论一些库和框架,进行高精度计算,特别是大整数乘法。System.Numerics。BigInteger [9]was introduced by Microsoft in .NET 4.0 and is the .NET type for large integers. The BigInteger type is an immutable type that represents an arbitrarily large integer whose value in theory has no upper or lower bounds. The members of the BigInteger type closely parallel those of other integral types. Because the BigInteger type is immutable (see Mutability and the BigInteger Structure) and because it has no upper or lower bounds, an OutOfMemoryException can be thrown for any operation that causes a BigInteger value to grow too large. One of them is IntX [10]. IntX is an arbitrary precision integers library with fast multiplication of big integers using Fast Hartley Transform. The GNU MP Library [11] - one of the fastest well-known Bignum libraries in the world. GNU MP (or GMP) is written in plain C and Assembly language so it compiles into optimized native code, it also uses fast calculation algorithms - that's why it's very fast. GMP is a free library for arbitrary precision arithmetic, operating on signed integers, rational numbers, and floating-point numbers. There is no practical limit to the precision except the ones implied by the available memory in the machine GMP runs on. Among other multiplication algorithms, GMP also uses FFT multiplication (depending on operand size). In [12] implemented FFT multiplication algorithm and done experiments by comparing FFT multiplications with normal multiplications at various bases. Also there is an existing large number multiplication implementation on CUDA by K. Zhao [13], where implemented multipleprecision Karatsuba and Montgomery multiplication algorithms.

三世。离散傅里叶变换
一维离散傅里叶变换(DFT的N-point离散时间信号f (x)由方程给出:
图像(1)
对于u = 0, 1, 2,。N−1。
同样,对于给定F (u)我们可以获得原始离散逆DFT函数F (x):
图像(2)
x = 0、1、2、……N−1。
离散傅里叶变换经常评估为每个数据样本,并可以被视为从信号中提取特定的频率成分。

第四,快速傅里叶变换
简单的方法计算F c的一个元素n需要O (n2)操作。然而,有算法计算F在O (nlogn)的步骤。让我们计算z = (z的傅里叶变换1,……,z2 n)。让F2 n相对于C表示傅里叶变换2 n让Fn相对于C表示傅里叶变换n。定义
图像(3)
让[x]k表示kth一个向量的坐标x
图像(4)
我们定义
图像(5)
这里ZE和Zo向量是分别从Z的偶数和奇数的组件。用这个符号,方程4可以写的更简洁如下。
图像(6)
方程6适用于所有k = 0,…, 2n - 1,但是我们只需要计算Ek和Okk = 0,…,n1because
图像(7)
假设需要T (n)操作来计算一个向量的傅里叶变换在Cn。上面的技巧显示我们可以计算一个向量的傅里叶变换在C2 n使用2 t (n) + 8 n。这是一个分解的计算。
•我们可以计算{Ok}和{Ekk = 0},…,n1in 2T(n) steps.
•我们可以计算ω2 nkk = 0,…,2n1in 2n steps.
•需要三个步骤计算方程的每个实例6。这是一个共有6 n额外的步骤。
我们显然有T (2°)≤8。一个简单的归纳论点
图像(8)
这表明,n = 2k傅里叶变换向量的Cn可以计算在O (n log (n))的步骤。值得一提的是,“一步”在这里指的是比简单的浮点操作更复杂的操作。例如,一个典型的步骤包括乘以一个复数的大小log (n) n根的团结。浮点运算的数量的实际分析需要计算傅里叶变换将取决于如何有效地这些单个步骤就可以完成。

诉架构和CUDA GPU FFT (CUFFT)图书馆
gpu多线程冲击芯片都很大。NVIDIA Tesla产品128标量处理器,12000多个并发线程在飞行中,超过470 GFLOPS持续性能。英伟达显卡架构包括许多所谓的流多处理器(SM)。每一个包括8材质处理器(SP)的核心,一个本地内存共享SP, 16384注册,超越函数的快速ALU单位硬件加速。全局内存是共享的,所有的短信和提供多达4 GB容量和内存带宽144 GB / s。费米架构引入了新的SMs配备32 SPs和32768注册,快速改善ALU单位双精度浮点性能,和L1缓存[14]。
CUDA是一个可扩展的并行编程模型和并行计算的软件环境。很容易使用程序员引入了少量的C语言扩展,以提供并行执行。另一个重要特性是数据结构的灵活性,明确在不同的物理存储器的访问级别的GPU,程序员和良好的框架包括一个编译器,CUDA软件开发工具包(CUDA SDK),调试器,一个分析器,cuFFT cuBLAS科学图书馆。在SIMT GPU执行指令(单指令,多头螺纹)时尚。典型的CUDA的执行程序见图1。
[8]cuFFT关键特性
•1 d, 2 d, 3 d变换复杂和真实的数据类型
•1 d变换大小1.28亿个元素
•灵活的数据布局,允许任意的单个元素和数组维度之间的进步
•基于Cooley-Tukey和Bluestein FFT算法
•熟悉的API类似FFTW高级接口
•流异步执行
•单和双精度转换
•做批处理执行多个转换
•合不就地转换
•灵活的输入和输出数据布局,类似tp FFTW“高级界面”
•线程安全的从多个主机&可调用的线程

VI。CUDA FFT大整数乘法算法
我们现在这个算法与cuFFT大整数相乘。的基本思想是利用快速多项式乘法执行快速整数乘法。图2所示。显示cuFFT乘法算法的流程图。让我们讨论这个图一步一步的每一点。
(颜色:白色-主机代码,黄色——内存复制操作,绿色-设备代码)
1。输入值(a和b)可以给程序以不同的方式输入。我们可以阅读从文件或数据库,或者我们可以设置程序接口。在我们的例子中用户可以插入从接口输入值,但对于测试和实验目的,我们有一个选项来生成随机大整数。数代我们使用数量的数字,由用户设定。
2。与FFT乘法首先我们需要一个整数表示为多项式。的默认标记一个多项式系数的形式。一个多项式p代表系数形式描述的系数向量A = {0,一个1……,n - 1}如下:
图像(9)
我们称之为都多项式的基础,和p (x)的评估是多项式,系数向量,定义基本x。两个多项式相乘的结果在第三个多项式,卷积,这个过程称为向量。与整数相乘,向量卷积需要O (n2)时间。但卷积变得乘法下的离散傅里叶变换(在时域卷积可以通过使用频域乘法):
F F (c) = F (a) (b)
c = F1F (F (a) (b))
一个整数表示为多项式时,我们可以选择在使用什么样的基础。可以使用任何正整数为基础,但为了简单起见,我们限制自己选择以10为底。考虑整数12345的多项式形式使用基础= 10 = {5、4、3、2、1}。由于FFT处理复数,我们必须得到向量的复数。为此,通过设置虚部为零,我们得到一个={(5,0)[4,0],[3,0],[2,0],[1,0]}向量。
3所示。决心blockSize和gridSize CUDA内核。我们做实验来找到最好的块大小CUDA内核,基于块大小和网格尺寸计算。
4所示。这些转移涉及的数据移动最慢的一部分在GPU计算的任何方面。实际的传输速度(带宽)依赖于硬件你使用的类型,但不管这一点上,它仍然是最慢的。设备之间的理论峰值带宽内存和设备处理器明显高于峰值理论主机内存和设备内存之间的带宽。因此,为了获得最大的效果在我们的应用程序中,我们需要减少这些host-device数据传输。如果您有多个转移发生在您的应用程序,试着减少这个数字和观察结果。在我们的例子中我们有两个“复制数据从主机到设备”操作:
cudaMemcpyHostToDevice cudaMemcpy (dev_a, numBytes);
cudaMemcpy (cudaMemcpyHostToDevice dev_b、b numBytes);
5。这里我们执行两个前锋arrayA和arrayB fft算法。结果多项式乘法arrayA和arrayB arrayC两次度大于arrayA和arrayB最高的学位。所以学位arrayC将计算为:
signalSize = 2 (。长度> b.Length ?一个。长度:b。长度)
向前执行之前傅里叶变换,我们填充系数arrayA和arrayB signalSize 0。我们执行cuFFT signalSize和cufftype.c2c计划。
6。在这一点上我们有两个转移阵列设备,我们必须执行成对乘法。因为我们处理复杂的数据,我们有:
复杂的c;
c。x = a。x * b。x - a。y * b.y;
c。y =。x * b。x +一个。y * b.y;
7所示。在这里,我们为arrayC执行逆FFT
8。的公式变换cuFFT使用非正交的√6倍(signalSize)。正常化signalSize和1 / signalSize需要使用fft算法计算傅里叶级数系数时,我们把结果点7 signalSize设备。
9。这一点类似于4点,只有在这里,我们复制内存从设备到主机
10。进位传递是最后一步生成多项式。我们将这个操作的伪代码:
伪代码1。进位传递对大整数乘法
输入:sourceArray整数数组
输出:resultArray整数数组
1。CarryPropagation ()
2。携带:= 0
3所示。(我从0到sourceArray.length)
4所示。总结:=携带+ sourceArray[我]
5。国防部:=和% 10
6。resultArray.Add (mod)
7所示。携带:=资金/ 10
8。结束了
9。而(携带> 0)
10。如果携带。长度> 1)
11。指数:=。长度- 1
12。其他的
13。指数:= 0
14。结束
15。resultArray.Add(携带(指数))
16。携带:=携带/ 10
17所示。结束时
11。在最后一步我们形式从多项式并将结果发送到输出整数表示。

七世。实验和结果
我们已经意识到在CUDA 5.5 cuFFT乘法算法,并进行了一系列的基准使用GeForce GT 630显卡在桌面处理器,英特尔(R)的核心(TM) i3 - 2100 3.10 ghz和4 GB内存。这个显卡有计算能力2.1,由96 CUDA整数和单精度浮点算术运算。我们第一次不同的块大小和计算网格大小基于块大小发现他们对性能的影响。大整数随机生成测试。我们生成与不同数量的整数位数。表1中给出了块大小对性能的影响。我们计算时间以毫秒为一个乘法操作。我们取平均值为每个数据大小后做100个测试乘法操作。大整数的一代时间不考虑计算。
图3所示。显示了图的实验结果如表1所示。正如我们所看到的,我们有一个最佳性能的乘法,当块大小的内核是256。我们用以下公式计算网格大小
gridSize = vectorSize / blockSize + (vectorSize % blockSize != 0 ?1:0)
vectorSize多项式相乘的长度,“/”和“%”吗div和国防部分别操作。水平轴的图3给出了数字的数量乘以整数乘法和纵轴是时间,以毫秒为单位。块大小决定了可以并行执行的线程的数量在一个块。块大小是基于GPU的最大值。我们最多可以有512个线程/ 1块gpu的计算能力。x和1024个线程每2块gpu的计算能力。倍和3.倍。
在他的论文安藤Emerencia礼物FFT与正常的乘法,乘法算法及其比较在不同的基地[12]。在图4中给出的结果为基地10 [12]。我们将讨论以10为底的,因为我们的实验也为基础做了10。个人价值观的测量也列入下表。我们看到一个输入的大小超过200 FFT方法变得越来越速度比正常的乘法。对于一个输入大小为105,FFT乘法算法耗时258毫秒,而正常的增殖需要超过28秒,所以所需的时间不同的比例超过一百人。
我们看到一个输入的大小超过200 FFT方法变得越来越速度比正常的乘法。对于一个输入大小为105,FFT乘法算法耗时258毫秒,而正常的增殖需要超过28秒,所以所需的时间不同的比例超过一百人。如果我们比较图4和图3中,我们可以看到,cuFFT乘法多倍,大约快5 x输入大小为105。
任意精度的算法在大多数计算机软件实现通过调用一个外部的库,它提供了数据类型和子程序来存储数字要求精度和执行计算。不同的图书馆有不同的方法来表示任意精度的数字。有许多任意精度的运算库执行大整数乘法。我们选择三个运行我们的实验:
•Microsoft . net System.Numerics。BigInteger [9]
•IntX [10]
•GNU议员(GMP) [11]
表2中给出的比较cuFFT先导入BigInteger,乘法运算和乘法的。net IntX和GMP库。实验对不同大小的输入整数(数字)。实验结果提供一个乘法操作的时间,以毫秒为单位。我们已经做了100乘法为每个数据大小和图书馆,并采取平均的结果。图5是表2的图表示。
从这个图我们可以看到,对于5000位的整数,cuFFT先导入BigInteger和IntX快于。net,但GMP是最快的。cuFFT变得比GMP从与50000位整数。数据大小105。cuFFT比GMP约2倍。

八世。结论
我们可以看到,我们使用基于GPU的并行乘法算法性能增益,CUDA cuFFT库。实验表明,cuFFT乘法变得比所有其他测试方法,当我们处理215位数的整数。

表乍一看
表的图标 表的图标
表1 表2

数据乍一看
图1 图2 图3 图4 图5
图1 图2 图3 图4 图5

引用














全球技术峰会