分布存儲(chǔ)并行算法的MPI實(shí)現(xiàn)

1、分布存儲(chǔ)并行算法的MPI實(shí)現(xiàn)程序的一般構(gòu)造6個(gè)根本函數(shù)MPI程序的一般構(gòu)造用MPI_Send與MPI_Recv時(shí)的死鎖防止同時(shí)發(fā)送與接收一個(gè)簡(jiǎn)單的MPI程序?qū)嵗?022/8/242MPI函數(shù)與常量的命名規(guī)那么Fortran中不分大小寫(xiě)，以mpi_開(kāi)頭Fortran中任何MPI對(duì)象與常數(shù)都只需要說(shuō)明為整型C中的函數(shù)以MPI_開(kāi)頭，后續(xù)第一個(gè)字母大寫(xiě)，其它字母小寫(xiě)。該規(guī)那么也適用于對(duì)象類型說(shuō)明。C中常量的字母全用大寫(xiě)2022/8/2436個(gè)根本函數(shù)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程序的一般構(gòu)造include

3、/usr/local/mpich-1.2.5/include/mpi.hmain(int argc, char *argv)參數(shù)說(shuō)明;MPI_Init(&argc, &argv)；MPI_Comm_dup(MPI_COMM_WORLD, &comm)；MPI_Comm_size(comm, &size)；MPI_Comm_rank(comm, &rank)；建立新的進(jìn)程拓?fù)浣Y(jié)構(gòu)和新的通信器應(yīng)用程序主體：包括計(jì)算與控制；進(jìn)程間通信，如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時(shí)的死鎖防止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采用緩沖區(qū)實(shí)現(xiàn)時(shí)，只要緩沖區(qū)足夠大，以上程序可以正確執(zhí)行。在采用阻塞方式實(shí)現(xiàn)時(shí)，將死鎖2022/8/246用MPI_Send與MPI_Recv時(shí)的死鎖防止(續(xù)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); 以上程序同樣不平安，因?yàn)槌绦虻恼_性與MPI_Send的實(shí)現(xiàn)方式有關(guān)。 對(duì)這種不平安性，可以通過(guò)將進(jìn)程分組，所有奇數(shù)號(hào)進(jìn)程分為一組，所有偶數(shù)號(hào)進(jìn)程分為一組，奇數(shù)號(hào)進(jìn)程先發(fā)送后承受，偶數(shù)號(hào)進(jìn)程先接收后發(fā)送的方式來(lái)消除。2022/8/247同時(shí)發(fā)送與接收MPI提供了同時(shí)發(fā)送與接收的函數(shù)，可以防止前面的死鎖現(xiàn)象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一個(gè)簡(jiǎn)單的MPI程序?qū)嵗齣nclude /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中的拓?fù)錁?gòu)造與嵌入利用MPI_Init初始化后，MPI將所有進(jìn)程看成一個(gè)線性陣列，進(jìn)程從0到p-1標(biāo)號(hào)在許多并行算法中，進(jìn)程之間需要組織為高維拓?fù)錁?gòu)造，如Cannon算法將一維陣列中的進(jìn)程映射到高維陣列時(shí)，有很多種映射方式，例如附圖列出了4種方式程序員可以利用MPI的函數(shù)將進(jìn)程組織成任何邏輯拓?fù)錁?gòu)造，而不需要以顯式的方式指明哪些進(jìn)程應(yīng)該映射到哪些處理器上2022/8/2410中的拓?fù)錁?gòu)造與嵌入(續(xù))01234567891011121314150481215913261014371115(a)先行后列映射 (b)先

11、列后行映射03451276141389151211100132457612131514891110(c)空間曲線填充 (d)超立方體映射2022/8/2411中的拓?fù)錁?gòu)造與嵌入(續(xù))建立Cartesian拓?fù)錁?gòu)造int MPI_Cart_create(MPI_Comm comm_old, int ndims, int *dims, int *periods, int reorder, MPI_Comm *comm_cart) ndims為維數(shù)，dims為各維中的結(jié)點(diǎn)數(shù)量periodsk=0指明第k維不帶環(huán)，否那么帶環(huán)reorder=0指明不對(duì)拓?fù)錁?gòu)造上的進(jìn)程進(jìn)展重新排序，否那么將重新排序com

