中国科学技术大学
2008－2009学年第一学期考试试卷
考试科目:并行程序设计 得分:
学生所在系:
姓名: _
学号:
一、给出以下循环中的迭代依赖图。（10分）
for(k=0;kN;k++){
a[k][k]=sqrt(a[k][k]);for(i=k+1;iN;i++){
a[i][k]=a[i][k]/a[k][k];for(j=k+1;jN;j++){
a[i][j]=a[i][j]-a[i][k]*a[k][j]/a[k][k];
}
}
}
二、分别考查以下循环中的依赖关系以及可向量化和可并行化情况（40分）
forI=2toN–1doforJ=2toN–1do
S: A(I,J)=B(I–1,J)+C
T: B(I,J)=A(I,J–1)*2
endforendfor
forI=1toNdo
forJ=1toNdo
: D(I,J) =A(I,J)+C
: A(I+1,J+1)=B(I,J)*2
endforendfor
三、给出以下程序的MPI并行实现。假设数组a的顺序分布于各计算进程（不必给出数据分发、空间分配以及结果收集的代码）。（20分）
for(j=0;j100000;j++)for(i=2;i10000;i++)
a[i]=sin(a[i]-a[i-1])+cos(a[i]+a[i-2]);
四、仔细阅读以下程序代码（30分）
给出OpenMP并行化实现（尽可能多地采用多线程并行化）；
给出MPI并行化实现；假设：数组a采用行连续划分方式顺序分布于各计算进程，数组x的初值也被广播到各个进程（不必写数据分布与最后结果的回收代码了）。
注：在上述两种实现里，可以添加适当的变量及操作。
#defineN5000
#defineepsilon1e-5//10-5
doublex[N],newx[N],a[N][N],b[N],diff;inti,j;
main(){
……//a,b的初始化；
for(i=0;iN;i++)x[i]=b[i]/a[i][i];//设置数组x的初值
diff=epsilon;
while(diff=epsilon)do{diff=0;
for(i=0;iN;i++){
newx[i]=b[i];
for(j=0;jN;j++){
if(j!=i)newx[i]=newx[i]-a[i][j]*x[j];
}
newx[i]=newx[i]/a[i][i];
}
for(i=0;iN;i++){
diff=max(diff,fabs(newx[i]-x[i]));x[i]=newx[i];
}//设max为求最大值函数，而fabs为求绝对值函数。
}
……//输出x[i]
}
可能用到的MPI函数原型：
MPI_Send(buf,count,datatype,dest,tag,comm);
MPI_Recv(buf,count,datatype,source,tag,comm,MPI_Status*status);MPI_Bcast(buf,count,datatype,root,comm)；
MPI_Allgather(sendbuf,sendcount,sendtype,recvbuf,recvcount,recvtype,comm);
MPI_Allreduce(sendbuf,recvbuf,count,datatype,MPI_Opop,comm);
2008－2009学年第一学期《并行程序设计》期末考试 第1页(共1页)