分布存储并行算法MPI实现

分布存储并行算法的MPI实现MPI程序的一般结构MPI中的拓扑结构与嵌入将计算与通信重叠利用自定义数据类型与数据封装减少通信次数聚合通信与计算通信器中进程组的获取MPI中墙上时间的获取2024/4/111.MPI程序的一般结构6个基本函数MPI程序的一般结构用MPI_Send与MPI_Recv时的死锁避免同时发送与接收一个简单的MPI程序实例2024/4/12MPI函数与常量的命名规则Fortran中不分大小写，以mpi_开头Fortran中任何MPI对象与常数都只需要说明为整型C中的函数以MPI_开头，后续第一个字母大写，其它字母小写。该规则也适用于对象类型说明。C中常量的字母全用大写2024/4/136个基本函数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()

2024/4/14MPI程序的一般结构include‘/usr/local/mpich-1.2.5/include/mpi.h’main(intargc,char*argv[]){参数说明;MPI_Init(&argc,&argv)；MPI_Comm_dup(MPI_COMM_WORLD,&comm)；MPI_Comm_size(comm,&size)；MPI_Comm_rank(comm,&rank)；建立新的进程拓扑结构和新的通信器应用程序主体：包括计算与控制；进程间通信，如MPI_Send(buf,datatype,nelem,dest,tag,comm)；MPI_Recv(buf,datatype,nelem,sour,tag,comm,&status)；MPI_Finalize()；}2024/4/15用MPI_Send与MPI_Recv时的死锁避免inta[10],b[10],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,&status);MPI_Recv(a,10,MPI_INT,0,1,MPI_COMM_WORLD,&status);}…在MPI_Send采用缓冲区实现时，只要缓冲区足够大，以上程序可以正确执行。在采用阻塞方式实现时，将死锁2024/4/16用MPI_Send与MPI_Recv时的死锁避免(续）inta[10],b[10],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,&status);…

以上程序同样不安全，因为程序的正确性与MPI_Send的实现方式有关。对这种不安全性，可以通过将进程分组，所有奇数号进程分为一组，所有偶数号进程分为一组，奇数号进程先发送后接受，偶数号进程先接收后发送的方式来消除。2024/4/17同时发送与接收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)

2024/4/18一个简单的MPI程序实例include‘/usr/local/mpich-1.2.5/include/mpif.h’integerx,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)end2024/4/192.MPI中的拓扑结构与嵌入利用MPI_Init初始化后，MPI将所有进程看成一个线性阵列，进程从0到p-1标号在许多并行算法中，进程之间需要组织为高维拓扑结构，如Cannon算法将一维阵列中的进程映射到高维阵列时，有很多种映射方式，例如附图列出了4种方式程序员可以利用MPI的函数将进程组织成任何逻辑拓扑结构，而不需要以显式的方式指明哪些进程应该映射到哪些处理器上2024/4/1102.MPI中的拓扑结构与嵌入(续)01234567891011121314150481215913261014371115(a)先行后列映射(b)先列后行映射03451276141389151211100132457612131514891110(c)空间曲线填充(d)超立方体映射2024/4/1112.MPI中的拓扑结构与嵌入(续)建立Cartesian拓扑结构intMPI_Cart_create(MPI_Commcomm_old,intndims,

int*dims,int*periods,intreorder,

MPI_Comm*comm_cart)

ndims为维数，dims为各维中的结点数量periods[k]=0指明第k维不带环，否则带环reorder=0指明不对拓扑结构上的进程进行重新排序，否则将重新排序comm_cart是新得到的包含拓扑结构信息与comm中信息的通信器2024/4/1122.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表示移动时本进程的目的进程号.

