LecNote_11_MPI并行程序开发基础(示例程序).ppt

1、第十一讲 MPI”点到点(Point-to-Point)”通信,阻塞式通信的概念 消息交换双方的不对称性 MPI_STATUS MPI_ANY_TAG MPI_ANY_SOURCE 并行算法：不要为了简化编码而牺牲算法本身的效率 以求素数为例 消息交换的顺序问题,阻塞式通信(blocking communication),MPI_Send(s_buf, s_count, datatype, dest, s_tag, comm) MPI_Recv(r_buf, r_count, datatype, source, r_tag, comm, status) message=(s_buf, s_co

2、unt, datatype, source, dest, tag, comm) 交换什么？(s_buf, s_count, datatype) 谁发送？(source, comm) 谁接收？(dest, comm) 程序中的消息分类(tag),s_tag ：一个整数，编号范围0.UB，对发送的消息进行分类 r_tag ：所接收消息的类型，可以是一个整数，编号范围0.UB UB：环境参数，大小由MPI系统决定，至少为32767，具体大小可以通过查询MPI属性MPI_TAG_UB获得 使用MPI查询函数MPI_ATTR_GET 消息的信封(message envelope) Source Dest

3、ination Tag Communicator 消息匹配 消息信封 数据类型,站在消息发送者的角度：执行了消息发送语句后，消息中的数据已经发送出去 不需要知道消息接收者的进度 可以对消息占用的存储空间执行其他的操作 此时，消息的数据处在下列两种状态之一，取决于消息传递系统的实现策略、消息接收方的进度、消息的大小 已经达到消息的接收方 在运行支持系统中缓存 MPI_Send(buf, count, datatype, dest, tag, comm) 执行完MPI_Send后，就可以修改 buf所指的内存区域,执行MPI_Send之前,Message data,Sender,用户程序空间,MP

4、I runtime空间,Receiver,Buffer specified by application on sender side,Buffer specified by application on receiver side,Buffer specified by MPI runtime on sender side,Buffer specified by MPI runtime on receiver side,从MPI_Send返回后：状态一,Sender,用户程序空间,MPI runtime空间,Receiver,Buffer specified by application o

5、n sender side,Buffer specified by application on receiver side,Buffer specified by MPI runtime on sender side,Buffer specified by MPI runtime on receiver side,Message data,从MPI_Send返回后：状态二,Message data,Sender,用户程序空间,MPI runtime空间,Receiver,Buffer specified by application on sender side,Buffer specifi

6、ed by application on receiver side,Buffer specified by MPI runtime on sender side,Buffer specified by MPI runtime on receiver side,通常情况下，MPI运行支持系统依据被传递消息的大小，决定MPI_Send返回后，消息数据的状态 消息比较小，可以存储在MPI runtime的缓冲区中，在sender端 把消息从application buffer复制到runtime buffer 开始向receiver端的runtime buffer传递 消息数据可能一部分在send

7、er端的runtime buffer中，另一部分在receiver端的runtime buffer中 消息很大，超出了MPI运行支持系统的缓存能力，在sender端 等待接收方执行预期的MPI_Recv 将数据从sender端的application buffer，传递到receiver端的application buffer 全部数据都安全到达receiver端的application buffer后，执行MPI_Send之后的语句,站在消息接收者的角度：执行了消息接收语句后，已经可以访问消息的数据了 不需要知道消息发送者的是何时发送的数据 可以对所接收的消息进行处理 MPI_Recv(bu

8、f, count, datatype, source, tag, comm, status) 执行完MPI_Recv后，消息数据已经覆盖了buf所指的内存区域 source可以是MPI_ANY_SOURCE tag可以是MPI_ANY_TAG,MPI runtime在执行MPI_Recv时，依据(datatype, source, tag, comm) 检查MPI runtime缓存的消息数据：匹配成功 从runtime buffer中复制到application buffer中 从runtime buffer中删除消息数据 检查sender端从application收到的消息请求，但消息数据

