并行计算课程设计任务书

1、*实践教学*兰州理工大学 理学院 2016年春季学期 并行计算 课程设计专业班级：2013级信息与计算科学2班姓 名： 学 号： 13540216 指导教师： 成 绩： 基于串行FFT蝶式递归计算摘要本文主要设计快速傅氏变换两种经典的串行算法之一的递归算法（蝶式）。它是利用分治的思想来推导递归的FFT计算算法，将b元素或a元素之下标分别按偶下标与奇下标展开而推导出的递归式。算法主要过程如下：首先主进程对输入的元素按其下标进行奇偶划分，然后分配给两个处理器，分别在各自的处理器在进行同样的划分、并计算其结果，将结果带入到上一层再进行计算，最后将结果带入到主进程合并进行计算，输出结果。关键字： 蝶式

2、计算 傅里叶变换 递归算法目录一题目及要求11.1设计题目11.2设计参数11.3测试实例1二设计算法及要求12.1 算法设计原理12.2 算法设计2三算法描述与设计流程33.1算法描述33.2 流程图4四原程序代码与运行结果54.1 源程序54.2 运行结果10五算法分析及其优缺点115.1 算法分析115.2 优缺点12六总结13七参考文献142一题目及要求1.1设计题目 串行FFT递归算法（蝶式递归计算原理）求傅里叶变换1.2设计参数 蝶式递归计算原理、算法性能和误差分析1.3测试实例对给定的，利用串行FFT递归算法（蝶式递归计算原理）计算其傅里叶变换的结果。二设计算法及要求2.1 算法

3、设计原理 令 为n/2次单位元根，则有 .将b向量的偶数项 和奇数项 分别记为 和 注意推导中反复使用 2.2 算法设计对于以上的分析可画出如图 1所示的离散傅里叶变换递归计算流图。图1 n=8的FFT蝶式计算图三算法描述与设计流程3.1算法描述开始3.2 流程图输入序列对应值（例如5+j3，输入5 3）计算出前size_x/2个exp(-j*2*k/size_x)个值，即W的值级数i>=错误!未找到引用源。？级数i加1 是 输出fft结果序列结束 否 该级该组起始下标j>=错误!未找到引用源。？计算出该级需要的W的个数l 是 否该级该组元素序数k>=错误!未找到引用源。？组

4、起始下标加2*lK加1 是Xj+k Xj+klXj+k+l*W(size_x/2/l)*k Xj+k+l -1 否 图2 算法设计流程图四原程序代码与运行结果4.1 源程序/*FFT*/ /整个程序输入和输出利用同一个空间xN，节约空间 #include <stdio.h> #include <math.h> #include <stdlib.h> #define N 1000 /定义输入或者输出空间的最大长度 typedef struct double real; double img; complex; /定义复数型变量的结构体 void fft();

5、/快速傅里叶变换函数声明 void initW(); /计算W(0)W(size_x-1)的值函数声明 void change(); /码元位置倒置函数函数声明 void add(complex,complex,complex *); /*复数加法*/ void mul(complex,complex,complex *); /*复数乘法*/ void sub(complex,complex,complex *); /*复数减法*/ void divi(complex,complex,complex *); /*复数除法*/ void output(); /*输出结果*/ complex xN

6、,*W; /*输出序列的值*/ int size_x=0; /*输入序列的长度，只限2的N次方*/ double PI; /pi的值int main() int i; system("cls"); PI=atan(1)*4; printf("Please input the size of x:n"); /*输入序列的长度*/ scanf("%d",&size_x); printf("Please input the data in xN:(such as:5 6)n"); /*输入序列对应的值*/ for

7、(i=0;i<size_x;i+) scanf("%lf %lf",&xi.real,&xi.img); initW(); /计算W(0)W(size_x-1)的值 fft(); /利用fft快速算法进行DFT变化 output(); /顺序输出size_x个fft的结果 return 0; /*进行基-2 FFT运算,蝶形算法。这个算法的思路就是， 先把计算过程分为log(size_x)/log(2)-1级（用i控制级数）； 然后把每一级蝶形单元分组（用j控制组的第一个元素起始下标）； 最后算出某一级某一组每一个蝶形单元（用k控制个数，共l个）。*/

8、 void fft() int i=0,j=0,k=0,l=0;complex up,down,product; change(); /实现对码位的倒置 for(i=0;i<log(size_x)/log(2);i+) /循环算出fft的结果 l=1<<i; for(j=0;j<size_x;j+=2*l) /算出第m=i级的结果【i从0到（log(size_x)/log(2)）-1】 for(k=0;k<l;k+) /算出第i级内j组蝶形单元的结果 /算出j组中第k个蝶形单元 mul(xj+k+l,W(size_x/2/l)*k,&product); /

