并行FFT实现

并行FFT算法的分析与实现目录1FFT算法分析与实现.............................................................................................................21.1FFT算法的分析...........................................................................................................21.1.1FFT算法的意义.......................................................................................................21.2DFT算法和FFT算法在计算量上的对比......................................................................21.2.1DFT正变换...............................................................................................................21.2.2变换后以2为底的FFT算法.................................................................................22基于二时分FFT算法的蝶式运算定理................................................................................32.1并行可行性分析............................................................................................................32.2难点分析........................................................................................................................42.3FFT算法的实现...........................................................................................................42.3.1计算旋转因子.........................................................................................................42.3.2创建线程.................................................................................................................52.3.3关闭线程.................................................................................................................53蝶形变换...............................................................................................................................54实验结果分析.......................................................................................................................64.1FFT算法效率分析..........................................................................................................64.1.1奇偶两部分的算法效率分析.................................................................................64.1.2蝶形变换内部多线程效率分析.............................................................................85原程序...................................................................................................................................91FFT算法分析与实现1.1FFT算法的分析1.1.1FFT算法的意义在离散傅里叶变换中，若要处理的数据量很大，工作量也变得非常巨大。正是由于这个原因，使得离散傅里叶变换的应用范围在过去很长的时间里受到了严格的限制。而快速傅里叶变换有效的解决了运算量的问题，使得它的理论与方法在数理方程、线性系统分析、信号处理与仿真等很多学科领域都有着广泛的应用。由于计算机只能处理有限长度的离散的序列，所以真正在计算机上运算的是一种离散傅里叶变换。若把此算法应用到并行程序设计中，它的效率将会有进一步的提高，将能得到更广泛的应用。FFT算法有多个不同的变形：基二时分FFT算法、基二频分FFT算法、基四时分FFT算法、基四频分FFT算法。其中基二时分FFT算法是最重要的一种，它是J.W.Cooley和J.W.Tukey在1965年发表的一篇论文中提出。1.2DFT算法和FFT算法在计算量上的对比1.2.1DFT正变换(1-1)公式(1-1)可以看出，对每个n，计算X(n)须作N次复数乘法和N-1次复数加法，要全部计算完成需要N2次复数乘法和N*(N-1)次加法运算，当N非常大时，计算量将非常大。例如N=1024，则要运算2*(1024*1023)次。1.2.2变换后以2为底的FFT算法由式(1-2)可以看出，共有r重和式，每重和式N个方程，每个方程仅需一次乘法运算，因此FFT算法的总计算量为Nr乘法和Nr次加法。如果在考虑WNK=-WNk+N/2，乘法的运算量还可以减少一半。如果在多核环境下用多线程技术让算法很好的并行运行，那么并行部分运行的效率有可能再提升一倍。（1-2）由公式(1-1)和(1-2)可知：FFT的时间复杂度为O(N2)，DFT算法的时间复杂度为O(Nlog2N)，当N很大时，FFT算法的效率可以明显的显示出来。2基于二时分FFT算法的蝶式运算定理设X(k)=DFT[x(n)](0=N,KN-1,n,k为整数,N为偶数)，x0(i)=x(2i)，x1(i)=x(2i+1)(0=i=N/2-1，i为整数)。若X0(k)=DFT[x0(i)]，若X1(k)=DFT[x1(i)]，0=k=N/2-l，则有：x(k)=x0(k)+X1(k)*wkN，X(k+N/2)=X0(k)-x1(k)*wkN(0=k=N/2-1,k为整数)。2.1并行可行性分析由定理可知，基二时分FFT算法在开始时就可以将要运算的数据分成对等的两部分，每部分都可以独立运算，这符合并行程序上的数据分解；且FFT运算内部不用建堆，运算后的数据可以替换先前的数据，这同样也满足了多线程的特点。若是必须要在线程内部建堆，那么当堆到一定程度时，就会出现内存读写错误。而此算法可以很好的避开线程内部建堆。即本算法适用于并行计算。2.2难点分析本算法的难点有两处，一是数据分解的问题，一般情况下可以将数据平均分为两部分，但是基二时分FFT算法不行，因为此算法的后一步会用到上一步的结果，如果直接分成两部分得出的结果一定错误。根据算法本身的特点，再结合并行程序的特性，将数据以序列的形式分为奇偶两部分，将这两部分分别以基二时分FFT算法进行运算，得出的结果再根据定理进行汇总，以得出最终正确的结果。第二个难点在于基二时分FFT算法本身，算法中的蝶形变换本身就是一个三重循环体，每次内部循环的结果都会在下次循环被用到。图1-11为八点蝶形变换情况：图1-1八点蝶形变换图2.3FFT算法的实现2.3.1计算旋转因子旋转因子的计算应分为两部分，一是先计算以数据量为整体数据量的一半的旋转因子，二是计算整体数据量的旋转因子的头半部分。依照数据的顺序将数据分解成为奇偶两部分，且这两部分的数据量相等，因为FFT的数据量要求是2的n次方(n为整数)。2.3.2创建线程创建两个线程，每个线程都以FFT的方法运行上面的一个数据块，因这两个数据块的大小相同，所以这两个线程运行的时间也基本相同，这样可以减少线程间等待的时间，创建线程函数如下：HANDLEhThread[2]；hThread[0]=CreateThread(NULL，0，FtmlProc，thread[O]，0,NULL)；hThread[1]=CreateThread(NULL，0，FunlProc,thread[1]，0,NULL)；一个线程运行结束后，必须等待另外的一个线程运行结束，只有当两个线程都运行结束后才能进行下一步，阻塞等待如下：WaitForMultipleObjects(NUM_THREADS，handle，true，INFINITE)；2.3.3关闭线程关闭创建的线程以释放其所占的系统资源，关闭线程句柄如下：CloseHandle(Thread[0])；CloseHandle(Thread[1])；将运行后的数据合并，当数据量很大时同样可以将合并部分分为多线程来进行。3蝶形变换作为对比，先不考虑算法的特性，直接看蝶形变换的三层循环，将第三层循环体分解为多个线程，若按照这个思路，整个程序的运行过程如下：先经过一次循环变换将数据反序输入，确保数据正序输出，再将数据输入至UFFT算法的核心(三层循环体)，由于上两层的循环需要用到以前的结果，不能独立出来，所以只能对第三层循环体进行线程划分。第一层循环为：For(intpk=0；pkn分解为二进制的位数；pk++)得出后两层所需数据：nl=2*n1，n2=n1/2，d=pk第二层循环为：for(j=0;jn2;j++)第三层循环将其分为两个线程，首先得出第三层循环的两个界限为：实现过程与以奇偶形式划分数据集的FFT方式同。4实验结果分析4.1FFT算法效率分析4.1.1奇偶两部分的算法效率分析分别使用并行傅立叶变换算法和串行傅立叶变换算法对不同个数的数据进行处理，比较两种算法的运行时间。实验结果如表4-1所示，其中N为输入数据总数，T1为FFT串行程序运行时间，T2为FFT并行程序运行时间，h为效率提升的幅度，时间单位是10-7s。表4-1奇偶两部分FFT算法性能对比数据表根据表4-1做图4-1。在双核机器上运行此算法，趋势相同，取时间平均值。为了使算法性能的对比效果更明显，以指数的形式表示数据，其中横坐标为数据量，N代表2N个，纵坐标为时间T，T代表2T*10-7秒，做图4-2。由图4-2可知，当N小于212(4096)时，并行算法的运算速度没有串行算法速度快，当数据总数N达到212时，并行算法与串行算法的效率相当。当N大于212时，并行算法的优势就表现出来。由图4-1可知，随着数据量的增加，并行算法的优势越来越明显，当达到4194304时并行运算较串行运算效率提升39％左右。随着数据量的进