9、还在application buffer中：匹配成功 从sender端的application buffer中，把消息数据传递到receiver端的application buffer中 在sender端，完成该消息的发送操作 MPI_send：从该函数返回到application中 其它消息发送语句(下一讲讲述) ，执行相应的操作 等待sender端的application执行消息发送语句，直到匹配成功为止,MPI_Send与MPI_Recv的不对称性、MPI_STATUS,MPI_Send(buf, count, datatype, dest, tag, comm)：所有参数的值都是确定的

10、 count：消息中元素的数量，元素的类型是datatype dest：接收者在comm中的编号 tag：0 UB中的一个整数 MPI_Recv(buf, count, datatype, source, tag, comm, status)：下列三个参数的值具有不确定性 count：buf所指内存区能存放的最大元素数量，元素的类型是datatype source：可以是发送者在comm中的编号，也可以是MPI_ANY_SOURCE tag：可以是0 UB中的一个整数，也可以是MPI_ANY_TAG,MPI_ANY_SOURCE：MPI runtime在执MPI_Recv时，对发送到当前处理器

11、的消息，依据(datatype, tag, comm)与MPI runtime缓存的消息进行匹配 多个发送者都向本处理器发送了消息时，从匹配成功的消息中任选一条进行接收 MPI_ANY_TAG：MPI runtime在执MPI_Recv时，对发送到当前处理器的消息，依据(datatype, source, comm)与MPI runtime缓存的消息进行匹配 发送者向本处理器发送了多条消息时，从匹配成功的消息中接收最早提交发送的一条进行接收 MPI_Recv返回时，status参数中记录了： 所接收消息中元素的数量，元素的类型是datatype 消息的发送方 消息的标签 如果接收消息失败，错误

12、的类型,分析：求小于N的全部素数,将3 N划分成一组大小相等的片段 已经完成了前i个片段的搜索，第i个片段的最后一个整数是m 从i+1个片段开始的k个片段可以并行执行，其中第从i+k个片段的最后一个整数小于m2 。这k个片段 需要的运算量不相同 包含的素数数量不同,3,N,已找到的素数,由0#处理器维护一个“待搜索片段的队列”，每个片段有一个唯一的ID，搜索到的结果也存储在0#处理器上。其他处理器 每次领取一个待搜索片段 完成计算后，将结果发送给0#处理器 在0#处理器上 不知道 哪个处理器先完成自己的任务 在每个任务中分别搜索到了多少个素数 解决办法 MPI_ANY_SOURCE：不限制消息

13、的发送方 MPI_ANY_TAG：不限制被接收消息的标签 MPI_Status：记录一次消息传递的结果，包括消息的发送方、标签、以及大小,对MPI Exercise中的mpi_prime.c进行批判 判断N是否为素数采用的算法: 令r是满足r2N的最大整数 将N与3 r中各奇数相除，按从小到大的顺序 找到一个能整除的奇数，则表示不是素数 所有奇数都不能整除，是一个素数 N=900001， r=2999：判断一个素数的开销是实际开销的3倍多；而且随着N的增加，这个比例还更大 3 2999包括将近1500个奇数 3 2999包括429个素数 计算划分的方法：循环分配，假设p个处理器，每个处理器负责

14、计算myRank*2+1:M:2*(P-1)中的素数 出发点是平衡计算的负载 看似均匀划分了计算任务 未看到计算开销的本质,p=4 1#处理器：3,9,15,21,27,33,所有数字都能被3整除 2#处理器：5,11,17,23,29,35,41, 3#处理器：7,13,19,25,31,37,43, p=5 1#处理器：3,11,19, 27,35, 2#处理器：5,13,21,29,37,45, 3#处理器：7,15,23,31,39,47, 4#处理器：9,17,25,33,41,49, p=6 1#处理器：3,13,23, 33,43, 2#处理器：5,15,25,35,45,55,

