中国科学技术大学
2010－2011学年第一学期考试试卷
参考解答
考试科目:并行程序设计 得分:
学生所在系:
姓名: _
学号:
本试卷共五个大题！
一、（1）针对如下双重循环：
forI=1to5doforJ=1to5do
S: A(I,J)=A(I-1,J)+A(I,J-1)
endforendfor
给出该双重循环的迭代依赖图；（10分）
分析该双重循环向量化或并行化的情况（5分）。参考解答：
原双重循环中存在依赖方向向量为（1，0）和（0，1）的流依赖关系。因此，迭代依赖图如下（部分）：
i
1 2 3 4
1
j
2
3
4
由上面的迭代依赖图可看出：无论是外层i循环，还是内层j循环均可携带跨迭代的依赖关系。故而双重循环的每一层均不能实施并行化。
由（0，1）的S?S流依赖关系知，内层循环j不能实施向量化！
若把（1）中的双重循环改为：
forI=1to5do
forJ=I+1toI+5do
S: A(I,J-I)=A(I-1,J-I)+A(I,J-I-1)
endforendfor
试给出修改后的双重循环的迭代依赖图。（10分）
分析该修改后的双重循环并行化的情况。如能实施并行，请给出相应的OpenMP实现。（5分）。
参考解答：
修改后的循环，就是对原来循环做了拉伸系数为1的变换。变换后，迭代依赖图示意如下：（部分）
j
1 2 3 4 5 6 7 8
1
2
3
4
由上图可见，对相同j值，沿i方向的计算无相关关系，因此交换i，j循环先后次序，i循环可并行执行。即，经过拉伸变换，修改后的双重循环中的依赖关系为：（1，1）和（0，1）。通过循环交换，可以得到（1，1）和（1，0）依赖关系，这样，交换到外层的循环j依然不可并行，但交换到内层的循环i则可以实施并行！
修改后得到并行程序如下：
forj=2to10do
fori=max(1,j-5)tomin(5,j-1)par-doa[i,j-i]=a[i-1,j-i]+a[i,j-i-1]
endforendfor
其中上述程序的par-do部分，可以采用OpenMP的并行域编译制导来进行多线程并行化！
for(j=2;j=10;j++)
{
#pragmaompparallelforprivate(i)
for(i=max(1,j-5);i=min(5,j-1);i++)a[i][j-i]=a[i-1][j-i]+a[i][j-i-1];
}
二、针对数组doubleA[100]，设计两种不同MPI实现，均可一次性发送数组A中所有奇数编号的元素。（15分）
2010－2011学年第一学期《并行程序设计》期末考试 第1页(共1页)
参考解答：
MPI_Pack函数调用方式：
doubleA[100];
MPI_Pack_size(50,MPI_DOUBLE,comm,BufferSize);TempBuffer=malloc(BufferSize);
j=sizeof(MPI_DOUBLE);Position=0;
for(i=0;i50;i++)
MPI_Pack(A+1+i*j,1,MPI_DOUBLE,TempBuffer,BufferSize,Position,comm);
MPI_Send(TempBuffer,Position,MPI_PACKED,destination,tag,comm);
MPI_Type_vector构造新类型：
doubleA[100];MPI_DatatypeEvenElements;
···
MPI_Type_vector(50,1,2,MPI_DOUBLE,EvenElements);MPI_Type_commit(EvenElements);
MPI_Send(A+1,1,EvenElements,destination,···);
三、向量化以下循环：（10分）
forI=2toNdo
S1: A(I)=B(I)+C(I+1)
S2: D(I)=A(I+1)+1
S3: C(I)=D(I)
Endfor
参考解答：
上述循环中依赖关系为：S2?aS1S1?aS3和S2