12、m_cart是新得到的包含拓?fù)錁?gòu)造信息與comm中信息的通信器2022/8/2412中的拓?fù)錁?gòu)造與嵌入(續(xù))Cartesian拓?fù)錁?gòu)造的使用int MPI_Cart_rank(MPI_Comm comm_cart, int *coords, int *rank) 對(duì)由coords給出的拓?fù)錁?gòu)造中坐標(biāo)，獲取對(duì)應(yīng)進(jìn)程的進(jìn)程號(hào)rankint MPI_Cart_coord(MPI_Comm comm_cart, int rank, int maxdims, int *coords) 對(duì)給定的進(jìn)程號(hào)rank，獲取其在拓?fù)錁?gòu)造中的位置坐標(biāo)coords，其中maxdims不能小于實(shí)際的維數(shù)int MPI_C

13、art_shift(MPI_Comm comm_cart, int dir, int s_step, int *rank_source, int *rank_dest) dir指明沿哪一維進(jìn)展數(shù)據(jù)移動(dòng)，如dir=0表示沿第0維移動(dòng)； s_step標(biāo)識(shí)往正方向移動(dòng)時(shí)的步長(zhǎng)(邊數(shù))，為負(fù)表示沿負(fù)方向移動(dòng)； rank_source表示移動(dòng)時(shí)本進(jìn)程的源進(jìn)程號(hào)； rank_dest表示移動(dòng)時(shí)本進(jìn)程的目的進(jìn)程號(hào). 2022/8/2413中的拓?fù)錁?gòu)造與嵌入(續(xù))Cannon算法圖示(a)對(duì)A的對(duì)齊 (b)對(duì)B的對(duì)齊 (c)對(duì)齊后的數(shù)據(jù) A00A01A02A03A10A11A12A13A20A21A22A23

14、A30A31A32A33B00B01B02B03B10B11B12B13B20B21B22B23B30B31B32B33(d)移動(dòng)1步后的數(shù)據(jù) (e)移動(dòng)2步后的數(shù)據(jù)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中的拓?fù)錁?gòu)造與嵌入(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中的拓?fù)錁?gòu)造與嵌入(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.將計(jì)算與通信重疊(續(xù))利用非阻塞式通信操作防止死鎖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.將計(jì)算與通信重疊(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.將計(jì)算與通信重疊(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.將計(jì)算與通信重疊(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中的根本數(shù)據(jù)類型2022/8/24224.用自定義數(shù)據(jù)類型與數(shù)據(jù)封裝減少通信次數(shù)(續(xù))自定義數(shù)據(jù)類型時(shí)常用的函數(shù)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) 當(dāng)count=4時(shí)，該函數(shù)的功能可以用以下圖來(lái)描述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) 當(dāng)count=3，blocklength=2，stride=3時(shí)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) 當(dāng)count=3，blocklengths=2, 3, 1，displacements=0, 3, 8時(shí)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) 當(dāng)count=3 ，blocklengths=2, 1, 3 ，oldtypes= MPI_INTEGER, MPI_DOUBLE_PRECISION, MPI_BYTE ，displacements=0, 9, 18時(shí)，該函數(shù)的功能可以用以下圖來(lái)描述2022/8/2427MPI_Type_commit與MPI_Type_freeint MPI_Type_commit(MPI_Dataty

35、pe *datatype) int MPI_Type_free(MPI_Datatype *datatype)注意，在定義了一個(gè)新的數(shù)據(jù)類型后，必須先調(diào)用MPI_Type_commit，才能使用該數(shù)據(jù)類型2022/8/24284.用自定義數(shù)據(jù)類型與數(shù)據(jù)封裝減少通信次數(shù)(續(xù))數(shù)據(jù)封裝與拆卸適用于自定義數(shù)據(jù)類型利用率很低時(shí)的情形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) 拆卸時(shí)的順序必須與進(jìn)展封裝時(shí)的順序一致 2022/8/2429同步int MPI_Barrier(MPI_Comm comm) 一對(duì)多播送int MPI_Bcast(void *buf, int count, MPI_Datatype datatype, int source, MPI_Comm comm) 多對(duì)一歸約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.聚合通信與計(jì)算(續(xù))多進(jìn)程歸約int MPI_Allreduce(void *sendbuf, void *recvbuf, int count, MPI_Datatype datatype, MPI_Op op, MPI_Comm comm)多對(duì)多歸約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.聚合通信與計(jì)算(續(xù))前綴操作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.聚合通信與計(jì)算(續(xù))多對(duì)多播送int MPI_Allgather(void *sendbuf, int sendcount, MPI_Datatype senddatatype, void *recvbuf, int recvcount, MPI_Datatype rec