并行处理与体系结构试验指导书

1、Aaa4并行处理与体系结构实验指导书GuideBookofParallelProcessingandArchitectureExperiment编者：王瘠教务处2015年10月实验一MPI安装与程序编译、运行和调试1实验二共享存储模型与消息传递模型的比较3实验三矩阵运算5实验四八皇后问题10实验五快速排序12实验六快速傅氏变换14实验一MPI安装与程序编译、运行和调试一、实验目的搭建MPI并行编程环境，开发并行程序；学习并行程序的编写、编译、运行步骤，了解系统结构对编程模式和环境工具的影响。二、实验内容在计算机局域网上安装MPICH2虚拟机，用一个简单的计算实例进行测试。运行实验代码MPI运行

2、程序文件夹下面的hello.c、who.c、message.c>isend.c和mtpi.c程序实例，体会MPI中获取进程标识、消息传递及非阻塞通信等工作模式。三、实验步骤推荐的MPI使用环境是Linux，但实际应用中Windows系统应用广泛。本实验主要给出Windows下MPI环境的搭建方法及MPI程序的编写、编译连接及运行。大致步骤及说明如下：1 .创建用户以管理员的身份登录主机，在主机上建立一个MPI账户。如：用户名：mympi密码：mympi若在局域网环境下所有主机均推荐创建相同的MPI账户，且创建相同的工作目录，如D:mpijob,将并行编译成功的可执行文件均存放在同一目录下

3、。2 .安装MPICH例如：本实验采用的mpich2-1.4.1p1-win-ia32安装程序的下载地址为：/research/projects/mpich2downloads/tarballs/1.4.1p1/mpich2-1.4.1p1-win-ia32.msi推荐局域网中准备进行并行计算的所有计算机都要安装MPICH2虚拟机，且要安装在相同的路径下。本实验以设置安装在C:ProgramFilesMPICH2目录下为例。运行mpich2目录下的mpich2-1.4.1p1-win-ia32.msi,将MPICH2虚拟机安装到计算机上。(2)测试MP

4、I是否安装成功前首先需要注册一个用户，具体操作如下：“开始”按钮->所有程序->MPICH2->wmpiregister.exe。输入用户名、密码，即我们第一步建立的系统管理员账户和系统登录密码。如图1.1所示：图1.1MPICH用户注册界面(3)用例程测试。选择开始->所有程序->MPICH2->wmpiexec.exe;选才?Application为c:programfilesmpich2examplescpi.exe(就是自带的一个计算圆周率的例子程序)。可在Numberofprocesses的数量选择2表示用二个进程来协同完成。选中"run

5、inseparatewindow”选项，再点击Excute执行。如图1.2所示。E-1IMIPfEKECwrHpp«"r_,口图1.2测试例程cpi.exe然后在控制台窗口下提示输入numberofintervals,随便输入个大点的数字(50000,5000000)就可以看到求的的圆周率值。如图1.3所示。Enterthenumbei'ofintervals：<0quits)50603piisapproxinettely3.1415926536231167,Erroris0.0003000000333236allclocktine-0.0013770Ente

6、rthenumberofintervals：(0quits)5060000piisapproximately3.1415926535896412.Erropis0-0000000000001519vmIIclocktine=0.074561Enterthenumhei*ofintervals:(0quits)0请按任意键继续.图1.3cpi.exe执行结果显示3.在VC6.0中配置MPI(1)新建Win32ConsoleApplication工程(2)先在VC6.0中加入mpi的includeoVC6.0程序菜单中“工具”->“选择”->“目录”然后添加，如图1.4所示。加入lib

7、方法相同。图1.4在VC6.0中添加MPI的include(3)在所在工程一设置一link中，加入mpi.libcxx.lib。(4)加入讲过的helloworld程序，测试运行结果。注：这里以windows下MPI+VC实现为例进行的说明，同学可以根据自己的操作系统或开发语言自行选择版本下载安装。实验二共享存储模型与消息传递模型的比较一、实验目的比较共享存储模型与消息传递模型之间的区别。了解多线程并行和消息传递并行的工作机制。二、实验内容(1)统计10000个随机数中3出现的次数。OPENMP线程数可为1、2、4等。MPI程序进程数可为1、2、4等。(2)比较相同线程/进程数下，采用OPEN