15、所有数字都能被5整除 3#处理器：7,17,27,37, 47,57, 4#处理器：9,19,29,39,49,59, 5#处理器：11,21,31,41,51,当使用偶数个处理器运行并行程序时，在(p-2)/2号处理器 上，所有数字都能被p-1整除。搜索其中素数需要的运算开销远小于其他处理器上的运算开销 P=4, i=1 P=6, i=2 P=8, i=3 P=10, i=4 P=12, i=5 P=14, i=6 P=16, i=7 P=18, i=8 计算任务的划分不均衡，原因在于hotspots把握不准确 不是每个整数：非素数一般只需要很少几次的除法运算 是素数：越是后面的素数，需要的

16、除法次数越多,对MPI Exercise中的mpi_prime.c的批判,局限1：未把握应用问题的hotspots 计算划分不均衡 系统的scalability不好：使用7个处理器的效果与6个处理器的效果几乎没有差别 局限2：为了简化并行编程，牺牲了判断一个数字是否是素数的效率。 与自己写的串行程序相比，并行加速比很理想 与一个简练的串行程序比，当搜索的范围N达到一定的规模后，并行效果很糟糕 N是非素数：多数情况下，经过少量的除法就能判定 N是素数：对奇数从小到大都要相除，做了大量不必要的除法运算。N越大，这种不不要的计算越多,对并行程序设计在算法方面的体会,把握其中真实的hotspots，重

17、点在于把这些hotspots划分到不同的机器上并行执行 从串行算法上寻找hotspots容易迷惑：我们经常关注于其中的循环 从问题域的特征、数学模型上分析，先不要考虑实现，更不要考虑串行算法。这样更能准确把握hotspots 先脱离具体的实现设计并行算法，设计好算法以后，再检查其中需要的通信和同步 我们在解决问题时，容易犯的一个错误：把问题的分析、方案的设计与实现手段的细节搅在一起,MPI_STATUS,包含三个分量 MPI_SOURCE：消息的发送方 MPI_TAG：发送方设置的消息标签 MPI_ERROR：MPI runtime设置的错误代码 提供一个信息：实际接收到的元素数量 MPI_G

