2014-2015-并行程序设计期末考试卷

2014－2015学年第一学期《并行程序设计》期末考试第1页(共2页)中国科学技术大学2014－2015学年第一学期考试试卷考试科目:并行程序设计得分:_________学生所在系:___________姓名:______学号:___________一、分析以下3个循环中存在的依赖关系；分别通过循环交换、分布和逆转等多种方法来尝试向量化和/或并行化变换：（3×10=30分）二、假设某种MPI广播通信方案如下：将P个进程看作pp的二维拓扑结构，并且将各个行或列进程组划分为单独的子通信域。这样，root进程可先在其行子通信域中进行广播，然后该行中的所有进程在各自的列通信子域中再广播。给出该广播方案的MPI具体实现。（20分）三、设有两个进程A和B，以及结构变量stu。现在，进程A将stu发送给进程B。请用三种不同的MPI实现来完成进程A的发送操作。（3×10=30分）structStudent{intid;charname[10];doublemark[3];charpass;}stu;fori=1to100do//循环1A[i]=A[i]+B[i-1];B[i]=C[i-1]*2;C[i]=1/B[i];D[i]=C[i]*C[i];endforfori=1to999do//循环2A[i]=B[i]+C[i];D[i]=(A[i]+A[999-i+1])/2;endforfori=1to100do//循环3forj=1to100doA[3*i+2*j,2*j]=C[i,j]*2;D[i,j]=A[i-j+6,i+j];endforendfor2014－2015学年第一学期《并行程序设计》期末考试第2页(共2页)四、以下是单处理器上的矩阵求逆算法：Beginfori=1tondo(1)a[i,i]=1/a[i,i](2)forj=1tondoif(j≠i)thena[i,j]=a[i,j]*a[i,i]endifendfor(3)fork=1tondoforj=1tondoif((k≠iandj≠i))thena[k,j]=a[k,j]-a[k,i]*a[i,j]endifendforendfor(4)fork=1tondoif(k≠i)thena[k,i]=-a[k,i]*a[i,i]endifendforendforEnd矩阵求逆的过程中，依次利用主行i(i=0,1,…,n-1)对其余各行j(j≠i)作初等行变换，由于各行计算之间没有数据相关关系，因此可以对矩阵A按行划分来实现并行计算。考虑到在计算过程中处理器之间的负载均衡，对A采用行交叉划分：设处理器个数为p，矩阵A的阶数为n，pnm/，对矩阵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_Commcomm,int*size)MPI_Comm_rank(MPI_Commcomm,int*rank)MPI_Reduce(void*sendbuf,void*recvbuf,intcount,MPI_Datatypedatatype,MPI_Opop,introot,MPI_Commcomm)MPI_Bcast(void*buffer,intcount,MPI_Datatypedatatype,introot,MPI_Commcomm)MPI_Gather(void*sendbuf,intsendcnt,MPI_Datatypesendtype,void*recvbuf,intrecvcnt,MPI_Datatyperecvtype,introot,MPI_Commcomm)MPI_Send(void*buf,intcount,MPI_Datatypedatatype,intdest,inttag,MPI_Commcomm)MPI_Recv(void*buf,intcount,MPI_Datatypedatatype,intsource,inttag,MPI_Commcomm,MPI_Status*status)MPI_Sendrecv(void*sendbuf,intsendcount,MPI_Datatypesendtype,intdest,intsendtag,void*recvbuf,intrecvcount,MPI_Datatyperecvtype,intsource,intrecvtag,MPI_Commcomm,MPI_Status*status)MPI_Pack(void*buf,intcount,MPI_Datatypetype,void*packBuf,intpackSize,int*Position,MPI_Commcomm)MPI_Pack_size(intincount,MPI_Datatypedatatype,MPI_Commcomm,int*size)MPI_Type_vector(intcount,intblocklength,intstride,MPI_Datatypeold_type,MPI_Datatype*newtype_p)MPI_Comm_dup(MPI_Commcomm,MPI_Comm*newcomm)MPI_Comm_split(MPI_Commcomm,intcolor,intkey,MPI_Comm*newcomm)MPI_Wait(MPI_Request*request,MPI_Status*status)MPI_Type_struct(intcount,intblocklens[],MPI_Aintindices[],MPI_Datatypeold_types[],MPI_Datatype*newtype)MPI_Address(void*location,MPI_Aint*address)MPI_Type_commit(MPI_Datatype*datatype)