棋盘划分下的矩阵—向量乘法

1、*实践教学*大学 理学院 2016年春季学期 并行计算 课程设计专业班级：_ 姓 名： _学 号：_指导教师：_ 成 绩：_棋盘划分下的矩阵向量乘法摘要并行计算是计算机科学中重要研究内容，已有几十年的发展历程，它是在串行计算的基础上演变而来的。创建和应用并行计算的最主要原因是因为它是解决单处理机速度瓶颈的最好的方法之一。并行计算的发展是大型复杂科学、工程问题的计算需求以及与当代社会相关问题的需求。并行计算的研究需要并行计算机系统、并行算法和并行程序设计等专家以及并行应用领域专家的共同参与。矩阵向量乘法同样可以有带状划分和棋盘划分下两中并行算法。所谓棋盘划分（Checker Board

2、 Partitioning）就是将方阵划分成若干个子方阵，每个子方阵指派给一个处理器，此时任意处理器均不包含整行或整列。目 录一、题目及要求2二、设计算法、算法原理2三、 算法描述、设计流程33.1算法描述33.2设计流程图4四、源程序代码及运行结果54.1源代码54.2题目运行结果示意图12五、算法分析、优缺点125.1算法分析125.2优缺点12六、总 结13七、参考文献14一、题目及要求棋盘划分的矩阵-向量乘法已知，求二、设计算法、算法原理所谓棋盘划分（Checker Board Partitioning）就是将方阵划分成若干子方阵，每个子方阵指派给一个处理器，此时任一处理器均

3、不包含整行整列。和带状划分类似，棋盘划分可分为块棋盘划分（Block- Checker Board Partitioning）和循环棋盘划分（Cycile-Checker Board Partitioning）。如图一所示：（a 块棋盘划分） （b.循环棋盘划分）图一 两种棋盘划分矩阵划分成棋盘状可和处理器连成二维网孔相对应。对与一个nn的方阵和的二维处理器，每个处理器均匀的分配有2/p个矩阵元素。值得指出的是，和带状划分相比，棋盘划分可开发出更高的并行度。例如，对于一个nn的方阵，棋盘划分最多可以使用n2个处理器进行并行计算，但使用带状划分可用的处理器不能多于n个。3、 算法描述、设计流程3

4、.1算法描述划分(块棋盘划分): Pij存放ai,j, xi置入Pi,i中算法: 对p=n2情形 每个Pi,i向Pj,i播送xi(一到多播送)； 按行方向进行乘-加与积累运算，最后一列Pi,n-1收集的结果为yi；注: 对p<n2情形,p个处理器排成的二维网孔， 算法中Pi,i向Pj,i播送X中相应的个分量 (1)网孔连接的计算时间Tp(CT): .X中相应分量置入Pi,i的通讯时间: .按列一到多播送时间: .按行单点积累的时间:示例如图二所示：图二 p时棋盘划分的矩阵向量乘法3.2设计流程图mpi的头文件相关变量声明MPI_INIT()MPI_COMM_RANK()MPI_COMM_

5、SIZE()进入MPI系统矩阵内部的通信应用控制实体：矩阵内部的计算程序MPI_FINALIZE()退出MPI系统结束开始循环直至结束图三 程序流程设计图四、源程序代码及运行结果4.1源代码#include<stdio.h>#include<stdlib.h>#include "mpi.h"#define intsize sizeof(int)#define floatsize sizeof(float)#define A(x,y) Ax*N+y#define B(x) Bx#define C(x) Cx#define a(x) ax#define

6、b(x) bx#define c(x) cxfloat *a,*b,*c;float *A,*B,*C;int M,N,K,P;int m,n;int myid;FILE *dataFile;MPI_Status status;double time1;double starttime,endtime;void readData() int i,j; starttime=MPI_Wtime(); dataFile=fopen("dataIn.txt","r"); fscanf(dataFile,"%d%d",&M,&N

7、); A=(float*)malloc(floatsize*M*N); for(i=0;i<M;i+) for(j=0;j<N;j+) fscanf(dataFile,"%f",A+i*N+j); fscanf(dataFile,"%d",&K); if(N!=K) printf("the input is wrongn"); exit(1); B=(float*)malloc(floatsize*K); for(i=0;i<K;i+) fscanf(dataFile,"%f",B+i);

