中国科学技术大学
2007－2008学年第一学期考试试卷
《并行程序设计》期末考试参考解答
一、针对以下循环，（20分）
描述此循环中依赖关系和迭代依赖图；
给出并行化此循环的两种方案，并比较它们的并行粒度。
for(i=0;i10;i++)for(j=0;j10;j++)
a[i][j]=(a[i-1][j]+a[i+1][j])/2;
参考解答：
依赖关系：此循环中存在依赖向量为(1，0)的S?fS流依赖关系和依赖向量为（1，
0）的S?aS反依赖关系。
for(i=0;i10;i++)for(j=0;j10;j++)
S： a[i][j]=(a[i-1][j]+a[i+1][j])/2;
迭代依赖图如下：
此循环并行化可以参考如下两种方案：
方案1：直接并行化内层循环。内层循环满足循环并行化条件（不存在由该层携带的依赖关系）；但这样的并行化的粒度仅为一条语句，即语句S。
方案2：采用循环交换的程序变换。原程序变换为，
for(j=0;j10;j++)for(i=0;i10;i++)
S： a[i][j]=(a[i-1][j]+a[i+1][j])/2;
其依赖向量为（0，1），可以将外层j循环直接并行化。这样，并行化的粒度就是内层整个i循环。
二、以下OpenMP程序不能正确工作（线程总数大于1），请给出两种解决方案。（20分）
#pragmaompforprivate(i,j)for(i=0;i100;i++)
for(j=0;j10;j++)
a[i][j]=a[i-1][j+1];
参考解答：
该循环存在着依赖向量为（1，-1）的流依赖关系。根据循环并行化条件，不能直接并行化外层i循环。
有两种解决方案可以使用：
方案一：将原来对外层i循环的并行化改为对内层j循环的并行化（内层j循环满足循环并行化条件）；但此时并行化的只是内层j循环的10次迭代。修改后的程序如下：
for(i=0;i100;i++){#pragmaompforprivate(j)
for(j=0;j10;j++)
a[i][j]=a[i-1][j+1];
}
方案二：先对内层j循环采用循环逆转变换，此时，循环依赖向量为（1，1），然后在进行内外层循环交换的程序变换，这样可以将内层i循环并行化。对比方案一，此时可并行化的是内层i循环的100次迭代。变换后程序如下：
for(j=9;j=0;j--){#pragmaompforprivate(i)
for(i=0;i100;i++)
a[i][j]=a[i-1][j+1];
}
2007－2008学年第一学期《并行程序设计》期末考试 第1页(共1页)
三、在以下MPI程序片段中，矩阵A被划分为5X5的子矩阵，并由rank为0的进程将子矩阵发送给所有进程中的矩阵B（如图1所示，Pi表示第i个进程）；请补全此程序中划线部分的代码，并给出rank为0的进程接收所有进程中的矩阵B而重新建立矩阵A的代码。
P0P1P2P3P4
P0
P1
P2
P3
P4
P5
P6
P7
P8
P9
P10
P11
P12
P13
P14
P15
doubleA[20][20],B[5][5];
MPI_DatatypeSubMatrix_5X5;
MPI_Type_vector(, , , MPI_DOUBLE,SubMatrix_5X5);MPI_Type_commit(SubMatrix_5X5);
//发送子矩阵
if(rank==0) //rank为进程号
for(i=0;isize;i++)//size为进程总数
MPI_Send(, ,SubMatrix_5X5,i,0,MPI_COMM_WORLD);MPI_Recv(, , ,0,0,MPI_COMM_WORLD,stat);
参考解答：
图1子矩阵分布图
划线部分代码补全如下：
MPI_Type_vector(5, 5, 20, MPI_DOUBLE,SubMatrix_5X5);
MPI_Send(A[0][0]+(i/4)*100+5*(i%4), 1,
SubMatrix_5X5,i,0,MPI_COMM_WORLD);
MPI_Recv(B, 25, MPI_DOUBLE,0,0,MPI_COMM_WORLD,stat);
rank为0的进程接收所有进程中的矩阵B而重新建立矩阵A的代码如下：
MPI_Send(