Cannon乘法的MPI实现解析Word格式.docx
《Cannon乘法的MPI实现解析Word格式.docx》由会员分享，可在线阅读，更多相关《Cannon乘法的MPI实现解析Word格式.docx（27页珍藏版）》请在冰点文库上搜索。
编写Cannon乘法的MPI程序
7
LU分解的MPI实现
编写LU分解的MPI程序
8
随机串匹配算法的MPI实现
编写随机串匹配算法的MPI程序
9
单源最短路径Dijkstra算法的MPI实现
编写单源最短路径Dijkstra算法的MPI程序
10
快速排序算法的MPI实现
编写快速排序算法的MPI程序
11
KMP串匹配的MPI实现
编写KMP串匹配算法的MPI程序
Cannon乘法的MPI实现及性能分析
摘要：
cannon算法是矩阵的并行乘法，属于数值并行算法MPI编程实现一篇，其中关于数值并行算法MPI编程由于要处理的数据量巨大，程序循环次数多，对于串行而言，处理时间将非常长，将其并行化非常必要。
本文将矩阵数据进行棋盘划分成多个子矩阵，再分别指派给多个处理器，使个处理器并行运算。
关键字：
cannon乘法并行计算数据划分
一、Cannon乘法的MPI实现基本原理
Cannon乘法属于数值并行算法MPI编程实现一篇，其中关于数值并行算法MPI编程由于要处理的数据量巨大，程序循环次数多，对于串行而言，处理时间将非常长，使其并行化的一般方法有：
1）数据相关分析2）数据划分和处理器指派3）循环重构
对原有程序并行化，首先要分析计算程序中所有语句间的依赖关系，这称之为相关分析。
本项目Cannon乘法的mpi实现，是矩阵运算，阶往往都很高，而且行列之间数据依赖关系也不强，所以就对矩阵进行划分，然后指派给不同的处理器进行处理。
最常用的矩阵划分有带状划分和块状划分。
1．带状划分方法
带状划分又叫行列划分，就是将矩阵整行或整列地分成若干组，各组指派给一个处理器。
也可以将若干行或列指派给一个处理器，而且这些行和列可以是连续的，也可以是等间距的，前者称为块带状的，后者称为循环带状的。
2.块状划分方法
块状划分又叫棋盘划分，就是将矩阵划分成若干个子矩阵，每个子矩阵指派给一个处理器，此时任意处理器均不含整行或整列。
和带状划分类似，棋盘划分也可分为块棋盘划分和循环棋盘划分。
棋盘划分比带状划分可开发更高的并行度，Cannon乘法的mpi实现也正是基于棋盘划分的并行实现。
循环重构是指在数据分解之后，相应地将串行程序循环部分进行重构，以实现这种划分所确定的并行计算，主要方法有1）循环交换2）拉伸法3）分裂法4）轮转法5）并列法在三种程序并行化的方法中，数据相关分析和循环重构目的都是挖掘语句间的并行性，而数据划分和处理器指派则重在策略，宏观上挖掘并行性。
Cannon算法是一种存储有效的算法，设矩阵
和
相乘。
为了使两矩阵下标满足相乘的要求，和带状的并行分块乘法不同，不是仅仅让B矩阵的各列块循环移动，而是有目的地让A的各行块以及B的各列块皆施行循环移位，从而实现对C的子块的计算。
将矩阵A和B分成p个方块Aij和Bij，
，每块大小为
，并将它们分配给
个处理器
。
开始时处理器Pij存放块Aij和Bij，并负责计算块Cij，然后算法开始执行：
⑴将块Aij向左循环移动i步；
将块Bij向上循环移动j步；
⑵Pij执行乘加运算后将块Aij向左循环移动1步，块Bij向上循环移动1步；
⑶重复第⑵步，总共执行
次乘加运算和
次块Aij和Bij的循环单步移位。
二、Cannon乘法的MPI实现内容和步骤
实验涉及内容主要有：
1）数据划分和指派处理器
最常用的矩阵数据划分有带状划分和块状划分。
设有P个处理器，将矩阵A和B分成p个方块Aij和Bij，
2）子矩阵的循环移动
处理器Pij存放块Aij和Bij，并负责计算块Cij，在使A矩阵的左右循环移动和B矩阵的上下循环移动时，为了避免在通信过程中发生死锁，奇数号及偶数号处理器的收发顺序被错开，使偶数号处理器先发送后接收；
而奇数号处理器先将子矩阵块存于缓冲区Buffer中，然后接收编号在其后面的处理器所发送的子矩阵块，最后再将缓冲区中子矩阵块发送给编号在其前面的处理器。
基本算法如下：
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的子块
（3）if（（j=sqrt（p）-1）and（jmod2≠0））then/*最右端子块处理器且块列号为奇数*/
（3.1）将所存的A的子块在缓冲区buffer中做备份
（3.2）接收其同行最左端子块所在的处理器发来的A的子块
（3.3）将在缓冲区buffer中所存的A的子块发送到其左邻处理器中
（4）if（（j≠sqrt（p）-1）and（jmod2=0）and（j≠0））then/*其余的偶数号处理器*/
（4.1）将所存的A的子块发送到其左邻处理器中
（4.2）接收其右邻处理器中发来的A的子块
（5）if（（j≠sqrt（p）-1）and（jmod2=1）and（j≠0））then/*其余的奇数号处理器*/
（5.1）将所存的A的子块在缓冲区buffer中做备份
（5.2）接收其右邻处理器中发来的A的子块
（5.3）将在缓冲区buffer中所存的A的子块发送到其左邻处理器中
End
实验步骤
1）登陆KD-60
图2.1KD-60登陆界面
2）转至node80节点，上传程序
输入命令：
sshloongson@node80和密码进入图界面
图2.2转到节点80的界面
再命令vim，进入vim编辑器加入程序,保存为cannon.c
3）编译程序
mpicccannon.c–ocannon–lm
在目录中查看，已成功。
如下图
图2.3将程序保存并编译后界面
4）运行程序
输入：
mpirun–np4cannon4,其中第一个4是指定的处理器个数，第二个4是产生随机矩阵的维数，这两个参数在实验过程中可以调整，但要求第一个参数即处理器的个数必须是一个数的平方数。
输出：
图2.4cannon乘法运行结果
图2.4并行程序运行界面两个参数都是4，分别输出两个随机矩阵和矩阵的乘积
三、数据及结果
1.下面列出了两组数据，分别是用一个处理器进行串行运算和四个处理器进行并行运算矩阵维数为200的计算时间比较。
四个处理器处理阶数为200的矩阵相乘时，所花时间为：
1.705844秒。
单个处理器处理阶数为200的矩阵相乘时，所花时间为：
3.727210秒。
如图3.1和图3.2所示。
图3.1四个处理器并行执行结果图
图3.2单个处理器串行执行结果图
附：
1.程序模块伪代码：
An×
n，Bn×
n
Cn×
对所有处理器my_rank（my_rank=0,…,p-1）同时执行如下的算法:
（1）计算子块的行号i=my_rank/sqrt（p）
计算子块的列号j=my_rankmodsqrt（p）
（2）fork=0to
-1do
if（i>
k）thenLeftmoveonestep（a）endif/*a循环左移至同行相邻处理器中*/
if（j>
k）thenUpmoveonestep（b）endif/*b循环上移至同列相邻处理器中*/
endfor
（3）fori=0tom-1do
forj=0tom-1do
c[i,j]=0
endfor
（4）fork=0to
fori=0tom-1do
fork1=0tom-1do
c[i,j]=c[i,j]+a[i,k1]*b[k1,j]
Leftmoveonestep（a）/*子块a循环左移至同行相邻的处理器中*/
Upmoveonestep（b）/*子块b循环上移至同列相邻的处理器中*/
Leftmoveonestep（a）见实验内容处
附2.程序源码
#include<
stdlib.h>
string.h>
mpi.h>
time.h>
stdio.h>
math.h>
/*全局变量声明*/
float**A,**B,**C;
/*总矩阵,C=A*B*/
float*a,*b,*c,*tmp_a,*tmp_b;
/*a、b、c表分块，tmp_a、tmp_b表缓冲区*/
intdg,dl,dl2,p,sp;
/*dg:
总矩阵维数;
dl:
矩阵块维数;
dl2=dl*dl;
p:
处理器个数;
sp＝sqrt（p）*/
intmy_rank,my_row,my_col;
/*my_rank:
处理器ID;
（my_row,my_col）:
处理器逻辑阵列坐标*/
MPI_Statusstatus;
floatstarttime;
floattime1;
/*
*函数名:
get_index
*功能：
处理器逻辑阵列坐标至rank号的转换
*输入：
坐标、逻辑阵列维数
*输出：
rank号
*/
intget_index（introw,intcol,intsp）
{
return（（row+sp）%sp）*sp+（col+sp）%sp;
}
*函数名：
random_A_B
随机生成矩阵A和B
voidrandom_A_B（）
inti,j;
srand（（unsignedint）time（NULL））;
/*设随机数种子*/
/*随机生成A,B,并初始化C*/
for（i=0;
i<
dg;
i++）
for（j=0;
j<
j++）
{
A[i][j]=rand（）;
B[i][j]=rand（）;
C[i][j]=0.0;
}
/*函数名：
scatter_A_B
*功能：
rank为0的处理器向其他处理器发送A、B矩阵的相关块
voidscatter_A_B（）
inti,j,k,l;
intp_imin,p_imax,p_jmin,p_jmax;
for（k=0;
k<
p;
k++）
/*计算相应处理器所分得的矩阵块在总矩阵中的坐标范围*/
p_jmin=（k%sp）*dl;
p_jmax=（k%sp+1）*dl-1;
p_imin=（k-（k%sp））/sp*dl;
p_imax=（（k-（k%sp））/sp+1）*dl-1;
l=0;
/*rank=0的处理器将A,B中的相应块拷至tmp_a,tmp_b，准备向其他处理器发送*/
for（i=p_imin;
=p_imax;
for（j=p_jmin;
=p_jmax;
{
tmp_a[l]=A[i][j];
tmp_b[l]=B[i][j];
l++;
/*rank=0的处理器直接将自己对应的矩阵块从tmp_a,tmp_b拷至a,b*/
if（k==0）
memcpy（a,tmp_a,dl2*sizeof（float））;
memcpy（b,tmp_b,dl2*sizeof（float））;
}else/*rank=0的处理器向其他处理器发送tmp_a,tmp_b中相关的矩阵块*/
MPI_Send（tmp_a,dl2,MPI_FLOAT,k,1,MPI_COMM_WORLD）;
MPI_Send（tmp_b,dl2,MPI_FLOAT,k,2,MPI_COMM_WORLD）;
init_alignment
*功能:
矩阵A和B初始对准
voidinit_alignment（）
/*将A中坐标为（i,j）的分块A（i,j）向左循环移动i步*/
MPI_Sendrecv（a,dl2,MPI_FLOAT,get_index（my_row,my_col-my_row,sp）,1,
tmp_a,dl2,MPI_FLOAT,get_index（my_row,my_col+my_row,sp）,1,MPI_COMM_WORLD,&
status）;
memcpy（a,tmp_a,dl2*sizeof（float））;
/*将B中坐标为（i,j）的分块B（i,j）向上循环移动j步*/
MPI_Sendrecv（b,dl2,MPI_FLOAT,get_index（my_row-my_col,my_col,sp）,1,
tmp_b,dl2,MPI_FLOAT,get_index（my_row+my_col,my_col,sp）,1,MPI_COMM_WORLD,&
memcpy（b,tmp_b,dl2*sizeof（float））;
main_shift
分块矩阵左移和上移，并计算分块c
voidmain_shift（）
for（l=0;
l<
sp;
l++）
/*矩阵块相乘，c+=a*b*/
dl;
c[i*dl+j]+=a[i*dl+k]*b[k*dl+j];
/*将分块a左移1位*/
MPI_Send（a,dl2,MPI_FLOAT,get_index（my_row,my_col-1,sp）,1,MPI_COMM_WORLD）;
MPI_Recv（a,dl2,MPI_FLOAT,get_index（my_row,my_col+1,sp）,1,MPI_COMM_WORLD,&
/*将分块b上移1位*/
MPI_Send（b,dl2,MPI_FLOAT,get_index（my_row-1,my_col,sp）,1,MPI_COMM_WORLD）;
MPI_Recv（b,dl2,MPI_FLOAT,get_index（my_row+1,my_col,sp）,1,MPI_COMM_WORLD,&
collect_c
rank为0的处理器从其余处理器收集分块矩阵c
voidcollect_C（）
inti,j,i2,j2,k;
/*分块矩阵在总矩阵中顶点边界值*/
/*将rank为0的处理器中分块矩阵c结果赋给总矩阵C对应位置*/
for（i=0;
i<
i++）
j<
j++）
C[i][j]=c[i*dl+j];
for（k=1;
k<
k++）
/*将rank为0的处理器从其他处理器接收相应的分块c*/
MPI_Recv（c,dl2,MPI_FLOAT,k,1,MPI_COMM_WORLD,&
p_jmin=（k%sp）*dl;
p_jmax=（k%sp+1）*dl-1;
p_imin=（k-（k%sp））/sp*dl;
i2=0;
/*将接收到的c拷至C中的相应位置,从而构造出C*/
j2=0;
for（j=p_jmin;
C[i][j]=c[i2*dl+j2];
j2++;
i2++;
/*函数名：
print
打印矩阵
指向矩阵指针的指针，字符串
voidprint（float**m,char*str）
printf（"
%s"
str）;
/*打印矩阵m*/
dg;
%15.0f"
m[i][j]）;
\n"
）;
main
主过程，Cannon算法，矩阵相乘
argc为命令行参数个数，argv为每个命令行参数组成的字符串数组
intmain（intargc,char*argv[]）
inti;
MPI_Init（&
argc,&
argv）;
/*启动MPI计算*/
MPI_Comm_size（MPI_COMM_WORLD,&
p）;
/*确定处理器个数*/
MPI_Comm_rank（MPI_COMM_WORLD,&
my_rank）;
/*确定各自的处理器标识符*/
sp=sqrt（p）;
/*确保处理器个数是完全平方数，否则打印错误信息，程序退出*/
if（sp*sp!
=p）
if（my_rank==0）
Numberofprocessorsisnotaquadraticnumber!
MPI_Finalize（）;
exit
（1）;
if（argc!
=2）
usage:
mpirun-npProcNumcannonMatrixDimension\n"
dg=atoi（argv[1]）;
/*总矩阵维数*/
dl=dg/sp;
/*计算分块矩阵维数*/
dl2=dl*dl;
/*计算处理器在逻辑阵列中的坐标*/
my_col=my_rank%sp;
my_row=（my_rank-my_col）/sp;
/*为a、b、c分配空间*/
a=（float*）malloc（dl2*sizeof（float））;
b=（float*）malloc（dl2*sizeof（float））;
c=（float*）malloc（dl2*sizeof（float））;
/*初始化c*/
dl2;
c[i]=0.0;
/*为tmp_a、tmp_b分配空间*/
tmp_a=（float*）malloc（dl2*sizeof（float））;
tmp_b=（float*）malloc（dl2*sizeof（float））;
/*rank为0的处理器为A、B、C分配空间*/
starttime=MPI_Wtime（）;
A=（float**）malloc（dg*sizeof（float*））;
B=（float**）malloc（dg*sizeof（float*））;
C=（float**）malloc（dg*sizeof（float*））;
A[i]=（float*）malloc（dg*sizeof（float））;
B[i]=（float*）malloc（dg*sizeof（float））;
C[i]=（float*）malloc（dg*sizeof（float））;
random_A_B（）;
/*rank为0的处理器随机化生成A、B矩阵*/
scatter_A_B（）;
/*rank为0的处理器向其他处理器发送A、B矩阵的相关块*/
}else/*rank不为0的处理器接收来自rank为
升级会员 