中科大并行实践期末考试试题和答案

中 国 科 学 技 术 大 学

2011－2012学年第一学期考试试卷

参考答案

考试科目: 并行程序设计 得分:____ ______

学生所在系:___________ 姓名:____ _ _____ 学号:_____ ______

本试卷共五个大题！

一、 描述以下循环中的依赖关系及语句依赖图：（20分）

for i = 4 to 100 do

S: 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 f T，满足依赖关系的偶对集合为：

{ <S(i), T(j)> | i = j -1 ; 5≤j≤100 } ∪{ <S(i), T(j)> | i = j -3 ; 7≤j≤100 }

语句S流依赖于语句T，即T f S，满足依赖关系的偶对集合为：

{ <T(i), S(j)> | i = j -2 ; 6≤j≤100 }

语句S输出依赖于语句U，即 U o S ，满足依赖关系的偶对集合为：

{ <U(i), S(j)> | i = j -1 ; 5≤j≤100 }

语句T反依赖于语句U，即U a T ，满足依赖关系的偶对集合为：

{ <U(i), T(j)> | j = 2*i + 1 ; 4≤i≤49 }

语句依赖图如下：

中科大并行实践期末考试试题和答案

编写MPI程序：依据所有MPI进程运行所在节点集合的大小，进行

MPI_COMM_WORLD通信域划分，使得运行在相同节点上的MPI进程都将

被分到相同的子通信域。（20分）

参考解答：

基本思想是：

首先，每个进程均收集所有进程的运行节点信息（通过MPI_Allgather完成）； 其次，根据所有节点信息和自身的运行节点名，每个进程确定自己在该节点上的位序，即key；

最后，根据所有节点信息和自身的运行节点名，每个进程确定该节点名在所有节点信息中的第一次出现的位置，即color。

MPI程序主要部分如下：

int rank,Group_Size;

char host[128];

char *allhost; //存放所有节点名称字符串的数组；

int color,key;

MPI_Comm myComm, 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,大小为进程总数 X 128字节

gethostname(host, 128); // 获得MPI进程运行所在节点的名称

MPI_Allgather(host,128,MPI_BYTE,allhost,128,MPI_BYTE, myComm );

// 每个MPI进程收集全部进程运行节点名称，并按照MPI进程编号由小到大的顺序，

// 存到allhost数组。示例如下表所示：每个节点名占据128个字节。

// 进程编号（rank）为i的MPI进程运行所在节点名称，即host，应该存放在allhost

的第i项，即allhost的第i*128个字节偏移处存放的字符串。 2011－2012 学年第一学期 《并行程序设计》期末考试 第 1 页(共 1 页)

中科大并行实践期末考试试题和答案

//现在开始获得通信子域划分所需的color和key

color = 0; key = 0; // 初值为0

for(i=0;i<rank;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数组中确定第一个和其节点名称相同的进程所在位置，

// 并以此作为通信域划分中的COLOR。 // 如此一来，可以划分通信域了！

MPI_Comm_split(myComm, color, key, &nodeComm);

三、 MPI构造函数MPI_Type_indexed可从相同类型元素组成的连续数据区中

提取若干不同长度、不同索引位置的数据块组合为派生类型消息，其原型如下:

int MPI_Type_indexed(int count,int blocklens[],

int indices[],MPI_Datatype old_type,

MPI_Datatype *newtype )

参数含义如下：

count： 数据块的个数；也是参数indices和blocklens两个数组的有效长度。 blocklens：数组，存放每个块中类型为old_type的元素个数。

indices：数组，存放每个块的首元素在old_type数据区中的索引。

old_type：元素的基本类型。newtype ：新的派生消息类型。

设有二维矩阵int SA[N][N]。试写出MPI程序片段来定义：（20分）

（1）由下三角矩阵构成的派生消息类型lowTriangle;

（2）由主对角线（N个元素）及其上下两侧辅对角线（N-1元素）组成的

主条带派生消息类型mainStripe。

（3）编写两个MPI进程组成的程序，其中0号进程向1号进程发送

由SA[0][11]开始的5×5的上三角矩阵。

中科大并行实践期末考试试题和答案

参考解答：

依题意，主要是完成函数MPI_Type_indexed的参数填写工作。

（1） 由下三角矩阵构成的派生消息类型lowTriangle;

count=N; // 下三角矩阵包含N个数据块

for(i=0;i<N;i++) blocklens[i] = i+1;

//每块数据含1、2、…、N个数据

for(i=0;i<N;i++) indices[i] = i*N;

//每块首元素偏移从0、N、2*N…、(N-1)*N

MPI_Type_indexed(count,blocklens,indices,MPI_INT,&lowTria …… 此处隐藏：5132字，全部文档内容请下载后查看。喜欢就下载吧 ……