天下美食菜谱与做法-我们身边的科学

*******************
实践教学
*******************






大学

理学院

2016年春季学期


并行计算
课程设计








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

棋盘划分下的矩阵—向量乘法
摘要
并行计算是计算机科学中重要研究内容，已有几十年的发展历程，它是在串行计算的基础上演
变而来的 。创建和应用并行计算的最主要原因是因为它是解决单处理机速度瓶颈的最好的方法之一。
并行计算的发 展是大型复杂科学、工程问题的计算需求以及与当代社会相关问题的需求。并行计算
的研究需要并行计算 机系统、并行算法和并行程序设计等专家以及并行应用领域专家的共同参与。
矩阵—向量乘法同样可以 有带状划分和棋盘划分下两中并行算法。所谓棋盘划分
（Checker Board Partiti oning）就是将方阵划分成若干个子方阵，每个子方阵指派给一个处理器，此
时任意处理器均不包含 整行或整列。

目 录
一、题目及要求 ...................................... .................................................. .................................................. ... 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




























1

一、题目及要求
棋盘划分的矩阵-向量乘法
273

9

1014

2
已知
A

202325


118777

4

21


3

13

，求
YAX
,X

951


7

47

二、设计算法、算法原理
所谓棋盘划分（Checker Board Partit ioning）就是将方阵划分成若干子方阵，每
个子方阵指派给一个处理器，此时任一处理器均不包含 整行整列。和带状划分类似，棋
盘划分可分为块棋盘划分（Block- Checker Board Partitioning）和循环棋盘划分
（Cycile-Checker Board Partitioning）。如图一所示：

（a．块棋盘划分） （b.循环棋盘划分）
图一 两种棋盘划分
矩阵划分成棋盘状可和处理器连成二维网孔相对应。对与一个n

n的方阵和

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


2

2

三、算法描述、设计流程
3.1算法描述
划分(块棋盘划分): P
ij
存放a
i,j
, x
i
置入P
i,i
中
算法: 对p=n
2
情形
①每个P
i,i
向P
j,i
播送x
i
(一到多播送)；
②按行方向进行乘- 加与积累运算，最后一列P
i,n-1
收集的结果为y
i
；
注: 对p2
情形,p个处理器排成
pp
的二维网孔，
算法中P
i,i
向P
j,i
播送X中相应的
np
个分量
(1)网孔连接的计算时间T
p
(CT):
t
s

n
p
t
w
t
h
p


n

.X中相应分量置入P
i,i
的通讯 时间:
t
s
t
w

logpt
h
< br>p



n
.按列一到多播送时间: < br>
t
s
t
w

logpt
h

p



p1



p1


n
2
n
.按行单点积累的时间:
T
p
t
s
logpt
wlogp3t
h
p

p
p
示例如图二所示：

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

3
2

3.2设计流程图



















图三 程序流程设计图



4

四、源程序代码及运行结果
4.1源代码
#include
#include
#include
#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();

5

dataFile=fopen(
fscanf(dataFile,
A=(float*)malloc(floatsize*M*N);
for(i=0;i {
for(j=0;j {
fscanf(dataFile,
}
}
fscanf(dataFile,
if(N!=K)
{
printf(
exit(1);
}
B=(float*)malloc(floatsize*K);
for(i=0;i {
fscanf(dataFile,
}
fscanf(dataFile,
fclose(dataFile);
printf(
printf(
for(i=0;i {
for(j=0;j {
printf(

6

}
printf(
}
printf(
for(i=0;i {
printf(

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

void printfResult()
{
int i;
printf(
for(i=0;i {
printf(
printf(
}
endtime=MPI_Wtime();
printf(
printf(
printf(
printf(
}

int main(int argc,char **argv)

7

{
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,M PI_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,&statu s);

}
if(myid {

8

a=(float *)malloc(floatsize*N);
b=(float *)malloc(floatsize*K);
c=(float *)malloc(floatsize*1);
c(0)=0;
if(a==NULL||b==NULL)
printf(
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)

9

{

MPI_Recv(&a(0),N,MPI_FLOAT,0,myid,MPI_COMM_WOR LD,&status);

MPI_Rec v(&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_WOR LD);
}
if(myid==0)
{

C(0)=c(0);
for(i=1;i
10

{
MPI_Recv(&C(i),1,MPI_FLOAT,i,i,MPI_COMM_W ORLD,&status);
}
}
if(myid==0)
{
printfResult();
}
}
MPI_Finalize();
if(myid {
free(a);
free(b);
free(c);
if(myid==0)
{
free(C);
}
}
return(0);
}

11

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 个。


12

六、总结
通过本次并行计算课程设计，通过对所学知识的融会贯通，我加深了解了并行计算
在大数据之中的应用以 及他的优点。并行算法是并行计算中非常重要的问题。并行算法
研究应该确立一个“理论—设计—实现— 应用”的系统方法，形成一个完善“架构—算
法—编程”的方法论，这样才能保证并行算法不断发展并变 得更加实用。在课程设计中，
我遇到了许多问题，而这些问题的产生都是由于我在理论知识和实践经验的 缺乏而造成
的。
在此过程中，感触最深的便是实践联系理论的重要性，当遇到实际问题时，只 要认
真思考，用所学的知识，再一步步探索，是完全可以解决遇到的一般问题的。通过老师
的指 导和自学克服了很多的困难，我得到了一次难得的锻炼机会，加深了对理论知识的
理解，也让我更加深刻 地体会到自学能力的重要性。课程设计让我真正做到了学有所用，
在设计当中受益匪浅。
通过 这次的课程学习，我也认识到了自己的很多不足，对专业知识的不够熟悉，以
至于在设计学习过程中卡住 了好多次，我想在今后的学习中我会加大自己的学习力度，
努力强化自己的专业知识，同时也学习其他同 学思考问题的思路，在以后的学习中可以
借鉴。在本次课程设计中老师耐心细致地给予了我很多的指导， 在此深表感谢，我相信
通过这次课程设计的锻炼，能为我以后处理程序设计打下坚实的基础。









13

七、参考文献
[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 el
Computerting,17:895-906
[8]高性能计算机TOP500,http:;
















14