8、MP和MPI实现N-BODY问题的性能。如：OPENMP线程数可为1、2、4等。MPI程序进程数可为1、2、4等。三、实验步骤(1)共享存储模型中，用openMP写一个程序，实现在一个长度为10,000的随机array里面，计算出3出现的次数，线程数为1,2或者4等。openMP可以拆分循环，比如2个线程，第一个线程负责array15000,第二个线程负责500110000,各循环5000次。这样两个线程可以同时遍历数组的两部分进行搜索计数。4个线程也类似，拆分成4部分同时进行。(OPENMP在VS2005以上支持，其他版本可查阅文献进行适当配置即可使用。)消息传递编程模型循环拆分的思量类似。

9、比如2个进程，第一个进程负责array15000,第二个线程负责500110000,各循环5000次。这样两个线程可以同时遍历数组的两部分进行搜索计数。4个线程也类似，拆分成4部分同时进行。最后结果可以返回0号进程。源代码清单：1 .共享存储模型计算随机数中3的个数(参考程序如下，可根据自己掌握的多线程知识自己编写新的OPM程序。)#include<stdio.h>#include<stdlib.h>#include<omp.h>#defineN10000intmain(intargc,char*argv)inti;intarrayN;intcount,nt

10、hreads,tid,chunk;unsignednum;chunk=100;count=0;doublestart,end;printf("pleasechoosenumberofthreads:1,2or4.n")scanf("%d",&num);提示输入计算线程数omp_set_num_threads(num);#pragmaompparallelshared(nthreads)tid=omp_get_thread_num();if(tid=0)(nthreads=omp_get_num_threads();printf("nSt

11、artingcountwith%dthreadsn",nthreads);)start=omp_get_wtime();#pragmaompparallelforreduction(+:count)schedule(static,chunk)for(i=0;i<N;i+)(arrayi=rand()%10;if(arrayi=3)count+;)end=omp_get_wtime();printf("Thecountcost%fsec.time.n",end-start);printf("Thenumberof3appearedinthearray

12、are%d",count);)消息传递编程模式统计随机数中3的个数采用消息传递机制，结果返回0号进程。可参考helloworld或课程第7章中计算兀值程序的例子自行编写程序。2 2)N-BODY问题分析OPENMP并行化N-BODY基本算法或简化算法分析MPI并行化N-BODY基本算法或简化算法比较这两种方法的性能。参考程序见“代码”文件夹。实验三矩阵运算一、实验目的矩阵运算是数值计算中最重要的一类运算，特别是在线性代数和数值分析中，它是一种最基本的运算。许多科学问题的基础都是矩阵。掌握在MPI虚拟机上进行矩阵运算求解算法及其程序设计、运行。二、实验内容求矩阵乘Cmxk=Amxn*B

13、Nk,以简单划分方法为例分析串并算法的性能。在单机或多机上，完成多个进程（如2、4、16等），两个方阵相乘运算（阶数可以自定如16X16、32X32128X128等），并比较运行时间，计算加速比。进一步了解棋盘划分方法进行矩阵运算的实例，以矩阵cannon相乘为例进行串并算法的分析和比较。三、实验步骤1、矩阵相乘及其串行算法矩阵是一些数的二维数组。一个mxn的矩阵有m行和n列元素，通常用二维数组来存储一个矩阵。一个mxn阶矩阵A=aj乘以一个nxk的矩阵B=bij就可以得到一个mxk的矩阵C=cij,它的元素Cj为A的第i行向量与B的第j列向量的内积。矩阵相乘的关键是相乘的两个元素的下标要满足