2024/4/1132.MPI中的拓扑结构与嵌入(续)Cannon算法图示(a)对A的对齐(b)对B的对齐(c)对齐后的数据A00A01A02A03A10A11A12A13A20A21A22A23A30A31A32A33B00B01B02B03B10B11B12B13B20B21B22B23B30B31B32B33(d)移动1步后的数据(e)移动2步后的数据A00B00A01B11A02B22A03B33A11B10A12B21A13B32A10B03A22B20A23B31A20B02A21B13A33B30A30B01A31B12A32B23A01B10A02B21A03B32A00B03A12B20A13B31A10B02A11B13A23B30A20B01A21B12A22B23A30B00A31B11A32B22A33B33A02B20A03B31A00B02A01B13A13B30A10B01A11B12A12B23A20B00A21B11A22B22A23B33A31B10A32B21A33B32A30B032024/4/1142.MPI中的拓扑结构与嵌入(Cannon算法)voidMatMatCannon(intn,double*a,double*b,double*c,MPI_Commcomm){intk,nlocal,p,dims[2],periods[2],myrank,my2drank,mycoords[2];intuprank,downrank,leftrank,rightrank,coords[2],shiftsource,shiftdest;MPI_Statusstatus;MPI_Commcomm_2d;MPI_Comm_size(comm,&p);MPI_Comm_rank(comm,&myrank);dims[0]=dims[1]=sqrt(p);periods[0]=periods[1]=1;MPI_Cart_create(comm,2,dims,periods,1,&comm_2d);MPI_Comm_rank(comm_2d,&my2drank);MPI_Cart_coords(comm_2d,my2drank,2,mycoords);MPI_Cart_shift(comm_2d,0,-1,&rightrank,&leftrank);MPI_Cart_shift(comm_2d,1,-1,&downrank,&uprank);nlocal=n/dims[0];MPI_Cart_shift(comm_2d,0,-mycoords[0],&shiftsource,&shiftdest);MPI_Sendrecv_replace(a,nlocal*nlocal,MPI_DOUBLE,shiftdest,1，shiftsource,1,comm_2d,&status);

2024/4/1152.MPI中的拓扑结构与嵌入(Cannon算法)MPI_Cart_shift(comm_2d,1,-mycoords[1],&shiftsource,&shiftdest);MPI_Sendrecv_replace(b,nlocal*nlocal,MPI_DOUBLE,shiftdest,1,shiftsource,1,comm_2d,&status);for(k=0;k<dims[0];k++){MatMatSerial(nlocal,a,b,c);/*c=c+a*b*/MPI_Sendrecv_replace(a,nlocal*nlocal,MPI_DOUBLE,leftrank,1,rightrank,1,comm_2d,&status);MPI_Sendrecv_replace(b,nlocal*nlocal,MPI_DOUBLE,uprank,1,downrank,1,comm_2d,&status);}MPI_Cart_shift(comm_2d,0,+mycoords[0],&shiftsource,&shiftdest);MPI_Sendrecv_replace(a,nlocal*nlocal,MPI_DOUBLE,shiftdest,1,shiftsource,1,comm_2d,&status);MPI_Cart_shift(comm_2d,1,+mycoords[1],&shiftsource,&shiftdest);MPI_Sendrecv_replace(b,nlocal*nlocal,MPI_DOUBLE,shiftdest,1,shiftsource,1,comm_2d,&status);MPI_Comm_free(&comm_2d);}2024/4/1163.将计算与通信重叠非阻塞式通信操作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)2024/4/1173.将计算与通信重叠(续)利用非阻塞式通信操作避免死锁inta[10],b[10],myrank;MPI_Requestreqs[2];…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,&reqs[0]);MPI_Irecv(a,10,MPI_INT,0,1,MPI_COMM_WORLD,&reqs[1]);}…2024/4/1183.将计算与通信重叠(Cannon算法)voidMatMatCannon_nblock(intn,double*a,double*b,double*c,MPI_Commcomm){intk,j,nlocal,p,dims[2],periods[2],myrank,my2drank,mycoords[2];intuprank,downrank,leftrank,rightrank,coords[2],shiftsource,shiftdest;

double*a_buffers[2],*b_buffers[2];MPI_Statusstatus;MPI_Commcomm_2d;MPI_Requestreqs[4];MPI_Comm_size(comm,&p);MPI_Comm_rank(comm,&myrank);dims[0]=dims[1]=sqrt(p);periods[0]=periods[1]=1;MPI_Cart_create(comm,2,dims,periods,1,&comm_2d);MPI_Comm_rank(comm_2d,&my2drank);MPI_Cart_coords(comm_2d,my2drank,2,mycoords);MPI_Cart_shift(comm_2d,0,-1,&rightrank,&leftrank);MPI_Cart_shift(comm_2d,1,-1,&downrank,&uprank);nlocal=n/dims[0];a_buffers[0]=a;b_buffers[0]=b;a_buffers[1]=(double*)malloc(nlocal*nlocal*sizeof(double));b_buffers[1]=(double*)malloc(nlocal*nlocal*sizeof(double));2024/4/1193.将计算与通信重叠(Cannon算法)

MPI_Cart_shift(comm_2d,0,-mycoords[0],&shiftsource,&shiftdest);MPI_Sendrecv_replace(a_buffers[0],nlocal*nlocal,MPI_DOUBLE,shiftdest,1,shiftsource,1,comm_2d,&status);MPI_Cart_shift(comm_2d,1,-mycoords[1],&shiftsource,&shiftdest);MPI_Sendrecv_replace(b_buffers[0],nlocal*nlocal,MPI_DOUBLE,shiftdest,1,shiftsource,1,comm_2d,&status);for(k=0;k<dims[0];k++){MPI_Isend(a_buffers[k%2],nlocal*nlocal,MPI_DOUBLE,leftrank,1,comm_2d,&reqs[0]);MPI_Isend(b_buffers[k%2],nlocal*nlocal,MPI_DOUBLE,uprank,1,comm_2d,&reqs[1]);MPI_Irecv(a_buffers[(k+1)%2],nlocal*nlocal,MPI_DOUBLE,rightrank,1,comm_2d,&reqs[2]);MPI_Irecv(b_buffers[(k+1)%2],nlocal*nlocal,MPI_DOUBLE,downrank,1,comm_2d,&reqs[3]);MatMatSerial(nlocal,a_buffers[k%2],b_buffers[k%2],c);/*c=c+a*b*/for(j=0;j<4;j++)MPI_Wait(&reqs[j],&status);}2024/4/1203.将计算与通信重叠(Cannon算法)

MPI_Cart_shift(comm_2d,0,+mycoords[0],&shiftsource,&shiftdest);MPI_Sendrecv_replace(a_buffers[k%2],nlocal*nlocal,MPI_DOUBLE,shiftdest,1,shiftsource,1,comm_2d,&status);MPI_Cart_shift(comm_2d,1,+mycoords[1],&shiftsource,&shiftdest);MPI_Sendrecv_replace(b_buffers[k%2],nlocal*nlocal,MPI_DOUBLE,shiftdest,1,shiftsource,1,comm_2d,&status);MPI_Comm_free(&comm_2d);free(a_buffers[1]);free(b_buffers[1]);}2024/4/1214.用自定义数据类型与数据封装减少通信次数MPI中的基本数据类型2024/4/1224.用自定义数据类型与数据封装减少通信次数(续)自定义数据类型时常用的函数MPI_Type_contiguousMPI_Type_vector与MPI_Type_hvectorMPI_Type_indexed与MPI_Type_hindexedMPI_Type_structMPI_Type_commit与MPI_Type_free2024/4/123MPI_Type_contiguousintMPI_Type_contiguous(intcount,MPI_Datatypeoldtype,MPI_Datatye*newtype)

