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

1、分布存储并行算法的MPI实现程序的一般构造6个根本函数MPI程序的一般构造用MPI_Send与MPI_Recv时的死锁防止同时发送与接收一个简单的MPI程序实例2022/8/242MPI函数与常量的命名规那么Fortran中不分大小写，以mpi_开头Fortran中任何MPI对象与常数都只需要说明为整型C中的函数以MPI_开头，后续第一个字母大写，其它字母小写。该规那么也适用于对象类型说明。C中常量的字母全用大写2022/8/2436个根本函数int MPI_Init(int *argc, char *argv) int MPI_Comm_size(MPI_Comm comm, int *si

2、ze) int MPI_Comm_rank(MPI_Comm comm, int *rank) int MPI_Send(void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm)int MPI_Recv(void *buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status *status) int MPI_Finalize() 2022/8/244MPI程序的一般构造include

3、/usr/local/mpich-1.2.5/include/mpi.hmain(int argc, 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, sou

4、r, tag, comm, &status)；MPI_Finalize()；2022/8/245用MPI_Send与MPI_Recv时的死锁防止int a10, b10, myrank;MPI_Status status;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);else if(myrank =1) MPI_Recv(b,10,MPI_INT,

5、 0, 2, MPI_COMM_WORLD, &status); MPI_Recv(a,10,MPI_INT, 0, 1, MPI_COMM_WORLD, &status);在MPI_Send采用缓冲区实现时，只要缓冲区足够大，以上程序可以正确执行。在采用阻塞方式实现时，将死锁2022/8/246用MPI_Send与MPI_Recv时的死锁防止(续int a10, b10, p, ip;MPI_Status status;MPI_Comm_size(MPI_COMM_WORLD, p);MPI_Comm_rank(MPI_COMM_WORLD, ip);MPI_Send(a,10,MPI_IN

6、T, (ip+1)%p, 1, MPI_COMM_WORLD);MPI_Recv(b,10,MPI_INT,(ip-1+p)%p,1, MPI_COMM_WORLD,&status); 以上程序同样不平安，因为程序的正确性与MPI_Send的实现方式有关。 对这种不平安性，可以通过将进程分组，所有奇数号进程分为一组，所有偶数号进程分为一组，奇数号进程先发送后承受，偶数号进程先接收后发送的方式来消除。2022/8/247同时发送与接收MPI提供了同时发送与接收的函数，可以防止前面的死锁现象int MPI_Sendrecv(void *sendbuf, int sendcount, MPI_Dat

7、atype sendtype, int dest, int sendtag, void *recvbuf, int recvcount, MPI_Datatype recvtype, int sour, int recvtag, MPI_Comm comm, MPI_Status, *status) int MPI_Sendrecv_replace(void *buf, int count, MPI_Datatype datatype, int dest, int sendtag, int sour, int recvtag, MPI_Comm comm, MPI_Status, *statu

8、s) 2022/8/248一个简单的MPI程序实例include /usr/local/mpich-1.2.5/include/mpif.hinteger x, comm, p, myrank, ierror, status(mpi_status_size)call mpi_init(ierror)call mpi_comm_dup(mpi_comm_world, comm, ierror)call mpi_comm_size(comm, p, ierror)call mpi_comm_rank(comm, myrank, ierror)if(myrank .eq. 0) then x = 1

9、0 call mpi_send(x, mpi_integer, 1, myrank+1, 100, comm, ierror)else if(myrank .eq. p-1) then call mpi_recv(x, mpi_integer, 1, myrank-1, 100, comm, status, ierror)else call mpi_recv(x, mpi_integer, 1, myrank-1, 100, comm, status, ierror) call mpi_send(x, mpi_integer, 1, myrank+1, 100, comm, ierror)en

10、difcall mpi_finalize(ierror)end2022/8/249中的拓扑构造与嵌入利用MPI_Init初始化后，MPI将所有进程看成一个线性阵列，进程从0到p-1标号在许多并行算法中，进程之间需要组织为高维拓扑构造，如Cannon算法将一维阵列中的进程映射到高维阵列时，有很多种映射方式，例如附图列出了4种方式程序员可以利用MPI的函数将进程组织成任何逻辑拓扑构造，而不需要以显式的方式指明哪些进程应该映射到哪些处理器上2022/8/2410中的拓扑构造与嵌入(续)01234567891011121314150481215913261014371115(a)先行后列映射 (b)先

11、列后行映射03451276141389151211100132457612131514891110(c)空间曲线填充 (d)超立方体映射2022/8/2411中的拓扑构造与嵌入(续)建立Cartesian拓扑构造int MPI_Cart_create(MPI_Comm comm_old, int ndims, int *dims, int *periods, int reorder, MPI_Comm *comm_cart) ndims为维数，dims为各维中的结点数量periodsk=0指明第k维不带环，否那么带环reorder=0指明不对拓扑构造上的进程进展重新排序，否那么将重新排序com

12、m_cart是新得到的包含拓扑构造信息与comm中信息的通信器2022/8/2412中的拓扑构造与嵌入(续)Cartesian拓扑构造的使用int MPI_Cart_rank(MPI_Comm comm_cart, int *coords, int *rank) 对由coords给出的拓扑构造中坐标，获取对应进程的进程号rankint MPI_Cart_coord(MPI_Comm comm_cart, int rank, int maxdims, int *coords) 对给定的进程号rank，获取其在拓扑构造中的位置坐标coords，其中maxdims不能小于实际的维数int MPI_C

13、art_shift(MPI_Comm comm_cart, int dir, int s_step, int *rank_source, int *rank_dest) dir指明沿哪一维进展数据移动，如dir=0表示沿第0维移动； s_step标识往正方向移动时的步长(边数)，为负表示沿负方向移动； rank_source表示移动时本进程的源进程号； rank_dest表示移动时本进程的目的进程号. 2022/8/2413中的拓扑构造与嵌入(续)Cannon算法图示(a)对A的对齐 (b)对B的对齐 (c)对齐后的数据 A00A01A02A03A10A11A12A13A20A21A22A23

14、A30A31A32A33B00B01B02B03B10B11B12B13B20B21B22B23B30B31B32B33(d)移动1步后的数据 (e)移动2步后的数据A00 B00A01 B11A02 B22A03 B33A11 B10A12 B21A13 B32A10 B03A22 B20A23 B31A20 B02A21 B13A33 B30A30 B01A31 B12A32 B23A01 B10A02 B21A03 B32A00 B03A12 B20A13 B31A10 B02A11 B13A23 B30A20 B01A21 B12A22 B23A30 B00A31 B11A32 B22

15、A33 B33A02 B20A03 B31A00 B02A01 B13A13 B30A10 B01A11 B12A12 B23A20 B00A21 B11A22 B22A23 B33A31 B10A32 B21A33 B32A30 B032022/8/2414中的拓扑构造与嵌入(Cannon算法)void MatMatCannon(int n, double *a, double *b, double *c, MPI_Comm comm) int k, nlocal, p, dims2, periods2, myrank, my2drank, mycoords2; int uprank, do

16、wnrank, leftrank, rightrank, coords2, shiftsource, shiftdest; MPI_Status status; MPI_Comm comm_2d; MPI_Comm_size(comm, &p); MPI_Comm_rank(comm, &myrank); dims0 = dims1 = sqrt(p); periods0 = periods1 = 1; MPI_Cart_create(comm, 2, dims, periods, 1, &comm_2d); MPI_Comm_rank(comm_2d, &my2drank); MPI_Car

17、t_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/dims0; MPI_Cart_shift(comm_2d, 0, -mycoords0, &shiftsource, &shiftdest); MPI_Sendrecv_replace(a, nlocal*nlocal, MPI_DOUBLE, shiftdest, 1， sh

18、iftsource, 1, comm_2d, &status); 2022/8/2415中的拓扑构造与嵌入(Cannon算法)MPI_Cart_shift(comm_2d, 1, -mycoords1, &shiftsource, &shiftdest);MPI_Sendrecv_replace(b, nlocal*nlocal, MPI_DOUBLE, shiftdest, 1, shiftsource, 1, comm_2d, &status);for (k=0; kdims0; k+) MatMatSerial(nlocal, a, b, c); /*c=c+a*b*/ MPI_Send

19、recv_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, +mycoords0, &shiftsource, &shiftdest); MPI_Sendrecv_replace(a, nlocal*nlocal, MPI_DOUBLE,

20、shiftdest, 1, shiftsource, 1, comm_2d, &status); MPI_Cart_shift(comm_2d, 1, +mycoords1, &shiftsource, &shiftdest); MPI_Sendrecv_replace(b, nlocal*nlocal, MPI_DOUBLE, shiftdest, 1, shiftsource, 1, comm_2d, &status); MPI_Comm_free(&comm_2d);2022/8/2416非阻塞式通信操作int MPI_Irecv(void *buf, int count, MPI_Da

21、tatype datatype, int sour, int tag, MPI_Comm comm, MPI_Request *request) int MPI_Isend(void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm, MPI_Request *request) int MPI_Test(MPI_Request *request, int *flag, MPI_Status *status) int MPI_Wait(MPI_Request *request, MPI_Status

22、*status) int MPI_Request_free(MPI_Request *request)2022/8/24173.将计算与通信重叠(续)利用非阻塞式通信操作防止死锁int a10, b10, myrank;MPI_Request reqs2;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);else if(myrank =1) MPI_I

