并行FFT实现

并行FFT算法的分析与实现 书目 1 FFT算法分析与实现2 1.1 FFT算法的分析2 1.1.1 FFT算法的意义2 1.2 DFT算法和FFT算法在计算量上的对比2 1.2.1 DFT正变换2 1.2.2 变换后以2为底的FFT算法2 2 基于二时分FFT算法的蝶式运算定理3 2.1 并行可行性分析3 2.2 难点分析4 2.3 FFT算法的实现4 2.3.1 计算旋转因子4 2.3.2 创建线程5 2.3.3 关闭线程5 3 蝶形变换5 4 试验结果分析6 4.1 FFT算法效率分析6 4.1.1 奇偶两部分的算法效率分析6 4.1.2 蝶形变换内部多线程效率分析8 5 原程序9 1 FFT算法分析与实现 1.1 FFT算法的分析 1.1.1 FFT算法的意义 在离散傅里叶变换中，若要处理的数据量很大，工作量也变得特别巨大。正是由于这个缘由，使得离散傅里叶变换的应用范围在过去很长的时间里受到了严格的限制。而快速傅里叶变换有效的解决了运算量的问题，使得它的理论与方法在数理方程、线性系统分析、信号处理与仿真等许多学科领域都有着广泛的应用。由于计算机只能处理有限长度的离散的序列，所以真正在计算机上运算的是一种离散傅里叶变换。若把此算法应用到并行程序设计中，它的效率将会有进一步的提高，将能得到更广泛的应用。 FFT算法有多个不同的变形基二时分FFT算法、基二频分FFT算法、基四时分FFT算法、基四频分FFT算法。其中基二时分FFT算法是最重要的一种，它是J.W.Cooley和J.W.Tukey在1965年发表的一篇论文中提出。 1.2 DFT算法和FFT算法在计算量上的对比 1.2.1 DFT正变换 1-1 公式1-1可以看出，对每个n，计算Xn须作N次复数乘法和N-1次复数加法，要全部计算完成须要N2次复数乘法和N*N-1次加法运算，当N特别大时，计算量将特别大。例如N1024，则要运算2*1024*1023次。 1.2.2 变换后以2为底的FFT算法 由式1-2可以看出，共有r重和式，每重和式N个方程，每个方程仅需一次乘法运算，因此FFT算法的总计算量为Nr乘法和Nr次加法。假如在考虑WNK-WNkN/2，乘法的运算量还可以削减一半。假如在多核环境下用多线程技术让算法很好的并行运行，那么并行部分运行的效率有可能再提升一倍。 （1-2） 由公式1-1和1-2可知FFT的时间困难度为ON2，DFT算法的时间困难度为ONlog2N，当N很大时，FFT算法的效率可以明显的显示出来。 2 基于二时分FFT算法的蝶式运算定理 设XkDFT[xn]0N,KN-1,n,k为整数,N为偶数，x0ix2i，x1ix2i10iN/2-1，i为整数。若X0kDFT[x0i]，若X1kDFT[x1i]，0kN/2-l，则有xkx0kX1k*wkN，XkN/2X0k-x1k*wkN0kN/2-1,k为整数。 2.1 并行可行性分析 由定理可知，基二时分FFT算法在起先时就可以将要运算的数据分成对等的两部分，每部分都可以独立运算，这符合并行程序上的数据分解；且FFT运算内部不用建堆，运算后的数据可以替换从前的数据，这同样也满意了多线程的特点。若是必须要在线程内部建堆，那么当堆到肯定程度时，就会出现内存读写错误。而此算法可以很好的避开线程内部建堆。即本算法适用于并行计算。 2.2 难点分析 本算法的难点有两处，一是数据分解的问题，一般状况下可以将数据平均分为两部分，但是基二时分FFT算法不行，因为此算法的后一步会用到上一步的结果，假如干脆分成两部分得出的结果肯定错误。依据算法本身的特点，再结合并行程序的特性，将数据以序列的形式分为奇偶两部分，将这两部分分别以基二时分FFT算法进行运算，得出的结果再依据定理进行汇总，以得出最终正确的结果。其次个难点在于基二时分FFT算法本身，算法中的蝶形变换本身就是一个三重循环体，每次内部循环的结果都会在下次循环被用到。图1-11为八点蝶形变换状况 图1-1 八点蝶形变换图 2.3 FFT算法的实现 2.3.1 计算旋转因子 旋转因子的计算应分为两部分，一是先计算以数据量为整体数据量的一半的旋转因子，二是计算整体数据量的旋转因子的头半部分。 依照数据的依次将数据分解成为奇偶两部分，且这两部分的数据量相等，因为FFT的数据量要求是2的n次方n为整数。 2.3.2 创建线程 创建两个线程，每个线程都以FFT的方法运行上面的一个数据块，因这两个数据块的大小相同，所以这两个线程运行的时间也基本相同，这样可以削减线程间等待的时间，创建线程函数如下 HANDLE hThread[2]； hThread[0]CreateThreadNULL，0，FtmlProc，thread[O]，0,NULL； hThread[1]CreateThreadNULL，0，FunlProc,thread[1]，0,NULL； 一个线程运行结束后，必需等待另外的一个线程运行结束，只有当两个线程都运行结束后才能进行下一步，堵塞等待如下 WaitultipleObjectsNUM_THREADS，handle，true，INFINITE； 2.3.3 关闭线程 关闭创建的线程以释放其所占的系统资源，关闭线程句柄如下 CloseHandleThread[0]； CloseHandleThread[1]； 将运行后的数据合并，当数据量很大时同样可以将合并部分分为多线程来进行。 3 蝶形变换 作为对比，先不考虑算法的特性，干脆看蝶形变换的三层循环，将第三层循 环体分解为多个线程，若依据这个思路，整个程序的运行过程如下先经过一次循环变换将数据反序输入，确保数据正序输出，再将数据输入至UFFT算法的核心三层循环体，由于上两层的循环须要用到以前的结果，不能独立出来，所以只能对第三层循环体进行线程划分。 第一层循环为 Forint pk0；pkn分解为二进制的位数；pk 得出后两层所需数据nl2*n1，n2n1/2，dpk 其次层循环为forj0;jn2;j 第三层循环将其分为两个线程，首先得出第三层循环的两个界限为实现 过程与以奇偶形式划分数据集的FFT方式同。 4 试验结果分析 4.1 FFT算法效率分析 4.1.1 奇偶两部分的算法效率分析 分别运用并行傅立叶变换算法和串行傅立叶变换算法对不同个数的数据进行处理，比较两种算法的运行时间。试验结果如表4-1所示，其中N为输入数据总数，T1为FFT串行程序运行时间，T2为FFT并行程序运行时间，h为效率提升的幅度，时间单位是10-7s。 表4-1奇偶两部分FFT算法性能对比数据表