2015－2016学年第一学期《并行程序设计》期末考试
2015－2016学年第一学期《并行程序设计》期末考试
第1页(共2页)
中国科学技术大学
2015－2016学年第一学期考试试卷
考试科目:并行程序设计 得分:
学生所在系: 姓名: _ _学号:_
fori=1to16do//循环2A[i+3]=A[i]+B[i];endforfor
fori=1to16do//循环2A[i+3]=A[i]+B[i];
endfor
fori=2to10do//循环1
forj=ito10
A[i,j]=(A[i,j-1]+A[i-1,j])*0.5;
endforendfor
fork=1to16step5do //循环3,k的循环步长为5fori=kto
fork=1to16step5do //循环3,k的循环步长为5fori=ktomin(16,i+4)do//设min为求最小值函数
A[i+3]=A[i]+B[i]
endforendfor
二、给出两种MPI实现方案：0号进程采用行交叉划分方式，将N*N的双精度数矩阵发送到P个进程（设N能被P整除）。（20分）
三、给出cannon乘法在4*4进程拓扑下的A、B子块矩阵在初始对齐以及前三次移位后的分布示意图。（10分）
四、设复数类型定义如下:
typedefstruct{doublereal,imag;
}Complex;
给出一个自定义归约函数及相关MPI代码，完成复数类型的加法。（15分）
2015－2016学年第一学期《并行程序设计》期末考试
2015－2016学年第一学期《并行程序设计》期末考试
第2页(共2页)
五、两多边形相交问题的一种朴素并行算法如下：
对于多边形R的每一条边，要确定其是否与多边形Q相交；如果R的边中有一条边与Q相交，那么就可以断定多边形R与Q是相交的。假设R有n条边，Q有m条边，总共有p个处理器P1,P2,…,Pp。对于R中的每条边依次判断是否与Q相交。
输入：多边形R的n条边E1,E2,,…,En的两个端点坐标集合S1，多边形Q的m条边
F1,F2,,…,Fm的两个端点坐标集合S2
输出：两个多边形是否相交：true(两多边形相交)；false(两多边形不相交)
Begin
fori=1tomdo将Fi广播到所有处理器上endfor
forj=1tondo将Ej广播到所有处理器上endfor
forallPkwhere1≤k≤ppar-do
fori=1to
?n?do
p
? ?
forj=1tomdo
if intersects(Ei×p+k,Fj)then resultk=trueendif
endforendfor
endfor
将各个处理器上resultk返回到主处理器，如果其中有一个为真，则两多边形相交，否则两多边形不相交
End
给出上述算法的MPI实现（15分）
本试卷答题过程中可能用到的函数原型：
本试卷答题过程中可能用到的函数原型：MPI_Comm_size(MPI_Commcomm,int*size)MPI_Comm_rank(MPI_Commcomm,int*rank)
MPI_Reduce(void*sendbuf,void*recvbuf,intcount,MPI_Datatypedatatype,MPI_Opop,introot,MPI_Commcomm)MPI_Bcast(void*buffer,intcount,MPI_Datatypedatatype,introot,MPI_Commcomm)
MPI_Gather(void*sendbuf,intsendcnt,MPI_Datatypesendtype,void*recvbuf,intrecvcnt,MPI_Datatyperecvtype,introot,MPI_Commcomm)
MPI_Send(void*buf,intcount,MPI_Datatypedatatype,intdest,inttag,MPI_Commcomm)
MPI