2024-2025-并行程序设计期末考试卷

中 国 科 学 技 术 大 学20242024学年第一学期考试试卷考试科目: 并行程序设计 得分:_ _ 学生所在系:_ _ 姓名:_ _ _ 学号:_ _ _一、 分析以下3个循环中存在的依靠关系；分别通过循环交换、分布和逆转等多种方法来尝试向量化和/或并行化变换：（310=30分）for i = 1 to 100 do /循环1 Ai = Ai + Bi-1; Bi = Ci-1 * 2 ; Ci = 1 / Bi ; Di = Ci * Ci ;endfor for i = 1 to 999 do / 循环2 Ai = Bi + Ci; Di = ( Ai + A 999-i+1 ) / 2 ;endfor for i = 1 to 100 do / 循环3 for j = 1 to 100 do A3*i+2*j, 2*j = Ci,j * 2 ;Di,j = Ai-j+6, i+j ; endforendfor 二、 假设某种MPI广播通信方案如下：将P个进程看作的二维拓扑结构，并且将各个行或列进程组划分为单独的子通信域。这样，root进程可先在其行子通信域中进行广播，然后该行中的全部进程在各自的列通信子域中再广播。给出该广播方案的MPI详细实现。（20分）三、 设有两个进程A和B，以及结构变量stu。现在，进程A将stu发送给进程B。请用三种不同的MPI实现来完成进程A的发送操作。（310=30分）struct Student int id; char name10;double mark3; char pass; stu;四、 以下是单处理器上的矩阵求逆算法：Beginfor i=1 to n do(1) ai,i=1/ai,i(2)for j=1 to n do if (ji) then ai,j=ai,j*ai,i end if end for (3)for k=1 to n do for j=1 to n do if (ki and ji) then ak,j=ak,j-ak,i*ai,j end if end forend for (4)for k=1 to n do if (ki) then ak,i= -ak,i*ai,i end if end for end forEnd矩阵求逆的过程中，依次利用主行i(i=0,1,n-1)对其余各行j(ji)作初等行变换，由于各行计算之间没有数据相关关系，因此可以对矩阵A按行划分来实现并行计算。考虑到在计算过程中处理器之间的负载均衡，对A采纳行交叉划分：设处理器个数为p，矩阵A的阶数为n，对矩阵A行交叉划分后，编号为i(i=0,1,p-1)的处理器存有A的第i, i+p, i+(m-1)p行。在计算中，依次将第0,1,n-1行作为主行，将其广播给全部处理器，这事实上是各处理器轮番选出主行并广播。发送主行数据的处理器利用主行对其主行之外的m-1行行向量做行变换，其余处理器则利用主行对其m行行向量做行变换。请写出矩阵求逆算法的MPI并行实现。（20分）本试卷答题过程中可能用到的函数原型：MPI_Comm_size( MPI_Comm comm, int *size )MPI_Comm_rank( MPI_Comm comm, int *rank )MPI_Reduce(void *sendbuf, void *recvbuf, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm)MPI_Bcast( void *buffer, int count, MPI_Datatype datatype, int root, MPI_Comm comm )MPI_Gather(void *sendbuf, int sendcnt, MPI_Datatype sendtype, void *recvbuf, int recvcnt, MPI_Datatype recvtype, int root, MPI_Comm comm)MPI_Send(void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm)MPI_Recv(void *buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status *status)MPI_Sendrecv(void *sendbuf, int sendcount, MPI_Datatype sendtype,int dest, int sendtag, void *recvbuf, int recvcount, MPI_Datatype recvtype, int source, int recvtag, MPI_Comm comm, MPI_Status *status)MPI_Pack(void *buf, int count, MPI_Datatype type, void* packBuf,int packSize,int *Position,MPI_Comm comm)MPI_Pack_size(int incount, MPI_Datatype datatype,MPI_Comm comm,int *size)MPI_Type_vector(int count, int blocklength, int stride, MPI_Datatype old_type, MPI_Datatype *newtype_p) MPI_Comm_dup(MPI_Comm comm, MPI_Comm *newcomm)MPI_Comm_split(MPI_Comm comm, int color, int key, MPI_Comm *newcomm)MPI_Wait(MPI_Request *request, MPI_Status *status)MPI_Type_struct(int count,int blocklens,MPI_Aint indices,MPI_Datatype old_types, MPI_Datatype *newtype)MPI_Address( void *location, MPI_Aint *address )MPI_Type_commit(MPI_Datatype *datatype)20242024 学年第一学期 并行程序设计期末考试 第 1 页(共 2页)