并行计算同步计算

《并行计算同步计算》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六章同步计算SynchronousComputations同步计算分为全同步和部分同步全同步(fullsynchronination)：所有的进程在一些规则的执行点上的同步。部分同步(partialsynchronization)或局部同步(localsynchronization)：在逻辑上相邻的一组进程参与的同步。同步计算是指那些带有全同步或大量部分同步的计算。主要内容全同步及相关技术问题同步计算同步迭代程序实例一、全同步及相关技术问题在消息传递并行计算中，常用的全同步的实现方法有：障碍、路障(barrier)计数器实现树实现1、障碍（路障）同步(barriersynchron

2、ization)：在并行系统中，使一组进程取得同步的一种方法。它在参与障碍同步的每个进程的程序中彼此必须等待的位置设置一个障碍点，当某进程执行到障碍点时暂停，等待所有进程都执行到这个障碍点上，它们才能继续运行。通常需要同步的进程的程序中有多个障碍点，以同步它们彼此的操作。障碍同步可应用于：共享存储器系统分布存储的消息传递系统进程不在同一时刻到达障碍点的情况进程时间P0P1…P2Pn-1活动等待…障碍在消息传递系统中，障碍同步通常是由库例程（函数）提供的。MPI的障碍同步例程：barrier(comm)阻塞所有的调用者，直到通信体(comm)中所有的成员都调用了该例程后,各进程中的ba

3、rrier调用才可返回。PVM库也有类似的例程：pvm_barrier()障碍同步例程的实现取决于并行系统的体系结构。:::barrier();:::::barrier();::::::::barrier();::……进程P0Pp-1P1各进程处于等待状态，直到所有的进程都到达barrier调用点为止。2、集中式计数器实现：用一个计数器对到达路障的进程数目计数。计数器的初值为0；每个调用路障的进程将计数器增1，并检查计数器是否已到达路障同步进程总数n；若未到达n值，则使进程转入“挂起”状态；否则释放该进程及所有其它等待进程。:::barrier();:::::barrier();::

4、::::::barrier();::……计数器计数器路障分为两个阶段：进入路障阶段离开路障阶段如果系统没有路障例程，通常由主进程维护路障计数器：当从进程到达路障时，主进程对来自从进程的消息计数；在离开路障阶段中，主进程释放各个从进程。/*countslavesastheyreachbarrier*/for(i=0;i

5、从进程代码：3、树实现：利用树结构实现的同步方法假设有8个进程P0～P7，路障同步完成的过程为：第一级：当P1到达路障时，P1给P0发送消息；当P3到达路障时，P3给P2发送消息；当P5到达路障时，P5给P4发送消息；当P7到达路障时，P7给P6发送消息；第二级：当P2到达路障且P2已收到P3发来的消息时，P2给P0发送消息；当P6到达路障且P6已收到P7发来的消息时，P6给P4发送消息；第三级：当P4到达路障且P4已收到P6发来的消息时，P4给P0发送消息。树型路障实现过程P0P1P2P3P4P5P6P7到达路障离开路障树型障碍同步算法(SPMD)：假设n是2的整幂次/*到达阶段*

6、/for(i=0;i=0;i--)if(myid%2i==0)if(myid%2i+1==0)send(Pmyid+2i);elserecv(Pmyid-2i);局部同步全同步要求所有的进程同步，但实际问题中常有些局部同步的情况。对于局部同步的情况，我们只需在要求同步的进程之间实现即可。例如：在进程Pi、Pj和Pk之间实现同步是利用彼此间的接收/发送空消息完成的：PiPjPksend(

7、Pi);send(Pk);recv(Pi);recv(Pk);recv(Pj);send(Pj);recv(Pj);send(Pj);死锁正如操作系统中的同步一样，并行系统中同步也会出现死锁问题；如果要通过接收/发送消息实现两进程彼此的同步：PiPjsend(Pi);recv(Pi);send(Pj);recv(Pj);可以看到：若两进程的send例程是同步或阻塞的，则两进程均会等待对方匹配的接收例程而造成死锁。常用的解决办法：两进程的发送和接收例程的顺序