14、一定的要求（即对准）。为此常采用适当旋转矩阵元素的方法（如后面将要阐述的Cannon乘法）,或采用适当复制矩阵元素的办法，或采用流水线的办法使元素下标对准。由矩阵乘法定义容易给出其串行算法3.1,若一次乘法和加法运算时间为一个单位时间，则显然其时间复杂度为O（mnk）。算法3.1单处理器上矩阵相乘算法输入：AmXn,BnXk输出：CmXkBeginfori=0tom-1doforj=0tok-1doci,j=0forr=0ton-1doci,j=ci,j+ai,r*br,jendforendforendforEnd2.矩阵运算的并行算法矩阵的两种常见的划分方法，即行列划分（又称为带状划分）和棋

15、盘划分（又称为块状划分）。所谓带状划分（StripedPartitioning）就是将矩阵整行或整列地分成若干个组，每组指派给一个处理器。所谓棋盘划分（CheckerBoardPartitioning）就是将方阵划分成若干个子方阵，每个子方阵指派给一个处理器，此时任意处理器均不包含整行或整列。2.1 简单的矩阵并行分块乘法算法矩阵乘法可以用分块的思想实现并行，即分块矩阵乘法（BlockMatrixMultiplication）,将矩阵A按行划分为p块（p为处理器个数），设u=16/pl,每块含有连续的u行向量，这些行块依次记为Ao,Ai,Ap-1,分别存放在标号为0,1,p-1的处理器中。对矩

16、阵B按列划分为P块，记v=k/p,每块含有连续的v列向量，这些列块依次记为B0,Bl,Bp-1,分别存放在标号0,1,p-1为的处理器中。将结果矩阵C也相应地同时进行行、列划分，得到pxp个大小为uxv的子矩阵，记第i行第j列的子矩阵为Cij,显然有Cij=AiXBj,其中，Ai大小为uXn,Bj大小为nXv。处理器编号存储内容0A0B01AiBi2A2二B2,P-1a.p-1Bp-1(a)处理器编号存储内容0A0B11AiB22A2IB3,P-1a.p-1B0(b)图3.1矩阵相乘并行算法中的数据交换开始，各处理器的存储内容如图3.1(a)所示。此时各处理器并行计算CH=AKBj其中i=0,

17、1,p-1,此后第i号处理器将其所存储的B的列块送至第i-1号处理器(第0号处理器将B的列块送至第p-1号处理器中，形成循环传送)，各处理器中的存储内容如图3.1(b)所示。它们再次并行计算Cj=aixBj,这里j=(i+1)modp。B的列块在各处理器中以这样的方式循环传送p-1次并做p次子矩阵相乘运算，就生成了矩阵C的所有子矩阵。编号为i的处理器的内部存储器存有子矩阵Ci0,Ci1,-Ci(p-1)O为了避免在通信过程中发生死锁，奇数号及偶数号处理器的收发顺序被错开，使偶数号处理器先发送后接收；而奇数号处理器先将B的列块存于缓冲区buffer中，然后接收编号在其后面的处理器所发送的B的列块