23、recv(b, 10, MPI_INT, 0, 2, MPI_COMM_WORLD, &reqs0); MPI_Irecv(a, 10, MPI_INT, 0, 1, MPI_COMM_WORLD, & reqs1);2022/8/24183.将计算与通信重叠(Cannon算法)void MatMatCannon_nblock(int n, double *a, double *b, double *c, MPI_Comm comm) int k, j, nlocal, p, dims2, periods2, myrank, my2drank, mycoords2; int uprank, d

24、ownrank, leftrank, rightrank, coords2, shiftsource, shiftdest; double *a_buffers2, *b_buffers2; MPI_Status status; MPI_Comm comm_2d; MPI_Request reqs4; MPI_Comm_size(comm, &p); MPI_Comm_rank(comm, &myrank); dims0 = dims1 = sqrt(p); periods0 = periods1 = 1; MPI_Cart_create(comm, 2, dims, periods, 1,

25、&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/dims0; a_buffers0=a; b_buffers0=b; a_buffers1=(double *)malloc(nlocal*nlocal*sizeof(dou

26、ble); b_buffers1=(double *)malloc(nlocal*nlocal*sizeof(double);2022/8/24193.将计算与通信重叠(Cannon算法) MPI_Cart_shift(comm_2d, 0, -mycoords0, &shiftsource, &shiftdest); MPI_Sendrecv_replace(a_buffers0, nlocal*nlocal, MPI_DOUBLE, shiftdest, 1, shiftsource, 1, comm_2d, &status); MPI_Cart_shift(comm_2d, 1, -my

27、coords1, &shiftsource, &shiftdest); MPI_Sendrecv_replace(b_buffers0, nlocal*nlocal, MPI_DOUBLE, shiftdest, 1, shiftsource, 1, comm_2d, &status); for (k=0; kdims0; k+) MPI_Isend(a_buffersk%2, nlocal*nlocal, MPI_DOUBLE, leftrank, 1, comm_2d, &reqs0); MPI_Isend(b_buffersk%2, nlocal*nlocal, MPI_DOUBLE,

28、uprank, 1, comm_2d, &reqs1); MPI_Irecv(a_buffers(k+1)%2, nlocal*nlocal, MPI_DOUBLE, rightrank, 1, comm_2d, &reqs2); MPI_Irecv(b_buffers(k+1)%2, nlocal*nlocal, MPI_DOUBLE, downrank, 1, comm_2d, &reqs3); MatMatSerial(nlocal, a_buffersk%2, b_buffersk%2, c); /*c=c+a*b*/ for (j=0;j4;j+) MPI_Wait(&reqsj,

29、&status);2022/8/24203.将计算与通信重叠(Cannon算法) MPI_Cart_shift(comm_2d, 0, +mycoords0, &shiftsource, &shiftdest); MPI_Sendrecv_replace(a_buffersk%2, nlocal*nlocal, MPI_DOUBLE, shiftdest, 1, shiftsource, 1, comm_2d, &status); MPI_Cart_shift(comm_2d, 1, +mycoords1, &shiftsource, &shiftdest); MPI_Sendrecv_rep

30、lace(b_buffersk%2, nlocal*nlocal, MPI_DOUBLE, shiftdest, 1, shiftsource, 1, comm_2d, &status); MPI_Comm_free(&comm_2d); free(a_buffers1); free(b_buffers1);2022/8/2421MPI中的根本数据类型2022/8/24224.用自定义数据类型与数据封装减少通信次数(续)自定义数据类型时常用的函数MPI_Type_contiguousMPI_Type_vector与MPI_Type_hvectorMPI_Type_indexed与MPI_Typ

31、e_hindexedMPI_Type_structMPI_Type_commit与MPI_Type_free 2022/8/2423MPI_Type_contiguousint MPI_Type_contiguous(int count, MPI_Datatype oldtype, MPI_Datatye *newtype) 当count=4时，该函数的功能可以用以下图来描述2022/8/2424MPI_Type_vector与MPI_Type_hvectorint MPI_Type_vector(int count, int blocklength, int stride, MPI_Data

32、type oldtype, MPI_Datatype *newtype) int MPI_Type_hvector(int count, int blocklength, int stride, MPI_Datatype oldtype, MPI_Datatype *newtype) 当count=3，blocklength=2，stride=3时MPI_Type_vector的功能可以描述如以下图2022/8/2425MPI_Type_indexed与MPI_Type_hindexedint MPI_Type_indexed(int count, int *blocklengths, int

33、 *displacements, MPI_Datatype oldtype, MPI_Datatype *newtype) int MPI_Type_hindexed(int count, int *blocklengths, int *displacements, MPI_Datatype oldtype, MPI_Datatype *newtype) 当count=3，blocklengths=2, 3, 1，displacements=0, 3, 8时MPI_Type_indexed的功能可以描述如下2022/8/2426MPI_Type_structint MPI_Type_struc

34、t(int count, 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时，该函数的功能可以用以下图来描述2022/8/2427MPI_Type_commit与MPI_Type_freeint MPI_Type_commit(MPI_Dataty

35、pe *datatype) int MPI_Type_free(MPI_Datatype *datatype)注意，在定义了一个新的数据类型后，必须先调用MPI_Type_commit，才能使用该数据类型2022/8/24284.用自定义数据类型与数据封装减少通信次数(续)数据封装与拆卸适用于自定义数据类型利用率很低时的情形int MPI_Pack(void *inbuf, int incount, MPI_Datatype datatype, void *outbuf, int outsize, int *position, MPI_Comm comm) int MPI_Unpack(voi

36、d *inbuf, int insize, int *position, void *outbuf, int outcount, MPI_Datatype datatype, MPI_Comm comm) 拆卸时的顺序必须与进展封装时的顺序一致 2022/8/2429同步int MPI_Barrier(MPI_Comm comm) 一对多播送int MPI_Bcast(void *buf, int count, MPI_Datatype datatype, int source, MPI_Comm comm) 多对一归约int MPI_Reduce(void *sendbuf, void *r

37、ecvbuf, int count, MPI_Datatype datatype, MPI_Op op, int target, MPI_Comm comm)2022/8/24305.聚合通信与计算(续)多进程归约int MPI_Allreduce(void *sendbuf, void *recvbuf, int count, MPI_Datatype datatype, MPI_Op op, MPI_Comm comm)多对多归约int MPI_Reduce_scatter(void *sendbuf, void *recvbuf, int *recvcounts, MPI_Datatyp

38、e datatype, MPI_Op op, MPI_Comm comm) op可为MPI_MAX、MPI_MIN、MPI_SUM、MPI_PROD、MPI_LAND、MPI_LOR、MPI_LXOR、MPI_BAND、MPI_BOR、MPI_BXOR、MPI_MAXLOC、MPI_MINLOC2022/8/24315.聚合通信与计算(续)前缀操作int MPI_Scan(void *sendbuf, void *recvbuf, int count, MPI_Datatype datatype, MPI_Op op, MPI_Comm comm) 收集int MPI_Gather(void

39、*sendbuf, int sendcount, MPI_Datatype senddatatype, void *recvbuf, int recvcount, MPI_Datatype recvdatatype, int target, MPI_Comm comm ) int MPI_Gatherv(void *sendbuf, int sendcount, MPI_Datatype senddatatype, void *recvbuf, int *recvcounts, int *displs, MPI_Datatype recvdatatype, int target, MPI_Comm comm) 2022/8/24325.聚合通信与计算(续)多对多播送int MPI_Allgather(void *sendbuf, int sendcount, MPI_Datatype senddatatype, void *recvbuf, int recvcount, MPI_Datatype rec