并行程序设计王刚矩阵乘法的并行化的设计与实现Word格式文档下载.docx
《并行程序设计王刚矩阵乘法的并行化的设计与实现Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《并行程序设计王刚矩阵乘法的并行化的设计与实现Word格式文档下载.docx（19页珍藏版）》请在冰点文库上搜索。
应符合科技论文写作规范，题目、摘要、关键字、章节、参考文献等等完整、正确。
这方面可参考附件范文。
四、论文提交注意事项：
1、论文一律以此文件为封面，写明学习中心、专业、姓名、学号等信息。
论文保存为word文件，以“课程名+学号+姓名”命名。
2、论文一律采用线上提交方式，在学院规定时间内上传到教学教务平台，逾期平台关闭，将不接受补交。
3、不接受纸质论文。
4、与论文一同打包提交源程序，注意，是提交.cpp、.h等源程序，不要将工程文件、编译后的目标文件等打包提交。
5、如有抄袭雷同现象，将按学院规定严肃处理。
矩阵乘法的并行化的设计与实现
摘要：
矩阵乘法是最基本的矩阵运算之一,由于其计算密集的特点,适合于在FPGA上实现。
本文给定两个n
阶矩阵A
与B
，矩阵乘法是指计算C=A×
B
，现在对两个矩阵乘法进行串行和并行的实验和分析。
关键词：
矩阵乘法；
并行算法；
实验；
一、算法原理:
1、串行算法
通常的O（n3）矩阵乘矩阵的串行计算过程如算法1所示，此外为计算矩阵相乘，还可以有对3层循环采用其他嵌套形式的串行算法。
算法1:
稠密矩阵相乘的i,j,k形式串行算法
2、并行算法
两个矩阵相乘的行列划分并行算法假设一共有P个进程，将矩阵A按行分成P个块，将矩阵B按列分成P个块：
每块包含连续若干个行．为使得负载平衡，应使得每块中的行数尽量相等．将Ak与Bk分别存储在进程Pk的A’与B’中．将C分为P×
P块，且将Ci,j存储在
的p’i中，如算法2
算法2稠密矩阵乘C=A×
B的行列划分并行算法
实验由MPICH2在VS2010上进行并行环境的配置来完成，单机情况下用进程数的个数模拟多处理器。
在实验中算法由以下几个函数实现：
voidreadData（）;
此函数被rankID为0的进程调用，负责从dataIn.txt文件中A[M,K],B[P,N]两个相乘矩阵的数据，并为结果矩阵C[M,N]分配空间。
其中C[N,N]=A[M,K]*B[P,N]。
intgcd（intM,intN,intgroup_size）此函数用来返回两个整数的不大于group_size的最大公因子，即算法所用到的处理器个数，为了保证行划分和列划分可以平均的划分，通过求M，N不大于group_size的最大公因子来确定实际用到的处理器p。
voidprintResult（）;
此函数被rankID为0的进程调用，用来将A,B,C矩阵打印输出给用户，并输出用于分发数据和并行计算的时间。
intmain（intargc,char**argv）;
程序的主函数。
算法分析（可扩展性分析）：
在LogP模型上，算法2并行执行时间为：
由此可知，并行效率为：
因此，等效率函数为：
3、算法的MPI程序:
//matrix.cpp:
定义控制台应用程序的入口点。
//
#include"
stdafx.h"
stdio.h"
stdlib.h"
mpi.h"
#include<
mpicxx.h>
#defineintsizesizeof（int）
#definefloatsizesizeof（float）
#definecharsizesizeof（char）
#defineA（x,y）A[x*K+y]
#defineB（x,y）B[x*N+y]
#defineC（x,y）C[x*N+y]
#definea（x,y）a[x*K+y]
#defineb（x,y）b[x*n+y]
#definebuffer（x,y）buffer[x*n+y]/*此宏用来简化对标号为奇数的处理器内的缓冲空间的访问*/
#definec（l,x,y）c[x*N+y+l*n]
float*a,*b,*c,*buffer;
ints;
float*A,*B,*C;
/*A[M,K],B[P,N].正确的情况下K应该等于P,否则无法进行矩阵相乘*/
intM,N,K,P;
intm,n;
intmyid;
intp;
/*保存工作站集群中处理器数目，也即通信子大小*/
FILE*dataFile;
/*用于读取输入文件内容和将计算结果输出到结果文件的临时文件指针*/
MPI_Statusstatus;
doubletime1;
doublestarttime,endtime;
/*
*函数名:
readData
*功能：
此函数被rankID为0的进程调用，负责从dataIn.txt文件中读入
*A[M,K],B[P,N]两个相乘矩阵的数据，并为结果矩阵C[M,N]分配空间。
*其中C[N,N]=A[M,K]*B[P,N]
*输入：
无
*返回值：
无
*/
voidreadData（）
{
inti,j;
starttime=MPI_Wtime（）;
dataFile=fopen（"
dataIn.txt"
"
r"
）;
fscanf（dataFile,"
%d%d"
&
M,&
K）;
/*读取矩阵A的行，列数M,K*/
A=（float*）malloc（floatsize*M*K）;
/*为矩阵A分配空间*/
for（i=0;
i<
M;
i++）/*读入矩阵A的各元素*/
{
for（j=0;
j<
K;
j++）
%f"
A+i*K+j）;
}
P,&
N）;
/*读取矩阵B的行，列数P,N*/
if（K!
=P）/*K应该等于P,否则矩阵无法相乘*/
printf（"
theinputiswrong\n"
exit
（1）;
B=（float*）malloc（floatsize*K*N）;
/*为矩阵B分配空间*/
i++）/*从文件中读入矩阵B的各元素*/
N;
B+i*N+j）;
fclose（dataFile）;
Inputoffile\"
dataIn.txt\"
\n"
%d\t%d\n"
M,K）;
/*输出A矩阵的维数*/
for（i=0;
i<
M;
i++）/*输出A矩阵的数据*/
for（j=0;
j<
K;
j++）printf（"
%f\t"
A（i,j））;
K,N）;
/*输出B矩阵的维数*/
i++）/*输出B矩阵的数据*/
N;
B（i,j））;
C=（float*）malloc（floatsize*M*N）;
/*为结果矩阵C[M,N]分配空间*/
}
gcd
此函数用来返回两个整数的不大于group_size的最大公因子
M,N:
要求最大公因数的两个整数
*group_size所求公因子必须小于此参数，此参数代表用户指定的通信子大小
M和N的不大于group_size的最大公因子
intgcd（intM,intN,intgroup_size）
inti;
for（i=M;
i>
0;
i--）
if（（M%i==0）&
&
（N%i==0）&
（i<
=group_size））
returni;
return1;
printResult
此函数被rankID为0的进程调用，用来将A,B,C矩阵打印输出给用户，
*并输出用于分发数据和并行计算的时间
voidprintResult（）
\nOutputofMatrixC=AB\n"
i++）/*输出C矩阵的结果数据*/
C（i,j））;
endtime=MPI_Wtime（）;
Wholerunningtime=%fseconds\n"
endtime-starttime）;
Distributedatatime=%fseconds\n"
time1-starttime）;
Parallelcomputetime=%fseconds\n"
endtime-time1）;
main
程序的主函数
argc为命令行参数个数；
*argv为每个命令行参数组成的字符串数组。
*输出：
返回0代表程序正常结束；
其它值表明程序出错。
intmain（intargc,char**argv）
inti,j,k,l,group_size,mp1,mm1;
MPI_Init（&
argc,&
argv）;
MPI_Comm_size（MPI_COMM_WORLD,&
group_size）;
MPI_Comm_rank（MPI_COMM_WORLD,&
myid）;
p=group_size;
//下面一段程序负责从dataIn.txt文件中读入A[M,K],B[P,N]两个相乘矩阵的数据，
//并为结果矩阵C[M,N]分配空间。
C[N,N]=A[M,K]*B[P,N]
//注意这段程序只有编号为0的处理器才执行此步操作
if（myid==0）
readData（）;
if（myid==0）/*由编号为0的进程将A,B两矩阵的行列维数M,K,N发送给所有其他进程*/
for（i=1;
p;
i++）
MPI_Send（&
M,1,MPI_INT,i,i,MPI_COMM_WORLD）;
K,1,MPI_INT,i,i,MPI_COMM_WORLD）;
N,1,MPI_INT,i,i,MPI_COMM_WORLD）;
else/*编号非0的进程负责接收A,B两矩阵的行列维数M,K,N*/
MPI_Recv（&
M,1,MPI_INT,0,myid,MPI_COMM_WORLD,&
status）;
K,1,MPI_INT,0,myid,MPI_COMM_WORLD,&
N,1,MPI_INT,0,myid,MPI_COMM_WORLD,&
p=gcd（M,N,group_size）;
m=M/p;
/*m代表将矩阵按行分块后每块的行数*/
n=N/p;
/*m代表将矩阵按列分块后每块的列数*/
if（myid<
p）
a=（float*）malloc（floatsize*m*K）;
/*a[m,K]用来存储本处理器拥有的矩阵A的行块*/
b=（float*）malloc（floatsize*K*n）;
/*b[K,n]用来存储此时处理器拥有的矩阵B的列块*/
c=（float*）malloc（floatsize*m*N）;
/*c[m,N]用来存储本处理器计算p-1次得到所有结果*/
if（myid%2!
=0）/*为标号为奇数的处理器分配发送缓冲空间*/
buffer=（float*）malloc（K*n*floatsize）;
if（a==NULL||b==NULL||c==NULL）/*如果分配空间出错，则打印出错信息*/
Allocatespacefora,borcfail!
"
if（myid==0）/*标号为0的处理器将应该它拥有的矩阵A,B的元素读入自己的a,b中*/
for（i=0;
m;
for（j=0;
j++）
a（i,j）=A（i,j）;
n;
b（i,j）=B（i,j）;
if（myid==0）/*标号为0的处理器将其他处理器的初始数据分别发给各处理器*/
for（i=1;
A（m*i,0）,K*m,MPI_FLOAT,i,i,MPI_COMM_WORLD）;
B（j,n*i）,n,MPI_FLOAT,i,i,MPI_COMM_WORLD）;
free（A）;
free（B）;
/*至此，A,B两矩阵的数据已经完全被分散到各处理器。
释放A,B所占空间*/
else/*标号非0的处理器从0处理器接受各自的初始矩阵数据*/
MPI_Recv（a,K*m,MPI_FLOAT,0,myid,MPI_COMM_WORLD,&
b（j,0）,n,MPI_FLOAT,0,myid,MPI_COMM_WORLD,&
if（myid==0）
time1=MPI_Wtime（）;
/*标号为0的处理器记录开始矩阵相乘计算的时间*/
i++）/*一共进行p轮计算*/
l=（i+myid）%p;
for（k=0;
k<
k++）
for（c（l,k,j）=0,s=0;
s<
s++）
c（l,k,j）+=a（k,s）*b（s,j）;
mm1=（p+myid-1）%p;
/*计算本进程的前一个进程的标号*/
mp1=（myid+1）%p;
/*计算本进程的后一个进程的标号*/
if（i!
=p-1）
if（myid%2==0）/*偶数号处理器先发送后接收*/
MPI_Send（b,K*n,MPI_FLOAT,mm1,mm1,MPI_COMM_WORLD）;
MPI_Recv（b,K*n,MPI_FLOAT,mp1,myid,MPI_COMM_WORLD,&
else/*奇数号处理器先将B的列块存于缓冲区buffer中，然后接收编号在其后面的
处理器所发送的B的列块，最后再将缓冲区中原矩阵B的列块发送给编号
在其前面的处理器*/
for（k=0;
buffer（k,j）=b（k,j）;
MPI_Send（buffer,K*n,MPI_FLOAT,mm1,mm1,MPI_COMM_WORLD）;
if（myid==0）/*标号为0的进程直接将计算结果保存到结果矩阵C中*/
C（i,j）=*（c+i*N+j）;
if（myid!
=0）/*标号非0的进程则要把计算结果发送到标号为0的处理器中去*/
MPI_Send（c,m*N,MPI_FLOAT,0,myid,MPI_COMM_WORLD）;
else/*标号为0的进程负责接收其他进程的计算结果并保存到结果矩阵C中*/
for（k=1;
MPI_Recv（c,m*N,MPI_FLOAT,k,k,MPI_COMM_WORLD,&
C（（k*m+i）,j）=*（c+i*N+j）;
if（myid==0）/*0号处理器负责将A,B,C矩阵打印输出给用户，并输出用于分发数据和并行计算的时间*/
printResult（）;
MPI_Finalize（）;
p）/*释放所有临时分配空间*/
free（a）;
free（b）;
free（c）;
if（myid==0）/*只有0号进程要释放C*/
free（C）;
if（myid%2!
=0）/*只有奇数号进程要释放buffer*/
free（buffer）;
%d"
p）;
getchar（）;
return（0）;
三、算例结果及分析
上面的dataIn.txt是两个10乘以10的矩阵，总的时间是0.197588秒，可以看到主要的时间用来通讯和分发数据，并行计算的时间其实较短。
换一个算例，即10乘以20矩阵乘以20乘以10的矩阵，下面是运行时间：
四、总结
数据量增大，但是并行时间并没有大量增加，而是在通讯时间上面消耗更多时间，跟算法可扩展的等效率分析一致。
参考文献
[1]都志辉，《高性能计算之并行编程技术——MPI并行程序设计》
[2]何红旗,邵仪.矩阵乘法的FPGA并行设计与实现[C]//计算机研究新进展（2010）——河南省计算机学会2010年学术年会论文集.2010.
升级会员 