18、et_count( MPI_Comm_rank(MPI_COMM_WORLD, ,else/slave(producer/client)端 flag=true; While(flag) local_computing; /对buf, count, tag, flag执行赋值 MPI_send(buf, count, MPI_CHAR, 0, tag, MPI_COMM_WORLD); 多个发送者并发地向一个接收者发送消息 不同发送者的消息达到顺序是任意的 每个消息(大小、标签)表示的请求不同,消息传递的顺序,MPI提供的消息缓存机制把消息的发送者和接收者独立开来 sender把消息交给MPI

19、receiver从MPI接收消息 MPI执行receiver的一个MPI_Recv时，从下列消息中进行匹配 被MPI缓存在系统缓冲区中的消息 处于posted状态的MPI_Send的消息,消息缓冲引起的发送次序和接收次序的关系问题 一对sender/receiver之间，如果receiver中的一个MPI_Recv能够与sender发送的多条消息都匹配，实际接收的是哪条消息？ ANY_SOURCE引起的发送次序和接收次序的关系问题 一个receiver与多个sender之间，如果每个sender所发送的消息都能receiver所执行的MPI_Recv匹配，实际接收的是哪个sender发送的消息

20、？,例如 在一对sender/receiver之间，希望按顺序依次msg1和msg2从sender传递给receiver sender的进度比receiver快，在sender执行完了这两条消息的MPI_Send之后，receiver才执行到第一个MPI_Recv MPI_Recv使用MPI_ANY_TAG为消息标签 msg1和msg2都被MPI缓存在系统缓冲区中 MPI_Recv所接收的消息是msg1还是msg2 ？编程者预期的是接收msg1,MPI的消息传递语义order：messages are non-overtaking 当消息发送者sender向消息接收者receiver所发送的连

21、续多条消息能够与同一个MPI_Recv匹配，如果第一条消息pending状态，那么该MPI_Recv一定不会接收其它的消息 当消息的接收者receiver向MPI提交(post)的连续多个MPI_Recv都能与同一个消息匹配，如果第一个MPI_ Recv的请求还处于pending状态，那么该消息不会被MPI用来满足其它MPI_Recv的消息接收请求 对于MPI_Send/MPI_Recv这种blocking通信，任何时刻，每个receiver最多只有一个消息接收请求处于 posted状态 但MPI提供了允许一个进程的多个消息传递请求同时处于posted状态的机制(non-blocking通信)

22、,对于MPI_Send/MPI_Recv，可以理解为MPI在每对sender和receiver之间实现了一组FIFO(First In First Out)通道channel(tag)，每个消息标签tag有一个唯一的通道 MPI_Send：向对应通道的push操作，把消息放到通道的末尾 MPI_Recv 检查哪些满足要求(符合消息的tag和source)的通道，进行消息匹配 从中选择一个匹配成功的通道，对该通道执行pull操作，从中取出匹配成功的第一条消息,考虑下面代码中，0号进程接收从哪个进程接收消息 tag=10; If (my_rank=0) MPI_Recv(buf, count, M

23、PI_INT, MPI_ANY_SOURCE, tag, MPI_COMM_WORLD, 0号进程的MPI_Recv可以与其他任何进程的MPI_Send匹配,MPI的order语义表明， 0号进程的MPI_Recv可能消费其他任何进程所发送来的消息。因此，上述代码完成之后，0号进程的buf中的内容是不确定的，取决于MPI系统的实现。 因此，在使用MPI_ANY_SOURCE时，为了保证应用程序计算结果的确定性(determinism：应用程序每次执行时，只要计算数据相同，计算的结果也相同)，需要应用程序根据消息接收语句完成后的status确定发送方sender,ANY_SOURCE引起的公平性

24、(fairness)问题,MPI的order语义表明，一个send请求被posted之后，即使消息的接收方不断地post与该send相匹配的receive请求，该send请求的消息可能永远也不会被接收。,示例 tag=10; flag=true; If (my_rank=0) while(flag) MPI_Recv(buf, count, MPI_INT, MPI_ANY_SOURCE, tag, MPI_COMM_WORLD, 一种可能的情形是：0号进程每次总是从2号进程接收数据进行处理，其它进程虽然也产生了很多数据，但始终没有被0号进程接收,由此，可以得到MPI“点到点”通信的另一个消息

25、传递语义fairness：MPI不保证消息处理的公平性 发送者提交了(post)一条消息msg; msg的意中接收者receiver不断提交(post)能够与msg匹配的消息接收请求 实际中可能发生msg一直都没有被receiver接收的情况 MPI消息传递的fairness语义所引发的另一个问题是starvation：在“多生产者单消费者”模式下，部分“生产者”产生的消息总也不能被“消费者”接收，另一部分“生产者”则不断地产生新消息，发送给“消费者”进行处理，引起“生产者”之间的负载不均衡 生产者：消息的发送方(producer/client/slave) 消费者：消息的接收方(consum

26、er/sever/master),根据MPI消息传递的order语义，还可以得到一个消息传递语义progress：当在两个进程上启动了(posted)一对匹配的发送和接收操作后，至少其中一个操作将能能够成功执行而不受系统中其他操作的影响 只要接收操作没有因为收到其他的消息而完成，那么发送操作就一定能够成功完成 只要发送操作所发出的消息没有被同一个接收进程提交的其它消息接收请求所消耗，接收操作就一定会完成,点到点通信,point-to-point通信的模式(communication mode) standard：标准模式 buffered：缓冲模式 synchronous：同步模式 ready

27、：就绪模式 point-to-point通信的分类 blocking communication ：阻塞通信 nonblocking communication ：非阻塞通信 point-to-point通信的语义 order：消息收发顺序 progress：消息传递进度 fairness：消息收发公平性,阻塞式点到点信,发送方 标准模式：MPI_Send 缓冲模式：MPI_Bsend 同步模式：MPI_Ssend 就绪模式：MPI_Rsend 接收方 MPI_Recv 这四种通信模式在语法上的差别表现为发送消息使用的MPI函数名称不同，接收消息都使用MPI_Recv。当函数返回用户程序时，都

28、表示MPI完成了相应的消息交换请求 消息发送请求(MPI_Send/Bsend/Ssend/Rsend)：MPI已经成功的从用户程序空间取走了消息的data和envelop 消息接收请求(MPI_Recv)：MPI已经成功地将消息数据存储到了用户程序空间,MPI_Send(buf, count, datatype, dest, tag, comm) 何时开始执行？无论意中匹配的MPI_Recv是否已经Posted(MPI从用户程序中收到了接收消息的请求)，sender都可以启动MPI_Send要求MPI执行消息发送 何时返回？消息的data和envelop都被MPI从用户程序空间安全取走之后

29、返回时消息在哪里？下列两种情况之一 message被MPI临时缓存在一个系统缓冲区中 message被MPI拷贝到对应MPI_Recv的接收缓冲区r_buf中 MPI_Recv(buf, count, datatype, source, tag, comm, status) 何时开始执行？无论意中匹配的MPI_Send是否已经Posted(MPI从用户程序中收到了发送消息的请求)，sender都可以启动MPI_Recv要求MPI执行消息接收 何时返回？消息的data被MPI存储到了用户程序空间中由(buf, count, datatype)指定的存储区域之后,标准模式,MPI_Send,MPI

30、_Recv,缓冲模式,MPI_Bsend(buf,count,datatype,dest,tag,comm) 无论意中匹配的MPI_Recv是否已经Posted，MPI都将消息的data和envelop从sender的用户程序空间取出来 标准模式下，只有意中匹配的MPI_Recv被posted、或有足够大的系统缓冲区缓存消息时，MPI才会把消息的data和envelop从sender的用户程序空间取走 MPI将buf里的内容放到由下面Buffer_attach建立的buffer中就返回，但在“后台”将buf中的数据送走。 MPI_Buffer_attach(IN buffer,IN size)

31、:在用户空间为MPI应用程序提供一个buffer，每个进程只能有一个这样的buffer。一个buffer可以由许多Bsend共用，MPI用一定的算法来管理它。即用户将自己空间的一块地方交给MPI来管，用于缓冲。 MPI_Buffer_detach(OUT buffer, OUT size):释放缓冲区，阻塞等待，直到buffer用空。,MPI_Bsend的用处是使用户缓冲区能尽快被重用(在用户程序的控制下)。例如这个缓冲区就是某个数组的一部分，一方面要送给其它进程处理，另一方面本进程也要处理(甚至更新)，此时用Bsend就很好，实现本进程通信和计算的重叠。（例如求解Laplace方程的情形）,

32、同步模式,MPI_Ssend(buf,count,datatype,dest,tag,comm) 无论意中匹配的MPI_Recv是否已经Posted， sender都可以启动MPI_Ssend，但必须等到意中匹配的MPI_Recv 已经开始接收消息数据之后， MPI_Ssend才能够成功返回 标准模式下，只有意中匹配的MPI_Recv被posted、或有足够大的系统缓冲区缓存消息时，MPI才会把消息的data和envelop从用户程序空间取走，然后MPI_Send就能够返回 返回时相应的MPI_Recv已经启动执行。这告诉sender的数据已经开始到达receiver的用户区(不一定全部收完)

33、,就绪模式,MPI_Rsend(buf,count,datatype,dest,tag,comm) 只有意中匹配的MPI_Recv是否已经Posted后， sender才能启动MPI_Rsend，否则会产生错误，执行的结果无定义 标准模式下，无论意中匹配的MPI_Recv是否已经Posted，sender都可以启动MPI_Send要求MPI执行消息发送 当调用MPI_Rsend时，相应的recv必须已经执行了，否则错误，结果无意义。这要由用户程序来保证。于是，MPI可用较简单的协议来实现MPI_Rsend，从而提高效率,非阻塞式点到点通信,四种通信模式在语法上的差别表现为发送消息使用的MPI函

34、数名称不同，接收消息都使用MPI_Irecv。 非阻塞的消息发送包括两个独立的部分 Non-blocking send start：把消息发送请求提交给MPI，但从用户程序空间取走消息的data和envelop前，即返回sender， Non-blocking send complete：检查消息数据是否已经由MPI从sender的程序空间取出来,Non-blocking send,Non-blocking send start：把消息发送请求提交给MPI，但从用户程序空间取走消息的data和envelop前，即返回sender，也包括四种模式 标准模式：MPI_Isend 缓冲模式：MPI_

35、Ibsend 同步模式：MPI_Issend 就绪模式：MPI_Irsend Non-blocking send complete：检查消息数据是否已经由MPI从sender的程序空间取出来，有两种检查模式 等待消息传递请求完成后才返回：MPI_Wait(request,status) 查看消息传递请求是否完成： MPI_Test(request, flag, status) 非阻塞的消息发送表示 MPI系统已经可以从sender的消息缓冲区取数据了 在提交了消息发送请求之后、MPI完成消息发送之前，sender不能够访问消息缓冲区,MPI_Isend,MPI_Irecv,Non-blocki

36、ng receive,非阻塞的消息接收包括两个独立的部分 Non-blocking receive start：把消息接收请求提交给MPI，但在消息数据被存储到用户程序空间前，即返回receiver MPI_Irecv(buf, count, datatype,source, tag, comm, request) Non-blocking receive complete：检查消息数据是否已经由MPI存储到receiver的程序空间，有两种检查模式 等待消息传递请求完成后才返回：MPI_Wait(request,status) 查看消息传递请求是否完成： MPI_Test(request,

37、flag, status) 非阻塞的消息接收表示 MPI系统已经可以向receiver的消息缓冲区写数据了 在提交了消息接收请求之后、MPI完成消息接收之前， receiver不能够访问消息缓冲区,MPI_Isend和MPI_Irecv,MPI_ISend(void* buf, int count, MPI_Datatype, datatype, int dest, int tag, MPI_COMM comm, MPI_Request* request) 与谁匹配？MPI_Recv或者MPI_Irecv 何时开始执行？无论意中匹配的消息接收请求是否已经Posted，sender都可以启动MP

38、I_ISend要求MPI执行消息发送 何时返回？MPI接收了消息发送请求之后，此时消息的data和envelop可能都还在sender的程序空间中 MPI_IRecv(void* buf, int count, MPI_Datatype, datatype, int source, int tag, MPI_COMM comm, MPI_Request* request) 与谁匹配？MPI_Send、 MPI_Bsend、 MPI_Ssend、MPI_Rsend MPI_ISend、 MPI_IBsend、 MPI_ISsend、MPI_IRsend 何时开始执行？无论意中匹配的消息发送请求是

39、否已经Posted， receiver都可以启动MPI_IRecv要求MPI执行消息接收 何时返回？ MPI接收了消息接收请求之后，此时消息数据可能还未存储到receiver的程序空间中,非阻塞通信的其它模式,MPI_Ibsend(void* buf, int count, MPI_Datatype, datatype, int dest, int tag, MPI_COMM comm, MPI_Request* request) MPI_Issend(void* buf, int count, MPI_Datatype, datatype, int dest, int tag, MPI_CO

40、MM comm, MPI_Request* request) 与谁匹配？MPI_Recv或者MPI_Irecv 何时开始执行？无论意中匹配的消息接收请求是否已经Posted，sender都可以启动MPI_ISend要求MPI执行消息发送 何时返回？MPI接收了消息发送请求之后，此时消息的data和envelop可能都还在sender的程序空间中 MPI_Irsend(void* buf, int count, MPI_Datatype, datatype, int dest, int tag, MPI_COMM comm, MPI_Request* request) 与谁匹配？MPI_Recv或者MPI_Irecv 何时开始执行？只有意中匹配的消息接收请求已经Posted，sender才可以启动MPI_Irsend要求MPI执行消息发送 何时返回？MPI接收了消息发送请求之后，此时消息的data和envelop可能都还在sender的程序空间中,非阻塞通信与并行性能优化,并行处理的目的之一是：通过让不同的“部件”一起工作，提高问题求解的效率 但是，blocking通信时，数据交换与数据计算是串行执行的，特别是在“标准”模式、“同步”模式和“就绪”模式下，sender在把消息传递给MPI系统时，还可能需要空等待以于receiver的进度同步 数据发送方