中国科学技术大学
2012－2013学年第一学期考试试卷
考试科目:并行程序设计 得分:
学生所在系:
姓名: _
学号:
本试卷共五个大题！
一、描述以下循环1中的依赖关系及语句依赖图，并尝试向量化变换：（15分）
for
fori=1to100do
S:A[i+1]=A[i+1]+B[i];
T:B[i+1]=C[i]+1;
U:A[i+1]=A[i]*C[i]+D[i];
endfor //循环1
二、判断循环2和循环3是否等价；并针对循环3，做出向量化变换和OpenMP
实现。（20分）
fori
fori=1toNdoA[i]=B[i]+1;
endfor
fori=1toNdoC[i]=A[i]/2;
endfor
fori=1toNdoD[i]=1/C[i+1];
endfor
//循环2
fori=1toNdoA[i]=B[i]+1;
C[i]=A[i]/2;
D[i]=1/C[i+1];
endfor
//循环3
三、以下为一个三进程的流水线。进程Q连续地从左边的进程P接收一个输入数据流X，计算一个新的Y值，然后将它发送给右边的进程R。
X=P(W)Z=R(Y)
X=P(W)
Z=R(Y)
Y=Q(X)
X
Y Z
请设计一个带有双缓冲方式的进程Q的流水线MPI程序框架，并使用非阻塞消息通信操作实现计算与通信的重叠。（15分）
四、将MPI_COMM_WORLD中所有进程视为二维p?p结构（p是进程总
p数且为平方数）。给出进程Pi，j(0?i,j? ?1)将其在MPI_COMM_WORLD
p
中编号rank分别循环下移i步，循环右移j步的MPI代码片段。（15分）
五、枚举排序（EnumerationSort）的具体思想是（假设按关键字递增排序），对每一个待排序的元素统计小于它的所有元素的个数，从而得到该元素最终处于序列中的位置。假定待排序的n个数存在a[1]…a[n]中。首先将a[1]
与a[2]…a[n]比较，记录比其小的数的个数，令其为k，a[1]就被存入有
序的数组b[1]…b[n]的b[k+1]位置上；然后将a[2]与a[1]，a[3]…a[n]
比较，记录比其小的数的个数，依此类推。
输入：a[1]
输入：a[1]…a[n]
输出：b[1]…b[n]
Begin
fori=1tondo
k=1
forj=1tondo
ifa[i]a[j]then
k=k+1
endifendfor
b[k]=a[i]
endfor
End//枚举排序串行算法
给出MPI并行实现。假设对一个长为n的输入序列使用n个处理器进行排序，只需是每个处理器负责完成对其中一个元素的定位，然后将所有的定位信息集中到主进程中，由主进程负责完成所有元素的最终排位。（20分）
给出OpenMP实现。（15分）
本试卷答题过程中可能用到的函数原型：
本试卷答题过程中可能用到的函数原型：
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_Allgather(void*sendbuf,intsendcount,MPI_Datatypesendtype,void*recvbuf,intrecvcount,MPI_Datatyperecvtype,MPI_Commcomm)
MPI_Send(void*buf,intcount,MPI_Datatypedatatype,intdest,inttag,MPI_Commcomm)
MPI_Isend(void*buf,intcount,MPI_Datatypedatat