当count=4时，该函数的功能可以用下图来描述2024/4/124MPI_Type_vector与MPI_Type_hvectorintMPI_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的功能可以描述如下图2024/4/125MPI_Type_indexed与MPI_Type_hindexedintMPI_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的功能可以描述如下2024/4/126MPI_Type_structintMPI_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]时，该函数的功能可以用下图来描述2024/4/127MPI_Type_commit与MPI_Type_freeintMPI_Type_commit(MPI_Datatype*datatype)

intMPI_Type_free(MPI_Datatype*datatype)注意，在定义了一个新的数据类型后，必须先调用MPI_Type_commit，才能使用该数据类型2024/4/1284.用自定义数据类型与数据封装减少通信次数(续)数据封装与拆卸适用于自定义数据类型利用率很低时的情形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)

拆卸时的顺序必须与进行封装时的顺序一致

2024/4/1295.聚合通信与计算同步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)2024/4/1305.聚合通信与计算(续)多进程归约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_MINLOC2024/4/1315.聚合通信与计算(续)前缀操作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)

2024/4/1325.聚合通信与计算(续)多对多广播intMPI_Allgather(void*sendbuf,intsendcount,MPI_Datatypesenddatatype,void*recvbuf,

intrecvcount,MPI_Datatyperecvdatatype,MPI_Commcomm)intMPI_Allgatherv(void*sendbuf,intsendcount,MPI_Datatypesenddatatype,

void*recvbuf,