8、 fscanf(dataFile,"%d",&P); fclose(dataFile); printf("Input of file dataIn.txtn"); printf("%dt %dn",M,N); for(i=0;i<M;i+) for(j=0;j<N;j+) printf("%ft",A(i,j); printf("n"); printf("%dn",K); for(i=0;i<K;i+) printf("%ft",

9、B(i); printf("n"); C=(float*)malloc(floatsize*M);void printfResult() int i; printf("nOutput of Matrix C=ABn"); for(i=0;i<M;i+) printf("%ft",C(i); printf("n"); endtime=MPI_Wtime(); printf("n"); printf("Whole running time = %f secondsn",en

10、dtime-starttime); printf("Distribute data time = %f secondsn",time1-starttime); printf("Parallel compute time = %f secondsn",endtime-time1);int main(int argc,char *argv) int i,k,group_size,p; MPI_Init(&argc,&argv); MPI_Comm_size(MPI_COMM_WORLD,&group_size); MPI_Comm_r

11、ank(MPI_COMM_WORLD,&myid); p=group_size; if(myid=0) readData(); if(myid=0) for(i=0;i<p;i+) MPI_Send(&M,1,MPI_INT,i,i,MPI_COMM_WORLD); MPI_Send(&N,1,MPI_INT,i,i,MPI_COMM_WORLD); MPI_Send(&K,1,MPI_INT,i,i,MPI_COMM_WORLD); else MPI_Recv(&M,1,MPI_INT,0,myid,MPI_COMM_WORLD,&sta

12、tus); MPI_Recv(&N,1,MPI_INT,0,myid,MPI_COMM_WORLD,&status); MPI_Recv(&K,1,MPI_INT,0,myid,MPI_COMM_WORLD,&status); if(myid<p) a=(float *)malloc(floatsize*N); b=(float *)malloc(floatsize*K); c=(float *)malloc(floatsize*1); c(0)=0; if(a=NULL|b=NULL) printf("Allocate spzce for a

13、or b fail"); if(myid=0) for(i=0;i<N;i+) a(i)=A(0,i); b(i)=B(i); if(myid=0) for(i=1;i<p;i+) MPI_Send(&A(i,0),N,MPI_FLOAT,i,i,MPI_COMM_WORLD); MPI_Send(&B(0),N,MPI_FLOAT,i,i,MPI_COMM_WORLD); free(A); free(B); if(myid!=0) MPI_Recv(&a(0),N,MPI_FLOAT,0,myid,MPI_COMM_WORLD,&stat

14、us); MPI_Recv(&b(0),N,MPI_FLOAT,0,myid,MPI_COMM_WORLD,&status); if(myid=0) time1=MPI_Wtime(); for(i=0;i<N;i+) c(0)=c(0)+a(i)*b(i); if(myid!=0) MPI_Send(&c(0),1,MPI_FLOAT,0,myid,MPI_COMM_WORLD); if(myid=0) C(0)=c(0); for(i=1;i<p;i+) MPI_Recv(&C(i),1,MPI_FLOAT,i,i,MPI_COMM_WORLD,

15、&status); if(myid=0) printfResult(); MPI_Finalize(); if(myid<p) free(a); free(b); free(c); if(myid=0) free(C); return(0);4.2题目运行结果示意图图四 运行结果五、算法分析、优缺点5.1算法分析在处理过程中，每个处理器存放有矩阵的一个元素，而向量xi通常是存放在pii中的。如果xi是存放在处理器阵列的最后一列中，则进行矩阵向量乘时，先要将向量元素与矩阵主对角线对准，在列方向上施行向量元素一到多播送；播送完毕后，接着施行乘加和单点累积，最后按行收集结果向量y。因为

16、每个处理器执行乘加操作的时间为常数，所以在nn的网孔上和n2个处理器的超立方上的并行矩阵向量乘之总时间分别为O（n）和O（），他们不是成本最佳的。5.2优缺点 在网孔上用同样多的处理器，棋盘划分的矩阵向量乘法比带状划分时要快。如果p>n，则无法使用带状划分，而棋盘划分不受此限制，即使pn，棋盘划分也更优。值得指出的是，和带状划分相比，棋盘划分可开发出更高的并行度。例如，对于一个nn的方阵，棋盘划分最多可以使用n个处理器进行并行计算，但使用带状划分可用的处理器不能多于n个。六、总结通过本次并行计算课程设计，通过对所学知识的融会贯通，我加深了解了并行计算在大数据之中的应用以及他的优点。并行算

17、法是并行计算中非常重要的问题。并行算法研究应该确立一个“理论设计实现应用”的系统方法，形成一个完善“架构算法编程”的方法论，这样才能保证并行算法不断发展并变得更加实用。在课程设计中，我遇到了许多问题，而这些问题的产生都是由于我在理论知识和实践经验的缺乏而造成的。在此过程中，感触最深的便是实践联系理论的重要性，当遇到实际问题时，只要认真思考，用所学的知识，再一步步探索，是完全可以解决遇到的一般问题的。通过老师的指导和自学克服了很多的困难，我得到了一次难得的锻炼机会，加深了对理论知识的理解，也让我更加深刻地体会到自学能力的重要性。课程设计让我真正做到了学有所用，在设计当中受益匪浅。通过这次的课程学习，我也认识到了自己的很多不足，对专业知识的不够熟悉，以至于在设计学习过程中卡住了好多次，我想在今后的学习中我会加大自己的学习力度，努力强化自己的专业知识，同时也学习其他同学思考问题的思路，在以后的学习中可以借鉴。在本次课程设计中老师耐心细致地给予了我很多的指导，在此深表感谢，我相信通过这次课程设计的锻炼，能为我以后处理程序设计打下坚实的基础。七、参考文献1陈国良，章峰，吴俊敏，等.002.并行计算机体系结构.北京：高等教育出版社.2陈国良.并行算法的可扩放性分析.小型微型计算机系统，16(2):10-16.1