分布存储并行算法的MPI实现PPT课件

2020/5/4,.,1,分布存储并行算法的MPI实现,MPI程序的一般结构MPI中的拓扑结构与嵌入将计算与通信重叠利用自定义数据类型与数据封装减少通信次数聚合通信与计算通信器中进程组的获取MPI中墙上时间的获取,2020/5/4,.,2,1.MPI程序的一般结构,6个基本函数MPI程序的一般结构用MPI_Send与MPI_Recv时的死锁避免同时发送与接收一个简单的MPI程序实例,2020/5/4,.,3,MPI函数与常量的命名规则,Fortran中不分大小写，以mpi_开头Fortran中任何MPI对象与常数都只需要说明为整型C中的函数以MPI_开头，后续第一个字母大写，其它字母小写。该规则也适用于对象类型说明。C中常量的字母全用大写,2020/5/4,.,4,6个基本函数,intMPI_Init(int*argc,char*argv)intMPI_Comm_size(MPI_Commcomm,int*size)intMPI_Comm_rank(MPI_Commcomm,int*rank)intMPI_Send(void*buf,intcount,MPI_Datatypedatatype,intdest,inttag,MPI_Commcomm)intMPI_Recv(void*buf,intcount,MPI_Datatypedatatype,intsource,inttag,MPI_Commcomm,MPI_Status*status)intMPI_Finalize(),2020/5/4,.,5,MPI程序的一般结构,2020/5/4,.,6,用MPI_Send与MPI_Recv时的死锁避免,inta10,b10,myrank;MPI_Statusstatus;MPI_Comm_rank(MPI_COMM_WORLD,myrank);if(myrank=0)MPI_Send(a,10,MPI_INT,1,1,MPI_COMM_WORLD);MPI_Send(b,10,MPI_INT,1,2,MPI_COMM_WORLD);elseif(myrank=1)MPI_Recv(b,10,MPI_INT,0,2,MPI_COMM_WORLD,在MPI_Send采用缓冲区实现时，只要缓冲区足够大，以上程序可以正确执行。在采用阻塞方式实现时，将死锁,2020/5/4,.,7,用MPI_Send与MPI_Recv时的死锁避免(续）,inta10,b10,p,ip;MPI_Statusstatus;MPI_Comm_size(MPI_COMM_WORLD,p);MPI_Comm_rank(MPI_COMM_WORLD,ip);MPI_Send(a,10,MPI_INT,(ip+1)%p,1,MPI_COMM_WORLD);MPI_Recv(b,10,MPI_INT,(ip-1+p)%p,1,MPI_COMM_WORLD,以上程序同样不安全，因为程序的正确性与MPI_Send的实现方式有关。对这种不安全性，可以通过将进程分组，所有奇数号进程分为一组，所有偶数号进程分为一组，奇数号进程先发送后接受，偶数号进程先接收后发送的方式来消除。,2020/5/4,.,8,同时发送与接收,MPI提供了同时发送与接收的函数，可以避免前面的死锁现象intMPI_Sendrecv(void*sendbuf,intsendcount,MPI_Datatypesendtype,intdest,intsendtag,void*recvbuf,intrecvcount,MPI_Datatyperecvtype,intsour,intrecvtag,MPI_Commcomm,MPI_Status,*status)intMPI_Sendrecv_replace(void*buf,intcount,MPI_Datatypedatatype,intdest,intsendtag,intsour,intrecvtag,MPI_Commcomm,MPI_Status,*status),2020/5/4,.,9,一个简单的MPI程序实例,include/usr/local/mpich-1.2.5/include/mpif.hintegerx,comm,p,myrank,ierror,status(mpi_status_size)callmpi_init(ierror)callmpi_comm_dup(mpi_comm_world,comm,ierror)callmpi_comm_size(comm,p,ierror)callmpi_comm_rank(comm,myrank,ierror)if(myrank.eq.0)thenx=10callmpi_send(x,mpi_integer,1,myrank+1,100,comm,ierror)elseif(myrank.eq.p-1)thencallmpi_recv(x,mpi_integer,1,myrank-1,100,comm,status,ierror)elsecallmpi_recv(x,mpi_integer,1,myrank-1,100,comm,status,ierror)callmpi_send(x,mpi_integer,1,myrank+1,100,comm,ierror)endifcallmpi_finalize(ierror)end,2020/5/4,.,10,2.MPI中的拓扑结构与嵌入,利用MPI_Init初始化后，MPI将所有进程看成一个线性阵列，进程从0到p-1标号在许多并行算法中，进程之间需要组织为高维拓扑结构，如Cannon算法将一维阵列中的进程映射到高维阵列时，有很多种映射方式，例如附图列出了4种方式程序员可以利用MPI的函数将进程组织成任何逻辑拓扑结构，而不需要以显式的方式指明哪些进程应该映射到哪些处理器上,2020/5/4,.,11,2.MPI中的拓扑结构与嵌入(续),2020/5/4,.,12,2.MPI中的拓扑结构与嵌入(续),建立Cartesian拓扑结构intMPI_Cart_create(MPI_Commcomm_old,intndims,int*dims,int*periods,intreorder,MPI_Comm*comm_cart)ndims为维数，dims为各维中的结点数量periodsk=0指明第k维不带环，否则带环reorder=0指明不对拓扑结构上的进程进行重新排序，否则将重新排序comm_cart是新得到的包含拓扑结构信息与comm中信息的通信器,2020/5/4,.,13,2.MPI中的拓扑结构与嵌入(续),Cartesian拓扑结构的使用intMPI_Cart_rank(MPI_Commcomm_cart,int*coords,int*rank)对由coords给出的拓扑结构中坐标，获取对应进程的进程号rankintMPI_Cart_coord(MPI_Commcomm_cart,intrank,intmaxdims,int*coords)对给定的进程号rank，获取其在拓扑结构中的位置坐标coords，其中maxdims不能小于实际的维数intMPI_Cart_shift(MPI_Commcomm_cart,intdir,ints_step,int*rank_source,int*rank_dest)dir指明沿哪一维进行数据移动，如dir=0表示沿第0维移动；s_step标识往正方向移动时的步长(边数)，为负表示沿负方向移动；rank_source表示移动时本进程的源进程号；rank_dest表示移动时本进程的目的进程号.,2020/5/4,.,14,2.MPI中的拓扑结构与嵌入(续),Cannon算法图示,2020/5/4,.,15,2.MPI中的拓扑结构与嵌入(Cannon算法),voidMatMatCannon(intn,double*a,double*b,double*c,MPI_Commcomm)intk,nlocal,p,dims2,periods2,myrank,my2drank,mycoords2;intuprank,downrank,leftrank,rightrank,coords2,shiftsource,shiftdest;MPI_Statusstatus;MPI_Commcomm_2d;MPI_Comm_size(comm,2020/5/4,.,16,2.MPI中的拓扑结构与嵌入(Cannon算法),MPI_Cart_shift(comm_2d,1,-mycoords1,2020/5/4,.,17,3.将计算与通信重叠,非阻塞式通信操作intMPI_Irecv(void*buf,intcount,MPI_Datatypedatatype,intsour,inttag,MPI_Commcomm,MPI_Request*request)intMPI_Isend(void*buf,intcount,MPI_Datatypedatatype,intdest,inttag,MPI_Commcomm,MPI_Request*request)intMPI_Test(MPI_Request*request,int*flag,MPI_Status*status)intMPI_Wait(MPI_Request*request,MPI_Status*status)intMPI_Request_free(MPI_Request*request),2020/5/4,.,18,3.将计算与通信重叠(续),利用非阻塞式通信操作避免死锁,inta10,b10,myrank;MPI_Requestreqs2;MPI_Comm_rank(MPI_COMM_WORLD,myrank);if(myrank=0)MPI_Send(a,10,MPI_INT,1,1,MPI_COMM_WORLD);MPI_Send(b,10,MPI_INT,1,2,MPI_COMM_WORLD);elseif(myrank=1)MPI_Irecv(b,10,MPI_INT,0,2,MPI_COMM_WORLD,2020/5/4,.,19,3.将计算与通信重叠(Cannon算法),voidMatMatCannon_nblock(intn,double*a,double*b,double*c,MPI_Commcomm)intk,j,nlocal,p,dims2,periods2,myrank,my2drank,mycoords2;intuprank,downrank,leftrank,rightrank,coords2,shiftsource,shiftdest;double*a_buffers2,*b_buffers2;MPI_Statusstatus;MPI_Commcomm_2d;MPI_Requestreqs4;MPI_Comm_size(comm,2020/5/4,.,20,3.将计算与通信重叠(Cannon算法),MPI_Cart_shift(comm_2d,0,-mycoords0,2020/5/4,.,21,3.将计算与通信重叠(Cannon算法),MPI_Cart_shift(comm_2d,0,+mycoords0,2020/5/4,.,22,4.用自定义数据类型与数据封装减少通信次数,MPI中的基本数据类型,2020/5/4,.,23,4.用自定义数据类型与数据封装减少通信次数(续),自定义数据类型时常用的函数MPI_Type_contiguousMPI_Type_vector与MPI_Type_hvectorMPI_Type_indexed与MPI_Type_hindexedMPI_Type_structMPI_Type_commit与MPI_Type_free,2020/5/4,.,24,MPI_Type_contiguous,intMPI_Type_contiguous(intcount,MPI_Datatypeoldtype,MPI_Datatye*newtype)当count=4时，该函数的功能可以用下图来描述,2020/5/4,.,25,MPI_Type_vector与MPI_Type_hvector,intMPI_Type_vector(intcount,intblocklength,intstride,MPI_Datatypeoldtype,MPI_Datatype*newtype)intMPI_Type_hvector(intcount,intblocklength,intstride,MPI_Datatypeoldtype,MPI_Datatype*newtype)当count=3，blocklength=2，stride=3时MPI_Type_vector的功能可以描述如下图,2020/5/4,.,26,MPI_Type_indexed与MPI_Type_hindexed,intMPI_Type_indexed(intcount,int*blocklengths,int*displacements,MPI_Datatypeoldtype,MPI_Datatype*newtype)intMPI_Type_hindexed(intcount,int*blocklengths,int*displacements,MPI_Datatypeoldtype,MPI_Datatype*newtype)当count=3，blocklengths=2,3,1，displacements=0,3,8时MPI_Type_indexed的功能可以描述如下,2020/5/4,.,27,MPI_Type_struct,intMPI_Type_struct(intcount,int*blocklengths,MPI_Aint*displacements,MPI_Datatype*oldtypes,MPI_Datatype*newtype)当count=3，blocklengths=2,1,3，oldtypes=MPI_INTEGER,MPI_DOUBLE_PRECISION,MPI_BYTE，displacements=0,9,18时，该函数的功能可以用下图来描述,2020/5/4,.,28,MPI_Type_commit与MPI_Type_free,intMPI_Type_commit(MPI_Datatype*datatype)intMPI_Type_free(MPI_Datatype*datatype)注意，在定义了一个新的数据类型后，必须先调用MPI_Type_commit，才能使用该数据类型,2020/5/4,.,29,4.用自定义数据类型与数据封装减少通信次数(续),数据封装与拆卸适用于自定义数据类型利用率很低时的情形intMPI_Pack(void*inbuf,intincount,MPI_Datatypedatatype,void*outbuf,intoutsize,int*position,MPI_Commcomm)intMPI_Unpack(void*inbuf,intinsize,int*position,void*outbuf,intoutcount,MPI_Datatypedatatype,MPI_Commcomm)拆卸时的顺序必须与进行封装时的顺序一致,2020/5/4,.,30,5.聚合通信与计算,同步intMPI_Barrier(MPI_Commcomm)一对多广播intMPI_Bcast(void*buf,intcount,MPI_Datatypedatatype,intsource,MPI_Commcomm)多对一归约intMPI_Reduce(void*sendbuf,void*recvbuf,intcount,MPI_Datatypedatatype,MPI_Opop,inttarget,MPI_Commcomm),2020/5/4,.,31,5.聚合通信与计算(续),多进程归约intMPI_Allreduce(void*sendbuf,void*recvbuf,intcount,MPI_Datatypedatatype,MPI_Opop,MPI_Commcomm)多对多归约intMPI_Reduce_scatter(void*sendbuf,void*recvbuf,int*recvcounts,MPI_Datatypedatatype,MPI_Opop,MPI_Commcomm)op可为MPI_MAX、MPI_MIN、MPI_SUM、MPI_PROD、MPI_LAND、MPI_LOR、MPI_LXOR、MPI_BAND、MPI_BOR、MPI_BXOR、MPI_MAXLOC、MPI_MINLOC,2020/5/4,.,32,5.聚合通信与计算(续),前缀操作intMPI_Scan(void*sendbuf,void*recvbuf,intcount,MPI_Datatypedatatype,MPI_Opop,MPI_Commcomm)收集intMPI_Gather(void*sendbuf,intsendcount,MPI_Datatypesenddatatype,void*recvbuf,intrecvcount,MPI_Datatyperecvdatatype,inttarget,MPI_Commcomm)intMPI_Gatherv(void*sendbuf,intsendcount,MPI_Datatypesenddatatype,void*recvbuf,int*recvcounts,int*displs,MPI_Datatyperecvdatatype,inttarget,MPI_Commcomm),2020/5/4,.,33,5.聚合通信与计算(续),多对多广播intMPI_Allgather(void*sendbuf,intsendcount,MPI_Datatypesenddatatype,void*recvbuf,intrecvcount,MPI_Datatyperecvdatatype,MPI_Commcomm)intMPI_Allgatherv(void*sendbuf,intsendcount,MPI_Datatypesenddatatype,void*recvbuf,int*recvcounts,int*displs,MPI_Datatyperecvdatatype,MPI_Commcomm),2020/5/4,.,34,5.聚合通信与计算(续),分散intMPI_Scatter(void*sendbuf,intsendcount,MPI_Datatypesenddatatype,void*recvbuf,intrecvcount,MPI_Datatyperecvdatatype,intsource,MPI_Commcomm)intMPI_Scat