2017－2018学年第一学期《并行程序设计》期末考试
2017－2018学年第一学期《并行程序设计》期末考试
第1页(共2页)
中国科学技术大学
2017－2018学年第一学期考试试卷
考试科目:并行程序设计 得分:
学生所在系: 姓名: _ _学号:_
fori=1to100do//
fori=1to100do//循环2N是常量
X[i]=Y[i]+10;//语句S1forj=1to100do
B[j]=A[j,N];//语句S2fork=1to100do
A[j+1,k]=B[j]+C[j,k];//语句S3endfor//loop-k
Y[i+j]=A[j+1,N];//语句S4endfor//loop-j
endfor//loop-i
给出此循环的语句依赖图。（10分）
尝试向量化/并行化此循环。（10分）
fori=1toMdo//循环1 M，N，C均是常量
forj=1toN
A[i+1,j+1]=A[i,j]+C;
endforendfor
给出迭代依赖示意图。(5分)
简述能否逆转外层的i循环？能否交换内外循环次序？（10分）
尝试用OpenMP并行化此循环。（5分）
二、给出如下C程序片段的OpenMP实现。（15分）
doublefactor=1.0,sum=0.0,Pi=0.0;intk;
for(k=0;kN;k++){//N是常量
sum=sum+factor/(2*k+1);factor=-factor;
}
Pi=4.0*sum;
三、采用MPI_Sendrecv()给出cannon乘法在N*N进程拓扑下，进行A、B子块矩阵初始对齐以及随后计算中移位对齐操作的主要代码。（15分）
2017－2018学年第一学期《并行程序设计》期末考试
2017－2018学年第一学期《并行程序设计》期末考试
第2页(共2页)
四、设有长度为N的双精度数向量M。给出构造新的消息类型且发送M中编号可被3整除的所有分量元素的MPI代码。设编号由0开始。（10分）
五、参数服务器系统的MPI模拟。
设系统中总计有N个进程，其中P个进程作为参数服务器进程，而Q个进程作为
工作进程（N=P+Q，且0PQ）。工作进程和服务器进程的互动过程如下：
第n个工作进程首先产生一个随机数，发送给第n%P个参数服务器进程。然后等待并接收它对应的参数服务器进程发送更新后的数值，之后，再产生随机数，再发送……。
每个参数服务器进程等待并接收来自它对应的所有工作进程的数据，在此之后，经通信，使所有的参数服务器获得所有工作进程发送数据的平均值。
每个参数服务器发送该平均值给它对应的所有工作进程，然后再等待……。试给出上述互动过程的MPI程序实现。（20分）
本试卷答题过程中可能用到的函数原型：MPI_Comm_size(MPI_Commcomm,int*size)MPI_Comm_rank(MPI_Commcomm,int*rank)
MPI_Allreduce(void*sendbuf,void*recvbuf,intcount,MPI_Datatypedatatype,MPI_Opop,MPI_Commcomm)MPI_Allgather(void*sendbuf,intsendcnt,MPI_Datatypesendtype,void*recvbuf,intrecvcnt,MPI_Datatyperecvtype,MPI_Commcomm)
MPI_Bcast(void*buffer,intcount,MPI_Datatypedatatype,introot,MPI_Commcomm)
MPI_Alltoall(void*sendbuf,intsendcount,MPI_Datatypesendtype,void*recvbuf,intrecvcount,MPI_Datatyperecvtype,MPI_Commcomm)
MPI_Send(void*buf,intcount,MPI_Datatypedatatype,intdest,inttag,MPI_Comm