中国科学技术大学
2011－2012学年第一学期考试试卷参考答案
考试科目:并行程序设计 得分:
学生所在系:
姓名: _
学号:
本试卷共五个大题！
一、描述以下循环中的依赖关系及语句依赖图：（20分）
fori=4to100doS:A(i)=B(i)+c(i)
T:B(i+2)=A(i-1)+A(i-3)+C(i-1)
U:A(i+1)=B(2*i+3)+1
endfor
参考解答:
循环中语句依赖关系如下：
语句T流依赖于语句S，即S?fT，满足依赖关系的偶对集合为：
{S(i),T(j)|i=j-1; 5≤j≤100}∪{S(i),T(j)|i=j-3; 7≤j≤100}
语句S流依赖于语句T，即T?fS，满足依赖关系的偶对集合为：
{T(i),S(j)|i=j-2; 6≤j≤100}
语句S输出依赖于语句U，即U?oS，满足依赖关系的偶对集合为：
{U(i),S(j)|i=j-1; 5≤j≤100}
语句T反依赖于语句U，即U?aT，满足依赖关系的偶对集合为：
{U(i),T(j)|j=2*i+1; 4≤i≤49}
语句依赖图如下：
二、编写MPI程序：依据所有MPI进程运行所在节点集合的大小，进行
MPI_COMM_WORLD通信域划分，使得运行在相同节点上的MPI进程都将被分到相同的子通信域。（20分）
参考解答：基本思想是：
首先，每个进程均收集所有进程的运行节点信息（通过MPI_Allgather完成）；
其次，根据所有节点信息和自身的运行节点名，每个进程确定自己在该节点上的位序，即key；
最后，根据所有节点信息和自身的运行节点名，每个进程确定该节点名在所有节点信息中的第一次出现的位置，即color。
MPI程序主要部分如下：
intrank,Group_Size;charhost[128];
char*allhost;//存放所有节点名称字符串的数组；
intcolor,key;
MPI_CommmyComm,nodeComm;
……
MPI_Init(argc,argv);//MPI初始化
MPI_Comm_dup(MPI_COMM_WORLD,myComm);//复制MPI_COMM_WORLD通信域
MPI_Comm_rank(myComm,rank);MPI_Comm_size(myComm,Group_Size);allhost=(char*)malloc(128*Group_Size);
//分配节点名数组空间allhost,大小为进程总数X128字节
gethostname(host,128);//获得MPI进程运行所在节点的名称
MPI_Allgather(host,128,MPI_BYTE,allhost,128,MPI_BYTE,myComm);
//每个MPI进程收集全部进程运行节点名称，并按照MPI进程编号由小到大的顺序，
//存到allhost数组。示例如下表所示：每个节点名占据128个字节。
rank
0
1
2
3
4
5
6
……
allhost
Node0
Node0
Node3
Node4
Node5
Node4
Node4
……
//进程编号（rank）为i的MPI进程运行所在节点名称，即host，应该存放在allhost
的第i项，即allhost的第i*128个字节偏移处存放的字符串。
2011－2012学年第一学期《并行程序设计》期末考试 第1页(共1页)
//现在开始获得通信子域划分所需的color和keycolor=0;key=0;//初值为0for(i=0;irank;i++){
//每个进程统计在编号小于它的进程中，有多少和其节点名称相同；if(strcmp(allhost+i*128,host))continue;//不同，则下一个进程else key++;//相同，key增一。
}//循环结束，key即为当前进程的所在通信域的编号（KEY）
for(i=0;i=rank;i++){if(!strcmp(allhost+i*128,host))break;
//节点名称相同，则跳出循环
}
color=i;//对于rank＝＝0的主进程而言，总是color为0。
//每个进程在allhost数组中确定第一个和其节