9、*size/2/l是该级W的相邻上标差，l是该级该组取的W总个数*/ add(xj+k,product,&up); sub(xj+k,product,&down); xj+k=up; /up为蝶形单元右上方的值 xj+k+l=down; /down为蝶形单元右下方的值 void initW() /计算W的实现函数 int i; W=(complex *)malloc(sizeof(complex) * size_x); /*申请size_x个复数W的空间(这部申请的空间有点多，实际上只要申请size_x/2个即可)*/for(i=0;i<(size_x/2);i+) /*

10、预先计算出size_x/2个W的值，存放,由于蝶形算法只需要前size_x/2个值即可*/ Wi.real=cos(2*PI/size_x*i); /计算W的实部 Wi.img=-1*sin(2*PI/size_x*i); /计算W的虚部 void change() /输入的码组码位倒置实现函数 complex temp; unsigned short i=0,j=0,k=0; double t; for(i=0;i<size_x;i+) k=i; j=0; t=(log(size_x)/log(2); while(t-)>0) j=j<<1; j|=(k &

11、1); k=k>>1; if(j>i) temp=xi; xi=xj; xj=temp; void output() /输出结果实现函数 int i; printf("The result are as followsn"); for(i=0;i<size_x;i+) printf("%.4f",xi.real); /输出实部 if(xi.img>=0.0001) /如果虚部的值大于0.0001，输出+jx.img的形式 printf("+j%.4fn",xi.img); else if(fabs(xi.

12、img)<0.0001) /如果虚部的绝对值小于0.0001，无需输出 printf("n"); else printf("-j%.4fn",fabs(xi.img); /如果虚部的值小于-0.0001，输出-jx.img的形式 void add(complex a,complex b,complex *c) /复数加法实现函数 c->real = a.real + b.real; /复数实部相加 c->img = a.img + b.img; /复数虚部相加 void mul(complex a,complex b,complex *

13、c) /复数乘法实现函数 c->real = a.real*b.real - a.img*b.img; /获取相乘结果的实部 c->img = a.real*b.img + a.img*b.real; /获取相乘结果的虚部 void sub(complex a,complex b,complex *c) /复数减法实现函数 c->real = a.real - b.real; /复数实部相减 c->img = a.img - b.img; /复数虚部相减 void divi(complex a,complex b,complex *c) /复数除法实现函数 c->

14、real=(a.real*b.real+a.img*b.img)/(b.real*b.real+b.img*b.img); /获取相除结果的实部 c->img = (a.img*b.real-a.real*b.img)/(b.real*b.real+b.img*b.img); /获取相除结果的虚部 4.2 运行结果 图3 运行结果图五算法分析及其优缺点5.1 算法分析（1）FFT算法的基本原理是把长序列的DFT逐次分解为较短序列的DFT。按照抽取方式的不同可分为DIT-FFT（按时间抽取）和DIF-FFT（按频率抽取）算法。按照蝶形运算的构成不同可分为基2、基4、基8以及任意因子（2n,

15、n为大于1的整数），基2、基4算法较为常用5。（2）总体结构说明，输入数据为串行的数据流，故在第一级蝶形运算模块前加入串并转换模块，将串行数据流转换为并行的两列数据流以适应基2蝶形运算模块的输入信号要求。 由于每级蝶形运算一次处理的两个输入数据不能直接由前一级蝶形运算一次性输出，故在两个蝶形运算单元之间插入延时对齐模块，将前一级蝶形运算的结果（两列并行的数据流）作适当的延时并通过转接器对齐，形成后一级蝶形运算模块所需要的2列输入序列6。 在最后一级蝶形运算后加入串并转换模块，将2列并行的数据流合成为1列。最后加入倒序模块将DIF-FFT得到的倒序输出序列整理为顺序输出。&#

16、160;基2蝶形运算模块由两个复数加法器和一个复数乘法器构成。旋转因子由ROM产生后，作为复数乘法器的输入之一，与前面复数加法器得到的结果相乘完成一次蝶形运算。为提高系统的运行速度可在蝶形运算单元中插入流水线寄存中间结果2。（3）蝶形运算单元如图所示： 图4 蝶式运算单元图5.2 优缺点优点：相对于DFT算法，FFT算法较高的效率，其基本思想是利用权函数的周期性、对称性、特殊性及周期的互换性，将点DFT运算逐次分解为较短序列的DFT运算。因DFT的运算量与序列长度的平方成比，故序列分解可大大减少运算量10。从FFT算法实现角度讲，应具有运算量较少、结构规整、易实现、可同址运算、内部数据不需重拍

17、等特点。缺点：由于定点乘法运算时间和占用资源都比定点加法都多得多，因此硬件实现定点FFT算法时，一般以乘法次数作为预算量的度量，对于浮点操作，因加法流水线比乘法流水线长，故不能忽略浮点加法运算时间而只根据浮点乘法运算次数推断计算时间10。六总结 这次课程设计是个难得的机会，可以让我们把所学的理论与实际相结合。通过这次比较完整的一个程序的设计，我走出了纯理论的学习，从一种全新的角度去学习。并且实现MPI运行过程中，除去知识的大量更新，我学到了很多东西。 其实个人而言，我体会较深的一点是团队互相帮助学习的过程，自己看书学习的经验，以及从网上或其他途径获得信息和知识的经验。理论与实际相结合的设计，锻

18、炼了我综合运用所学的基础知识，解决实际问题的能力，同时也提高我查阅文献资料、对程序整体的把握等其他能力水平。而且通过对整体的掌控，对局部的取舍，以及对细节的斟酌处理，都使我的能力得到了锻炼，我的各方面经验都得到了极大的丰富。 这次课程设计，感谢老师在这一周的教导，每天陪着我们，解答我们的疑难，也监督我们的学习。当然，同学们的帮助也是很重要的，我们互相讨论，虽然课题并不完全一样，可是解决方法却大同小异，各方面知识都要运用到，合作就显得至关重要。 总之，完成这次课程设计，我学到了很多。希望学校以后多开设些课程设计，多些机会来锻炼我们。七参考文献1 陈国良，并行计算结构·算法·编程（修订版）M, 北京: 高等教育出版社，2003.2 陈国良，并行算法的设计与分析M, 北京: 高等教育出版社，2002.3 陈国良，并行计算机体系结构M, 北京: