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

*******************

实践教学

*******************

大学

理学院

2016年春季学期

专业班级：_____________________ 姓 名： _____________________ 学 号：______________________ 指导教师：成 绩：_______________________

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

摘要

并行计算是计算机科学中重要研究内容，已有几十年的发展历程，它是在串行计算的基础上演变而来的。创建和应用并行计算的最主要原因是因为它是解决单处理机速度瓶颈的最好的方法之一。并行计算的发展是大型复杂科学、工程问题的计算需求以及与当代社会相关问题的需求。并行计算的研究需要并行计算机系统、并行算法和并行程序设计等专家以及并行应用领域专家的共同参与。

矩阵—向量乘法同样可以有带状划分和棋盘划分下两中并行算法。所谓棋盘划分（Checker Board Partitioning）就是将方阵划分成若干个子方阵，每个子方阵指派给一个处理器，此时任意处理器均不包含整行或整列。

目 录

一、题目及要求 . ............................................................................................................................................ 2 二、设计算法、算法原理 ............................................................................................................................. 2 三、 算法描述、设计流程 ........................................................................................................................... 3

3.1算法描述 . ......................................................................................................................................... 3 3.2设计流程图 . ...................................................................................................................................... 4 四、源程序代码及运行结果 ......................................................................................................................... 5

4.1源代码 . ............................................................................................................................................. 5 4.2题目运行结果示意图 .................................................................................................................... 12 五、算法分析、优缺点 ............................................................................................................................... 12

5.1算法分析 . ....................................................................................................................................... 12 5.2优缺点 . ........................................................................................................................................... 12 六、总 结 . .................................................................................................................................................... 13 七、参考文献 . .............................................................................................................................................. 14

一、题目及要求

棋盘划分的矩阵-向量乘法

273⎛9

101-4 2

已知A =

202325

-11-8777⎝4⎫⎛21⎫⎪ ⎪3⎪-13 ⎪

，求Y =AX , X =⎪ ⎪9-51

⎪ ⎪⎪ ⎪7⎭⎝47⎭

二、设计算法、算法原理

所谓棋盘划分（Checker Board Partitioning）就是将方阵划分成若干子方阵，每个子方阵指派给一个处理器，此时任一处理器均不包含整行整列。和带状划分类似，棋盘划分可分为块棋盘划分（Block- Checker Board Partitioning）和循环棋盘划分（Cycile-Checker Board Partitioning）。如图一所示：

（a ．块棋盘划分） （b. 循环棋盘划分）

图一 两种棋盘划分

矩阵划分成棋盘状可和处理器连成二维网孔相对应。对与一个n ⨯n 的方阵和 p ⨯p 的二维处理器，每个处理器均匀的分配有n /p ⨯n /p =n /p个矩阵元素。值得指出的是，和带状划分相比，棋盘划分可开发出更高的并行度。例如，对于一个n ⨯n 的方阵，棋盘划分最多可以使用n 2个处理器进行并行计算，但使用带状划分可用的处理器不能多于n 个。

()()

2

三、算法描述、设计流程

3.1算法描述

划分(块棋盘划分): Pij 存放a i,j , xi 置入P i,i 中 算法: 对p=n2情形

①每个P i,i 向P j,i 播送x i (一到多播送) ；

②按行方向进行乘-加与积累运算，最后一列P i,n-1收集的结果为y i ； 注: 对p

n p

t w +t h p

⎛⎫n .X中相应分量置入P i,i 的通讯时间:t s +t w ⎪log p +t h p ⎪⎝⎭⎛⎫n

.按列一到多播送时间: t s +t w ⎪log p +t h

p ⎪⎝⎭

p -1

)

p -1

)

n 2n

.按行单点积累的时间:T p ≈+t s log p +t w log p +3t h p

p p 示例如图二所示：

图二 p=n 时棋盘划分的矩阵—向量乘法

2

3.2设计流程图

图三 程序流程设计图

四、源程序代码及运行结果

4.1源代码 #include #include #include "mpi.h"

#define intsize sizeof(int) #define floatsize sizeof(float) #define A(x,y) A[x*N+y] #define B(x) B[x] #define C(x) C[x] #define a(x) a[x] #define b(x) b[x] #define c(x) c[x]

float *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); A=(float*)malloc(floatsize*M*N); for(i=0;i

for(j=0;j

fscanf(dataFile,"%f",A+i*N+j); } }

fscanf(dataFile,"%d",&K); if(N!=K) {

printf("the input is wrong\n"); exit(1); }

B=(float*)malloc(floatsize*K); for(i=0;i

fscanf(dataFile,"%f",B+i); }

fscanf(dataFile,"%d",&P); fclose(dataFile);

printf("Input of file dataIn.txt\n"); printf("%d\t %d\n",M,N); for(i=0;i

for(j=0;j

printf("%f\t",A(i,j));

}

printf("\n"); }

printf("%d\n",K); for(i=0;i

printf("%f\t",B(i)); }

printf("\n");

C=(float*)malloc(floatsize*M); }

void printfResult() {

int i;

printf("\nOutput of Matrix C=AB\n"); for(i=0;i

printf("%f\t",C(i)); printf("\n"); }

endtime=MPI_Wtime(); printf("\n");

printf("Whole running time = %f seconds\n",endtime-starttime); printf("Distribute data time = %f seconds\n",time1-starttime); printf("Parallel compute time = %f seconds\n",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_rank(MPI_COMM_WORLD,&myid); p=group_size;

if(myid==0) {

readData(); }

if(myid==0) {

for(i=0;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,&status); 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

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 or b fail");

if(myid==0)

{

for(i=0;i

{

a(i)=A(0,i);

b(i)=B(i);

}

}

if(myid==0)

{

for(i=1;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,&status);

MPI_Recv(&b(0),N,MPI_FLOAT,0,myid,MPI_COMM_WORLD,&status);

}

if(myid==0)

time1=MPI_Wtime();

for(i=0;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

{

MPI_Recv(&C(i),1,MPI_FLOAT,i,i,MPI_COMM_WORLD,&status);

}

}

if(myid==0)

{

printfResult();

}

}

MPI_Finalize();

if(myid

{

free(a);

free(b);

free(c);

if(myid==0)

{

free(C);

}

}

return(0);

}

4.2题目运行结果示意图

图四 运行结果

五、算法分析、优缺点

5.1算法分析

在处理过程中，每个处理器存放有矩阵的一个元素，而向量x i 通常是存放在p ii 中的。如果x i 是存放在处理器阵列的最后一列中，则进行矩阵向量乘时，先要将向量元素

与矩阵主对角线对准，在列方向上施行向量元素一到多播送；播送完毕后，接着施行乘—加和单点累积，最后按行收集结果向量y 。因为每个处理器执行乘加操作的时间为常数，所以在n ⨯n 的网孔上和n 2个处理器的超立方上的并行矩阵向量乘之总时间分别为O （n ）和O （logn ），他们不是成本最佳的。

5.2优缺点

在网孔上用同样多的处理器，棋盘划分的矩阵—向量乘法比带状划分时要快。如果p>n，则无法使用带状划分，而棋盘划分不受此限制，即使p ≤n ，棋盘划分也更优。值得指出的是，和带状划分相比，棋盘划分可开发出更高的并行度。例如，对于一个n ⨯n 的方阵，棋盘划分最多可以使用n 2个处理器进行并行计算，但使用带状划分可用的处理器不能多于n 个。

六、总结

通过本次并行计算课程设计，通过对所学知识的融会贯通，我加深了解了并行计算在大数据之中的应用以及他的优点。并行算法是并行计算中非常重要的问题。并行算法研究应该确立一个“理论—设计—实现—应用”的系统方法，形成一个完善“架构—算法—编程”的方法论，这样才能保证并行算法不断发展并变得更加实用。在课程设计中，我遇到了许多问题，而这些问题的产生都是由于我在理论知识和实践经验的缺乏而造成的。

在此过程中，感触最深的便是实践联系理论的重要性，当遇到实际问题时，只要认真思考，用所学的知识，再一步步探索，是完全可以解决遇到的一般问题的。通过老师的指导和自学克服了很多的困难，我得到了一次难得的锻炼机会，加深了对理论知识的理解，也让我更加深刻地体会到自学能力的重要性。课程设计让我真正做到了学有所用，在设计当中受益匪浅。

通过这次的课程学习，我也认识到了自己的很多不足，对专业知识的不够熟悉，以至于在设计学习过程中卡住了好多次，我想在今后的学习中我会加大自己的学习力度，努力强化自己的专业知识，同时也学习其他同学思考问题的思路，在以后的学习中可以借鉴。在本次课程设计中老师耐心细致地给予了我很多的指导，在此深表感谢，我相信通过这次课程设计的锻炼，能为我以后处理程序设计打下坚实的基础。

七、参考文献

[1]陈国良，章峰，吴俊敏，等.002. 并行计算机体系结构. 北京：高等教育出版社.

[2]陈国良. 并行算法的可扩放性分析. 小型微型计算机系统，16(2):10-16.1995.

[3]陈国良. 并行算法的设计与分析.3版. 北京：高等教育出版社.2009.

[4]陈国良，等. 并行算法实践. 北京：高等教育出版社.2003.

[5]陈国良.VLSI 计算理论与并行算法. 合肥：中国科学技术大学出版社.1991.

[6]Adams J et al.1992,The FORTRAN 90 Handbook.[S.L]:McGraw-Hill

[7]Huang Y,PakerY.1991.A Parallel FFT Algorithm for Transputer Network.parallel Computerting,17:895-906

[8]高性能计算机TOP500,http://www.top.org;