18、，最后再将缓冲区中原矩阵B的列块发送给编号在其前面的处理器，具体并行算法框架描述如下：算法3.2矩阵并行分块乘法算法输入：Amixn,Bnxk,输出：CmxkBegin对所有处理器my_rank(my_rank=0,p-1)同时执行如下的算法：(1)目前计算C的子块号l=(i+my_rank)modp(2)forz=0tou-1doforj=0tov-1docl,z,j=0fors=0ton-1docl,z,j=cl,z,j+az,s*bs,jendforendforendfor(3)计算左邻处理器的标号mm1=(p+my_rank-1)modp计算右邻处理器的标号mp1=(my_rank+1

19、)modp(4) if(i半p-1)then(4.(1) if(my_rankmod2=0)then/*编号为偶数的处理器*/(i)将所存的B的子块发送到其左邻处理器中(ii)接收其右邻处理器中发来的B的子块endif(4.(2) if(my_rankmod2丰th)en/*编号为奇数的处理器*/(i)将所存的B子块在缓冲区buffer中做备份(ii)接收其右邻处理器中发来的B的子块(iii)将buffer中所存的B的子块发送到其左邻处理器中endifendifEnd设一次乘法和加法运算时间为一个单位时间，由于每个处理器计算p个uxn与nxv阶的子矩阵相乘，因此计算时间为u*v*n*p;所有处

20、理器交换数据p-1次，每次的通信量为v*n,通信过程中为了避免死锁，错开奇数号及偶数号处理器的收发顺序，通信时间为2(p-1)(ts+nv*tw)=O(nk),所以并行计算时间Tp=uvnp+2(p-1)(ts+nvtw)=mnk/p+2(p-1)(ts+nvtw)。2.2Cannon乘法2.2.1 Cannon乘法的原理Cannon算法是一种存储有效的算法。为了使两矩阵下标满足相乘的要求，它和上一节的并行分块乘法不同，不是仅仅让B矩阵的各列块循环移动，而是有目的地让A的各行块以及B的各列块皆施行循环移位，从而实现对C的子块的计算。将矩阵A和B分成p个方块Aj和Bij,(0<i,j<

21、;/_1),每块大小为-n/lx/l,并将它们分配给种黑种个处理器(P00,P01,，Pjp行)。开始时处理器Pj存放块Aj和Bj,并负责计算块Cj,然后算法开始执行：将块Aj向左循环移动i步；将块Bj向上循环移动j步；Pj执行乘加运算后将块Aj向左循环移动1步，块Bj向上循环移动1步；重复第步，总共执行寸增次乘加运算和J6次块Aj和Bj的循环单步移位。2.2.2 Cannon乘法的并行算法图3.2示例了在16个处理器上，用Cannon算法执行A4X4XB4X4的过程。其中(a)和(b)对应于上述算法的第步；(c)、(d)、(e)、(f)对应于上述算法的第和第步。在算法第步时，A矩阵的第0列不

22、移位，第1行循环左移1位，第2行循环左移2位，第3行循环左移3位；类似地，B矩阵的第0行不移位，第1列循环上移1位，第2列循环上移2歹U,第3列循环上移3歹U。这样Cannon算法具体描述如下：算法3.3Cannon乘法算法输入：AnXn,BnXn输出：CnxnBegin对所有处理器my_rank(my_rank=0,p-1)同时执行如下的算法：(1)计算子块的行号i=my_rank/sqrt(p)计算子块的歹U号j=my_rankmodsqrt(p)(2)fork=0to,p-1doif(i>k)thenLeftmoveonestep(a)endif/*a循环左移至同行相邻处理器中*/

23、if(j>k)thenUpmoveonestep(b)endif/*b循环上移至同列相邻处理器中*/endfor(3)fori=0tom-1doforj=0tom-1doci,j=0endforendfor(4)fork=0top-1dofori=0tom-1doforj=0tom-1dofork1=0tom-1doci,j=ci,j+ai,k1*bk1,jendforendforendforLeftmoveonestep(a)/*子块a循环左移至同行相邻的处理器中*/Upmoveonestep(b)/*子块b循环上移至同列相邻的处理器中*/endforEndA0,0A0,1A0,2A0

24、,3A1,0A1,1.A1,2.*A1,3,A2,0A2,12,2A2,3TA3,01-A3,1AA3,2A3,3B0,0B0,1AB0,2B0,3jLB1,0B1,1AB1,2A'B1,3B2,0B2,1BB212TB2,3B3,0BB311BB312BB3,3(a) A阵起始对准(b) B阵起始对准A0,0-jB0,0A0,1B1,1A0,2-.B2,2A0,3B3,34A1,1Ji,0A1,2<B2,1A1,3.B3,2A1,0-B0,3A2,2.B2,0A2,3.B3,1A2,0.B0,2A2,1.B1,34A3,3.B3,0A3,0.B0,1A3,1.B1211,2A3

25、,2.B2,3A0,1JB1,0A0,2-.B2,1A0,3-.B3,2A0,0dB0,3A1,24B2,0A1,3B3,1A1,0.B0,2A1,1/B1,3A2,3.产,0A2,0<B0,1A2,1.B1,2A2,2B2,3A3,0.B0,0A3,1.B1,1A3,2.B2,2A3,3BB3,3(c)对准后的A和B(d)第一次移位后的子阵位置A0,2A0,3A0,0A0,1/2,0B3,1上B0,2B1,3<4.A1,3tA1,0A1,1.A1,2.产,01rB0,1*B1,2*B2,3A2,0.A2,1A2,2.A2,3.0,04B1,1.B2,2-J3,3_A3,1.A3,

26、2A3,3.A3,0.B1,0BB2,1.B3,2*B0,3A0,3B3,0A0,0B0,1A0,1B1,2A0,2B2,3A1,0A1,1A1,2A1,3B0,0B1,1B2,2B3,3A2,1A2,2A2,3A2,0B1,0B2,1B3,2B0,3A3,2A3,3A3,0A3,1B2,0B3,1B0,2B1,3(e)第二次移位后的子阵位置(f)第三次移位后的子阵位置图3.216个处理器上的Cannon乘法过程这里函数Leftmoveonestep(a)表示子块a在编号处于同行的处理器之间以循环左移的方式移至相邻的处理器中；函数Upmoveonestep(b)表示子块b在编号处于同列的处理器

27、之间以循环上移的方式移至相邻的处理器中。这里我们以函数Leftmoveonestep(a)为例，给出处理器间交换数据的过程：算法3.4函数Leftmoveonestep(a)的基本算法Begin(1) if(j=0)then/*最左端的子块*/(1.(1) 存的A的子块发送到同行最右端子块所在的处理器中(1.(2) 其右邻处理器中发来的A的子块endif(2)if(j=sqrt(p)-1)and(jmod2=0)then/*最右端子块处理器且块列号为偶数*/(2.(1) 存的A的子块发送到其左邻处理器中(2.(2) 其同行最左端子块所在的处理器发来的A的子块endif(3)if(j=sqrt(

28、p)-1)and(jmod2网)then/*最右端子块处理器且块列号为奇数*/(3.(1) 存的A的子块在缓冲区buffer中做备份(3.(2) 其同行最左端子块所在的处理器发来的A的子块(3.(3) 缓冲区buffer中所存的A的子块发送到其左邻处理器中endif(3.(4) (j丰sqrt(p)-1)and(jmod2=0)and(jw0)then/*其余的偶数号处理器*/(4.(1) 存的A的子块发送到其左邻处理器中(4.(2) 其右邻处理器中发来的A的子块endif(3.(5) (jwsqrt(p)-1)and(jmod2=1)and(jw0)then/*其余的奇数号处理器*/(5.(

29、1) 存的A的子块在缓冲区buffer中做备份(5.(2) 其右邻处理器中发来的A的子块(5.(3) 缓冲区buffer中所存的A的子块发送到其左邻处理器中endifEnd当算法执行在布乂布的二维网孔上时，若使用切通CT选路法，算法18.7第(2)步的循环移位时间n2n2为2(ts卅w)/,第(4)步的单步移位时间为2(ts+tw)Jp、运算时间为n3/p。所以在一维网孔pp上Cannon乘法的并行运行时间为Tp=4(ts+tw吧)Jp+n3/poyp简单划分的矩阵相乘源代码和Cannon相乘源代码见附件。实验四八皇后问题一、实验目的(1)八皇后问题是计算机中经典智能搜索问题。掌握在MPI虚拟

30、机上进行八皇后问题求解算法及其程序设计、运行。(2)在分析八皇后的并行算法和MPI源程序基础上。查找相关参考资料，对于一般的n皇后问题，设计其并行算法及其程序，并运行结果。二、实验内容在单机或多机上完成8、12、16、32等n皇后问题求解，并比较运行时间，计算加速比。三、实验步骤1、了解八皇后问题及其串行算法所谓八皇后问题(EightQueensProblem),是在8*8格的棋盘上，放置8个皇后。要求每行每列放一个皇后，而且每一条对角线和每一条反对角线上最多只能有一个皇后，即对同时放置在棋盘的任意两个皇后(i1,1)和(i2,j2),不允许(i1-i2)=(j1-j2)或者(i1+%)=4+

31、j2)的情况出现。八皇后问题的串行解法为如下的递归算法。算法4.1八皇后问题的串行递归算法/*从chessboard的第row行开始放置皇后*/procedurePlaceQueens(chessboard,row)Beginifrow>8thenOutputResult(chessboard)/*结束递归并输出结果*/elseforcol=1to8do/*判断是否有列、对角线或反对角线冲突*/(1) no_collision=true(2) i=1(3) whileno_collisionandi<rowdo(3.(1) ifcollides(i,chessboardi,row,

32、col)thenno_collision=falseendif(3.(2) i=i+1endwhile(4) ifno_collisionthen(4.(1) chessboardrow=col/*在当前位置放置一个皇后*/(4.(2) go(step+1,place)/*递归地从下一行开始放置皇后*/endifendforendifEnd/*PlaceQueens*/2、八皇后问题的并行算法该算法是将八皇后所有可能的解置于相应的棋盘上，主进程负责生成初始化的棋盘，并将该棋盘发送到某个空闲的从进程，由该从进程求出该棋盘上满足初始化条件的所有的解。这里，我们假10定主进程只初始化棋盘的前两列，即

33、在棋盘的前两列分别放上2个皇后，这样就可以产生8*8=64个棋盘。算法4.2八皇后问题的并行算法(1)主进程算法procedureEightQueensMasterBegin(1) active_slaves=n(2) whileactive_slaves>0do(2.(1) 个从进程i接收信号signal(2.(2) ifsignal=Accomplishedthen从从进程i接收并记录解endif(2.(3) ifhas_more_boardsthen(i)向从进程i发送NewTask信号(ii)向从进程i发送一个新棋盘else(i)向从进程i发送Terminate信号(ii)act

34、ive_slaves=active_slaves-1endifendwhileEnd/*EightQueensMaster*/(2)从进程算法procedureEightQueenSlaveBegin(1)向主进程发送Ready信号(2) finished=false(3) whilenotfinisheddo(3.(1) 进程接收信号signal(3.(2) ifsignal=NewTaskthen(i)从主进程接收新棋盘(11) if新棋盘合法then在新棋盘的基础上找出所有合法的解，并将解发送给主进程endifelse/*signal=Terminate*/finished=trueen

35、difendwhileEnd/*日ghtQueenSlave*/八皇后问题源代码见附件。11实验五快速排序一、实验目的快速排序是计算机中常用的、典型非数值算法。熟悉并掌握在MPI虚拟机上进行快速排序的算法及其程序设计、运行。二、实验内容在单机或多机上完成快速排序，并比较运行时间，计算加速比，并与枚举排序对比分析结果。三、实验步骤1、了解快速排序及其串行算法快速排序(QuickSort)是一种最基本的排序算法，它的基本思想是：在当前无序区R1,n中取一个记录作为比较的“基准”(一般取第一个、最后一个或中间位置的元素)，用此基准将当前的无序区R1,n划分成左右两个无序的子区R1,i-1和Ri,n(

36、1<i<n),且左边的无序子区中记录的所有关键字均小于等于基准的关键字，右边的无序子区中记录的所有关键字均大于等于基准的关键字；当R1,i-1和Ri,n非空时，分别对它们重复上述的划分过程，直到所有的无序子区中的记录均排好序为止。算法5.1单处理机上快速排序算法输入：无序数组data1,n输出：有序数组data1,nBegincallprocedurequicksort(data,1,n)Endprocedurequicksort(data,i,j)Begin(1) if(i<j)then(1.(1) =partition(data,i,j)(1.(2) quicksort(

37、data,i,r-1);(1.(3) quicksort(data,r+1,j);endifEndprocedurepartition(data,k,l)Beginpivo=datal(2) i=k-1(3) forj=ktol-1doifdataj<pivotheni=i+1exchangedataianddatajendifendfor(4) exchangedatai+1anddatal(5) returni+1End12快速排序算法的性能主要决定于输入数组的划分是否均衡，而这与基准元素的选择密切相关。在最坏的情况下，划分的结果是一边有n-1个元素，而另一边有0个元素(除去被选中的

38、基准元素)如果每次递归排序中的划分都产生这种极度的不平衡，那么整个算法的复杂度将是©(n2)。在最好的情况下，每次划分都使得输入数组平均分为两半，那么算法的复杂度为O(nlogn)。在一般的情况下该算法仍能保持O(nlogn)的复杂度，只不过其具有更高的常数因子。2、快速排序的并行算法快速排序算法并行化的一个简单思想是，对每次划分过后所得到的两个序列分别使用两个处理器完成递归排序。例如对一个长为n的序列，首先划分得到两个长为n/2的序列，将其交给两个处理器分别处理；而后进一步划分得到四个长为n/4的序列，再分别交给四个处理器处理；如此递归下去最终得到排序好的序列。当然这里举的是理想的

39、划分情况，如果划分步骤不能达到平均分配的目的，那么排序的效率会相对较差。算法13.4中描述了使用2m个处理器完成对n个输入数据排序的并行算法。算法5.2快速排序并行算法输入：无序数组data1,n,使用的处理器个数2m输出：有序数组data1,nBeginpara_quicksort(data,1,n,m,0)Endprocedurepara_quicksort(data,i,j,m,id)Begin(1) if(j-i)<korm=0then(1.(1) Pidcallquicksort(data,i,j)else(1.(2) Pid:r=patrition(data,i,j)，.一_

40、-_m-1(1.(3) Pidsenddatar+1,m-1toPid+2(1.(4) para_quicksort(data,i,r-1,m-1,id)(1.(5) para_quicksort(data,r+1,j,m-1,id+2m-1)(1.(6) Pid+2m-1senddatar+1,m-1backtoPidendifEnd在最优的情况下该并行算法形成一个高度为logn的排序树，其计算复杂度为O(n),通信复杂度也为O(n)。同串行算法一样，在最坏情况下其计算复杂度降为O(n2)。正常情况下该算法的计算复杂度也为O(n),只不过具有更高的常数因子。快速排序问题源代码见附件13实验六

41、快速傅氏变换、实验目的长期以来，快速傅氏变换(FastFourierTransform,FFT)和离散小波变换(DiscreteWaveletTransform,DWT)在数字信号处理、石油勘探、地震预报、医学断层诊断、编码理论、量子物理及概率论等领域中都得到了广泛的应用。各种FFT和DWT算法不断出现，成为数值代数方面最活跃的一个研究领域，而其意义远远超过了算法研究的范围，进而为诸多科技领域的研究打开了一个崭新的局面。掌握在MPI虚拟机上进行快速傅氏变换求解算法及其程序设计、运行。二、实验内容在单机或多机上完成快速傅氏变换问题求解，并比较运行时间，计算加速比。三、实验步骤1、了解快速傅里叶变

42、换FFT离散傅里叶变换是20世纪60年代是计算复杂性研究的主要里程碑之一，1965年Cooley和Tukey所研究的计算离散傅里叶变换(DiscreteFourierTest)的快速傅氏变换(FFT)将计算量从0(n2)下降至Onlogn),推进了FFT更深层、更广法的研究与应用。FFT算法有很多版本，但大体上可分为两类：迭代法和递归法，本实验采用迭代法。b0,b1,bn-1为离散傅里叶变换的结2rWn=e-,实际上，上式可写成矩阵W和向假定a0,a1,an-1为一个有限长的输入序列,n1果序列，则有：bk=£akWnkm(kH,1,2，,n1),其中m卫量a的乘积形式：一-b01Iw0w0w0w0为1b1w0w1w2wn1a1b2aw0w2w4w2(n)amm+ma2b一w0w(n)w2(n)“w(n二)(n)an(公式6.1)般的n阶矩阵和n维向量相乘，计算时间复杂度为n2,但由于W是一种特殊矩阵，故可以降低计算量。FFT的计算流图如图6.1所示，其串行算法如下:算法6.1单处理器上的FFT迭代算法输入：a=(a0,a1,an-1)输出：b=(b0,b1,bn-1)Begin(1)fork=0ton-1dock=akendfor(2)forh=logn-1downto0doh(2.(1) p=2(2