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

《多核程序設計總結報告——並行fft算法的實現與研究小組成員》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、多核程序设计总结报告——并行FFT算法的实现与研究小组成员：09008106陈慧09008110姜立波报告时间：2011年3月30日一、实验目的通过引入多线程的并行处理，使得快速傅里叶变换在多核处理器上获得更加的处理性能。利用将串行算法中的性能瓶颈部分并行化，达到提高效率的目的，并通过实验研究多线程在机器上的实际性能，加深对多核及其相关概念的理解。二、设计思路1、基本算法设序列点数为N=2^L，L为整数，如果不满足，可人为添加零项使之达到这一要求。并且将x(n)分为奇偶两组，其中x1（r）=x(2r),x2（r）=x（2

2、r+1）(r=0,1，……，N/2-1)。DFT根据公式可以表示为：  ，令   ，  (k，r取值为0,1，……，N/2-1)。因 ， ，所以可得：  ，因此只需计算0到（N/2-1）区间的所有X1（k）和X2（k）即可，这种方法把一个N点的DFT序列分解为两个N/2个点的子DFT序列，将子序列按同样的方法分解下去直到不能为止，最后即可计算出N点的DFT序列。2、并行化由于将结点每次分两组，两组之间的计算互不干扰，则有关这两组的计算可以在多核处理器上并行。理论上每次对结点分解后都可以创建新的线程来对其进行并行处理，但由

3、于测试所用CPU为IntelCore2双核处理器，因此我们提交的程序仅仅创建了两个线程对第一次分解后的结点作并行化。更多的线程我们也作了实现，但在双核处理器上出现了性能的退化。三、主要函数及注释1、FFT计算的主体calculate()函数if(!y

4、

5、!x)return0;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[begi

6、n+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,calcu

7、late1,p_2,0,NULL);//创建新线程执行calculate1函数WaitForMultipleObjects(2,hThread,TRUE,INFINITE);//等待两个线程执行完成后合并doublew=2*pi/length;for(inti=begin;i

8、[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(intj=begin+n/2;j

9、cos(w*length*(j-begin-n/2)/n)*y_temp1[j]-sin(w*length*(j-begin-n/2)/n)*y_temp[j];}for(intk=begin;k

10、