并行计算

并行处理及体系结构实验报告

Parallel Computing and architecture Experiment Report

班级：计算机科学与技术25班 学号：S15081200029 姓名：陶双男 指导教师：王璿

信息学院 2015年 10 月

实验一 MPI安装与程序编译、运行和调试

一、实验题目 MPI安装与程序编译、运行和调试 二、实验目的

1、学会搭建MPI并行编程环境，能够开发运行并行程序。

2、学习并行程序的编写、编译、运行步骤，了解系统结构对编程模式和环境工具的影响。 三、实验内容

1、搭建MPI并行编程环境（Windows下MPI环境的搭建）

1)首先以管理员的身份登录主机，在主机上建立一个MPI账户。用户名：mympi，密码：mympi。然后安装MPICH2，运行mpich2-1.4.1p1-win-ia32，将MPICH2虚拟机安装到计算机上并测试MPI是否安装成功前首先需要注册一个用户，具体操作如下：“开始”按钮-->所有程序-->MPICH2 -->wmpiregister.exe。输入用户名、密码，即我们第一步建立的系统管理员账户和系统登录密码。如图1.1所示：

图1.1

1

安装完成之后可以用程序自带的examples下的cpi.exe进行测试，选择开始-->所有程序-->MPICH2-->wmpiexec.exe，可在Number of processes的数量选择2表示用两个进程来协同完成。选中“run in separate window”选项，再点击Excute执行。如图1.2所示，运行结果如图1.3所示：

图1.2

图1.3 cpi.exe运行结果

2)在VC6.0中配置MPI，建立一个Win32 Console Application工程，先在VC6.0中加入mpi的include。VC6.0程序菜单中“工具” -->“选择”-->“目录”，如图1.4所示，然后再添加lib如图1.5所示：

2

图1.4 include files添加

图1.5 Library files添加

在所在工程—设置—连接中，加入mpi.lib cxx.lib。如图1.6所示：

图1.6 加入mpi.lib和cxx.lib

3)对hello程序进行测试，选择4个进程来协同完成，结果如图1.7所示：

3

图1.7 hello运行结果

对isend程序进行测试，选择2个进程协同完成，运行结果如图1.8所示：

图1.8 isend程序运行结果

根据图1.8可以看到flag的两个值是一样的，都等于1，原因是在还没有执行MPI_Wait(&r,&status)函数的时候进程间通信已经完成。 对message程序进行测试，选择4个进程协同完成，运行结果如图1.9所示：

图1.9 message运行结果

4

对mtpi程序进行测试，选择3个进程协同完成，运行结果如图1.10所示：

图1.10 mtpi运行结果

对who程序进行测试，选择5个进程协同完成，运行结果如图1.11所示：

图1.11 who运行结果

四、非阻塞消息传递机制与阻塞消息传递机制的区别

阻塞的消息传递主要包括阻塞发送和阻塞接收。阻塞发送是指发送方只有在消息已经发送出去之后才能返回，这就意味着发送返回时，消息缓冲区已经可以安全地进行写操作，而不改变程序语义。阻塞接收是指接收方一直阻塞到消息已经被确认地接收到为止，这也意味着接收返回时，消息缓冲区已经可以安全地进行读操作，而不改变程序语义。

非阻塞的消息传递包括非阻塞发送和非阻塞接收。非阻塞发送是指发送原语在通知系统将要发送存储区内的消息后即返回，而系统在晚些时候才从消息缓冲区中取走消息发出，所以，若之后的语句有对消息缓冲区的写操作，则在语义上是不安全的。非阻塞接收是指接收原语在通知系统将要消息并将其存储于消息缓冲区内即返回，而此时消息可能早已到达，也可能正在途中，甚至可能相应的发送尚未开始，所以若接收原语之后的语句有对消息缓冲区的读操作，则可能导致语义错误。

所以，阻塞和非阻塞通信的主要区别在于返回后的资源可用性。阻塞

5

通信返回的条件：通信操作已经完成，即消息已经发送或接收；调用的缓冲区可用。若是发送操作，则该缓冲区可以被其它的操作更新；若是接收操作，该缓冲区的数据已经完整，可以被正确引用。而非阻塞通信返回后并不意味着通信操作的完成。

