多核程序設計總結報告——並行fft算法的實現與研究小組成員.docVIP

多核程序设计总结报告 ——并行FFT算法的实现与研究 小组成员： 陈慧 姜立波 报告时间： 2011年3月30日 一、实验目的 通过引入多线程的并行处理，使得快速傅里叶变换在多核处理器上获得更加的处理性能。利用将串行算法中的性能瓶颈部分并行化，达到提高效率的目的，并通过实验研究多线程在机器上的实际性能，加深对多核及其相关概念的理解。 二、设计思路 1、基本算法 设序列点数为N=2^L，L为整数，如果不满足，可人为添加零项使之达到这一要求。并且将x(n)分为奇偶两组，其中x1（r）=x(2r), x2（r）=x（2r+1）r=0,1，……，N/2-1DFT根据公式可以表示为：，令?，k，r取值为0,1，……，N/2-1因，，所以可得：，因此只需计算0到（N/2-1）区间的所有X1（k）和X2（k）即可，这种方法把一个N点的DFT序列分解为两个N/2个点的子DFT序列，将子序列按同样的方法分解下去直到不能为止，最后即可计算出N点的DFT序列 2、并行化 由于将结点每次分两组，两组之间的计算互不干扰，则有关这两组的计算可以在多核处理器上并行。理论上每次对结点分解后都可以创建新的线程来对其进行并行处理，但由于测试所用CPU为Intel Core2双核处理器，因此我们提交的程序仅仅创建了两个线程对第一次分解后的结点作并行化。更多的线程我们也作了实现，但在双核处理器上出现了性能的退化。 三、主要函数及注释 1、FFT计算的主体calculate()函数 if(!y || !x) return 0; else { change(n,begin); //用于对结点进行排序 if(n == 2) { y_temp[begin]=x[begin]+x[begin+1]; y_temp1[begin]=x_1[begin]+x_1[begin+1]; y_temp[begin+1]=x[begin]-x[begin+1]; y_temp1[begin+1]=x_1[begin]-x_1[begin+1]; } else { p_1[0]=n/2; //以p开头的数组存放了长度、起始值等参数用于传递给线程 p_1[1]=begin; p_2[0]=n/2; p_2[1]=begin+n/2; hThread[0] =CreateThread(NULL, 0,calculate1, p_1, 0, NULL );//创建新线程执行calculate1函数 hThread[1] = CreateThread(NULL, 0, calculate1, p_2, 0, NULL );//创建新线程执行calculate1函数 WaitForMultipleObjects(2, hThread, TRUE, INFINITE); //等待两个线程执行完成后合并 double w=2*pi/length; for(int i=begin;ibegin+n/2;i++) //对前半段结点处理 { y[i]=y_temp[i]+cos(w*length*(i-begin)/n)*y_temp[i+n/2]-sin(w*length*(i-begin)/n)*y_temp1[i+n/2]; y_1[i]=y_temp1[i]+cos(w*length*(i-begin)/n)*y_temp1[i+n/2]+sin(w*length*(i-begin)/n)*y_temp[i+n/2]; } for(int j=begin+n/2;jbegin+n;j++) //对后半段结点处理 { y[j]=y_temp[j-n/2]-cos(w*length*(j-begin-n/2)/n)*y_temp[j]+sin(w*length*(j-begin-n/2)/n)*y_temp1[j]; y_1[j]=y_temp1[j-n/2]-cos(w*length*(j-begin-n/2)/n)*y_temp1[j]-sin(w*length*(j-begin-n/2)/n)*y_temp[j]; } for(int k=begin;kbegin+n;k++)