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

并行处理与体系结构实验指导书GuideBookofParallelProcessingandArchitectureExperiment编者：王璿教务处2015年10月目录实验一MPI安装与程序编译、运行和调试..............................................................................................1实验二共享存储模型与消息传递模型的比较...........................................................................................3实验三矩阵运算.........................................................................................................................................5实验四八皇后问题...................................................................................................................................10实验五快速排序.......................................................................................................................................12实验六快速傅氏变换.................................................................................................................................141实验一MPI安装与程序编译、运行和调试一、实验目的搭建MPI并行编程环境，开发并行程序；学习并行程序的编写、编译、运行步骤，了解系统结构对编程模式和环境工具的影响。二、实验内容在计算机局域网上安装MPICH2虚拟机，用一个简单的计算实例进行测试。运行\实验代码\MPI运行程序\文件夹下面的hello.c、who.c、message.c、isend.c和mtpi.c程序实例，体会MPI中获取进程标识、消息传递及非阻塞通信等工作模式。三、实验步骤推荐的MPI使用环境是Linux，但实际应用中Windows系统应用广泛。本实验主要给出Windows下MPI环境的搭建方法及MPI程序的编写、编译连接及运行。大致步骤及说明如下：1.创建用户以管理员的身份登录主机，在主机上建立一个MPI账户。如：用户名：mympi密码：mympi若在局域网环境下所有主机均推荐创建相同的MPI账户，且创建相同的工作目录，如D:\mpijob，将并行编译成功的可执行文件均存放在同一目录下。2.安装MPICH例如：本实验采用的mpich2-1.4.1p1-win-ia32安装程序的下载地址为：推荐局域网中准备进行并行计算的所有计算机都要安装MPICH2虚拟机，且要安装在相同的路径下。本实验以设置安装在C:\ProgramFiles\MPICH2目录下为例。(1)运行mpich2目录下的mpich2-1.4.1p1-win-ia32.msi，将MPICH2虚拟机安装到计算机上。(2)测试MPI是否安装成功前首先需要注册一个用户，具体操作如下：“开始”按钮--所有程序--MPICH2--wmpiregister.exe。输入用户名、密码，即我们第一步建立的系统管理员账户和系统登录密码。如图1.1所示：图1.1MPICH用户注册界面(3)用例程测试。选择开始--所有程序--MPICH2--wmpiexec.exe；选择Application为c:\programfiles\mpich2\examples\cpi.exe(就是自带的一个计算圆周率的例子程序)。可在Numberofprocesses的数量选择2表示用二个进程来协同完成。选中“runinseparatewindow”选项，再点击Excute执行。如图1.2所示。2图1.2测试例程cpi.exe然后在控制台窗口下提示输入numberofintervals，随便输入个大点的数字（50000，5000000）就可以看到求的的圆周率值。如图1.3所示。图1.3cpi.exe执行结果显示3.在VC6.0中配置MPI(1)新建Win32ConsoleApplication工程(2)先在VC6.0中加入mpi的include。VC6.0程序菜单中“工具”--“选择”--“目录”然后添加，如图1.4所示。加入lib方法相同。图1.4在VC6.0中添加MPI的include(3)在所在工程—设置—link中，加入mpi.libcxx.lib。(4)加入讲过的helloworld程序，测试运行结果。注：这里以windows下MPI+VC实现为例进行的说明，同学可以根据自己的操作系统或开发语言自行选择版本下载安装。3实验二共享存储模型与消息传递模型的比较一、实验目的比较共享存储模型与消息传递模型之间的区别。了解多线程并行和消息传递并行的工作机制。二、实验内容（1）统计10000个随机数中3出现的次数。OPENMP线程数可为1、2、4等。MPI程序进程数可为1、2、4等。（2）比较相同线程/进程数下，采用OPENMP和MPI实现N-BODY问题的性能。如：OPENMP线程数可为1、2、4等。MPI程序进程数可为1、2、4等。三、实验步骤（1）共享存储模型中，用openMP写一个程序，实现在一个长度为10，000的随机array里面，计算出3出现的次数，线程数为1，2或者4等。openMP可以拆分循环，比如2个线程，第一个线程负责array1~5000，第二个线程负责5001~10000，各循环5000次。这样两个线程可以同时遍历数组的两部分进行搜索计数。4个线程也类似，拆分成4部分同时进行。（OPENMP在VS2005以上支持，其他版本可查阅文献进行适当配置即可使用。）消息传递编程模型循环拆分的思量类似。比如2个进程，第一个进程负责array1~5000，第二个线程负责5001~10000，各循环5000次。这样两个线程可以同时遍历数组的两部分进行搜索计数。4个线程也类似，拆分成4部分同时进行。最后结果可以返回0号进程。源代码清单：1．共享存储模型计算随机数中3的个数（参考程序如下，可根据自己掌握的多线程知识自己编写新的OPM程序。）#includestdio.h#includestdlib.h#includeomp.h#defineN10000intmain(intargc,char*argv[]){inti;intarray[N];intcount,nthreads,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)4{nthreads=omp_get_num_threads();printf(\nStartingcountwith%dthreads\n,nthreads);}}start=omp_get_wtime();#pragmaompparallelforreduction(+:count)schedule(static,chunk)for(i=0;iN;i++){array[i]=rand()%10;if(array[i]==3)count++;}end=omp_get_wtime();printf(Thecountcost%fsec.time.\n,end-start);printf(Thenumberof3appearedinthearrayare%d,count);}消息传递编程模式统计随机数中3的个数采用消息传递机制，结果返回0号进程。可参考helloworld或课程第7章中计算π值程序的例子自行编写程序。(2)N-BODY问题分析OPENMP并行化N-BODY基本算法或简化算法分析MPI并行化N-BODY基本算法或简化算法比较这两种方法的性能。参考程序见“代码”文件夹。5实验三矩阵运算一、实验目的矩阵运算是数值计算中最重要的一类运算，特别是在线性代数和数值分析中，它是一种最基本的运算。许多科学问题的基础都是矩阵。掌握在MPI虚拟机上进行矩阵运算求解算法及其程序设计、运行。二、实验内容求矩阵乘Cm×k=Am×n*Bn×k，以简单划分方法为例分析串并算法的性能。在单机或多机上，完成多个进程（如2、4、16等），两个方阵相乘运算（阶数可以自定如16×16、32×32128×128等），并比较运行时间，计算加速比。进一步了解棋盘划分方法进行矩阵运算的实例，以矩阵cannon相乘为例进行串并算法的分析和比较。三、实验步骤1、矩阵相乘及其串行算法矩阵是一些数的二维数组。一个m×n的矩阵有m行和n列元素，通常用二维数组来存储一个矩阵。一个m×n阶矩阵A=[aij]乘以一个n×k的矩阵B=[bij]就可以得到一个m×k的矩阵C=[cij]，它的元素cij为A的第i行向量与B的第j列向量的内积。矩阵相乘的关键是相乘的两个元素的下标要满足一定的要求(即对准)。为此常采用适当旋转矩阵元素的方法(如后面将要阐述的Cannon乘法)，或采用适当复制矩阵元素的办法，或采用流水线的办法使元素下标对准。由矩阵乘法定义容易给出其串行算法3.1，若一次乘法和加法运算时间为一个单位时间，则显然其时间复杂度为O(mnk)。算法3.1单处理器上矩阵相乘算法输入：Am×n，Bn×k输出：Cm×kBeginfori=0tom-1doforj=0tok-1doc[i,j]=0forr=0ton-1doc[i,j]=c[i,j]+a[i,r]*b[r,j]endforendforendforEnd2.矩阵运算的并行算法矩阵的两种常见的划分方法，即行列划分（又称为带状划分）和棋盘划分（又称为块状划分）。所谓带状划分（StripedPartitioning）就是将矩阵整行或整列地分成若干个组，每组指派给一个处理器。所谓棋盘划分（CheckerBoardPartitioning）就是将方阵划分成若干个子方阵，每个子方阵指派给一个处理器，此时任意处理器均不包含整行或整列。2.1简单的矩阵并行分块乘法算法矩阵乘法可以用分块的思想实现并行，即分块矩阵乘法(BlockMatrixMultiplication)，将矩阵A按行划分为p块(p为处理器个数)，设pmu/，每块含有连续的u行向量，这些行块依次记为A0,A1,…,Ap-1，分别存放在标号为0,1,…,p-1的处理器中。对矩阵B按列划分为P块，记pkv/，6每块含有连续的v列向量，这些列块依次记为B0,B1,…,Bp-1，分别存放在标号0,1,…,p-1为的处理器中。将结果矩阵C也相应地同时进行行、列划分，得到p×p个大小为u×v的子矩阵，记第i行第j列的子矩阵为Cij，显然有Cij=Ai×Bj，其中，Ai大小为u×n，Bj大小为n×v。A0