6

实验二 共享存储模型与消息传递模型的比较

一、实验题目 共享存储模型与消息传递模型的比较 二、实验目的

1、比较共享存储模型与消息传递模型之间的区别。 2、了解多线程并行和消息传递并行的工作机制。 三、实验内容

1)统计10000个随机数中3出现的次数。

OPENMP（共享存储模型）程序如下：

#include #include #include #define N 10000

int main(int argc, char *argv[]) { int i;

int array[N];

int count, nthreads, tid, chunk; unsigned num; chunk = 100; count = 0;

double start, end;

printf(\scanf(\ //提示输入计算线程数 omp_set_num_threads(num);

#pragma omp parallel shared(nthreads) { tid=omp_get_thread_num();

if(tid==0) {

nthreads=omp_get_num_threads();

printf(\

7

} }

start = omp_get_wtime();

#pragma omp parallel for reduction(+:count) schedule(static,chunk)

for( i=0; i

array[i] = rand()% 10 ; if(array[i]==3) count++ ; }

end =omp_get_wtime();

printf(\

printf(\}

选择一个进程的运行结果如图2.1所示：

图2.1 一个进程的OPENMP程序运行结果

选择两个进程的运行结果如图2.2所示：

图2.2 两个进程的OPENMP程序运行结果

8

选择四个进程的运行结果如图2.3所示：

图2.3 四个进程的OPENMP程序运行结果

MPI（消息传递模型）程序如下：

#include #include

#define MPICH_SKIP_MPICXX #include #define N 10000

int main(int argc,char **argv) { int i; int init;

int array[N];

int count, tid, numtask,flag;

count = 0;

double start, end;

MPI_Init( &argc, &argv );

MPI_Comm_rank(MPI_COMM_WORLD,&tid); //tid=omp_get_thread_num();当前线程ID

MPI_Comm_size(MPI_COMM_WORLD,&numtask); //线程总数

9

start = MPI_Wtime();

//#pragma omp parallel for reduction(+:count) schedule(static,chunk)

for( i=tid; i

array[i] = rand()% 10 ; if(array[i]==3) count++ ; }

end =MPI_Wtime();

printf(\

MPI_Reduce (&count,&init,1,MPI_INT,MPI_SUM,0,MPI_COMM_WORLD);//归约

MPI_Finalize ();

if(tid==0) { printf(\} }

选择一个进程的运行结果如图2.4所示：

图2.4 一个进程的MPI程序运行结果

选择两个进程的运行结果如图2.5所示：

图2.5 两个进程的MPI程序运行结果

10

选择四个进程的运行结果如图2.6所示：

图2.6 四个进程的MPI程序运行结果

2)比较相同线程/进程数下，采用OPENMP和MPI实现N-BODY问题的性能。

选择一个进程的OPENMP运行结果如图2.7所示：

图2.7 一个进程的OPENMP程序运行结果

选择两个进程的OPENMP运行结果如图2.8所示：

图2.8 两个进程的OPENMP程序运行结果

选择四个进程的OPENMP运行结果如图2.9所示：

11

图2.9 四个进程的OPENMP程序运行结果

选择一个进程的MPI运行结果如图2.10所示：

图2.10 一个进程的MPI程序运行结果

选择两个进程的MPI运行结果如图2.11所示：

12

图2.11 两个进程的MPI程序运行结果

选择四个进程的MPI运行结果如图2.12所示：

图2.12 四个进程的MPI程序运行结果

四、共享存储编程模型和消息传递编程模型的区别

共享存储器编程的主要特征是共享存储器提供了创建出能够直接被所有的处理器访问的而不用消息传递环境中那样用消息来传递数据的变量和数据结构。在共享存储编程模型中，所有节点共享存储空间，适于PVP,SMP,DSM。编程工具代表OPENMP。

消息传递模型的编程级别相对较低，但可以有更广泛的应用范围。在消息传递模型中，每个并行实体均有自己独立的地址空间，一个并行实体不能直接访问领一个并行实体的数据，这种远程访问必须通过显示的消息传递来实现。所以，驻留在不同节点上的进程可以通过网络显式地传递消息相互通信，实现进程之间的信息交换、协调步伐、控制执行等。消息传递的特点是多线程、异步并行性、分开的地址空间、显式相互作用、显式数据映射和负载分配等。消息传递一般是面向分布式内存的，但是它也可适用于共享内存的并行机。消息传递为编程者提供了更灵活的控制手段和表达并行的方法，一些用数据并行方法很难表达的并行算法都可以用消息

13

传递模型来实现。灵活性和控制手段的多样化是消息传递并行程序能提供高的执行效率的重要原因。编程工具代表MPI。

消息传递模型一方面为编程者提供了灵活性，另一方面，它也将各个并行执行部分之间复杂的信息交换和协调 控制的任务交给了编程者，这在一定程度上增加了编程者的负担。这也是消息传递编程模型编程级别低的主要原因。虽然如此，消息传递的基本通信模式是简单和清楚的，学习和掌握这些部分并不困难，因此目前大量的并行程序设计仍然是消息传递并行编程模式。共享存储程序设计比消息传递程序设计更加容易，因为进程间的数据交换可利用共享存储器来实现。但共享存储程序设计需要设计都使用特殊的机制（如临界段等）来协调各个进程对数据的访问。

14

实验三 快速排序

一、实验题目 快速排序

二、实验目的 快速排序是计算机中常用的、典型非数值算法。熟悉并掌握在MPI虚拟机上进行快速排序的算法及其程序设计、运行。 三、实验内容

在单机或多机上完成快速排序，并比较运行时间，计算加速比，并与枚举排序对比分析结果。

1) 采用快速排序法，当线程数为1、2、4时的运行结果。

线程数为1时，对5000个数字进行快速排序，程序运行结果及所用时间如图3.1所示：

图3.1 线程数为1程序运行结果

线程数为2时，对5000个数字进行快速排序，程序运行结果及所用时间如图3.2所示：

15

图3.2 线程为2时程序运行结果

线程数为4时，对5000个数字进行快速排序，程序运行结果及所用时间如图3.3所示：

图3.3 线程为4时程序运行结果

16

2）采用枚举排序法，当线程数为1、2、4时的运行结果。

线程数为1时，对5000个数字进行枚举排序，程序运行结果及所用时间如图3.4所示：

图3.4 线程为1时程序运行结果

线程数为2时，对5000个数字进行枚举排序，程序运行结果及所用时间如图3.5所示：

图3.5 线程为2时程序运行结果

17

线程数为4时，对5000个数字进行枚举排序，程序运行结果及所用时间如图3.6所示：

图3.6 线程为4时程序运行结果

四、实验结果分析 1）快速排序并行算法

输入：无序数组data[1,n]，使用的处理器个数2m 输出：有序数组data[1,n] Begin para_quicksort(data,1,n,m,0) End

procedure para_quicksort(data,i,j,m,id) Begin

(1) if (j-i)≤k or m=0 then (1.1) Pid call quicksort(data,i,j)

else

(1.2) Pid: r=patrition(data,i,j)

(1.3) P id send data[r+1,m-1] to Pid+2m-1 (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-1 send data[r+1,m-1] back to Pid end if End

18

2）单处理机上快速排序算法

输入：无序数组data[1,n] 输出：有序数组data[1,n] Begin call procedure quicksort(data,1,n) End

procedure quicksort(data,i,j) Begin

(1) if (i

(1.1)r = partition(data,i,j)

(1.2)quicksort(data,i,r-1); (1.3)quicksort(data,r+1,j);

end if End

procedure partition(data,k,l) Begin

(1) pivo=data[l] (2) i=k-1

(3) for j=k to l-1 do

if data[j]≤pivo then

i=i+1

exchange data[i] and data[j] end if end for

(4) exchange data[i+1] and data[l] (5) return i+1 End

3）对由图3.1及图3.2排序所用时间对比知：在一定条件下，增加进程（或处理器）的数目能加快问题的求解速度。由图3.2及图3.3所用时间对比知，用消息传递模型所设计的并行程序，由于各通信带来的开销，问题的解决速度随着进程（或处理器）数目的增多反而下降，故并行程序在解决较大规模的问题时会有更显著的效果。 4）加速比：R1=T1/T2=1.02611 R2=T1/T3=0.09433

19

本文来源：https://www.bwwdw.com/article/f4sr.html