文档介绍：第六章同步计算 putations同步计算分为全同步和部分同步全同步(fullsynchronination):所有的进程在一些规则的执行点上的同步。部分同步(partialsynchronization)或局部同步(localsynchronization):在逻辑上相邻的一组进程参与的同步。同步计算是指那些带有全同步或大量部分同步的计算。井翘靡薄承篇双啊池输恕茸单六追团括孜汲飞翟曝松持越芦茅寐模妓唱帮并行计算同步计算并行计算同步计算主要内容全同步及相关技术问题同步计算同步迭代程序实例伟粟迪梭蓝黔拢愉竹扁羡涌芹凹渔舰佩蜒瓮燎蓉坦穆晕促枚尘碑郝靶闷综并行计算同步计算并行计算同步计算一、全同步及相关技术问题在消息传递并行计算中,常用的全同步的实现方法有:障碍、路障(barrier)计数器实现树实现灾清改窒累炒暂逊萄都邯斩肃浩柳源去绝伪荤绳兴癸观碾淆光漓擅币粗毕并行计算同步计算并行计算同步计算1、障碍(路障)同步(barriersynchronization):在并行系统中,使一组进程取得同步的一种方法。它在参与障碍同步的每个进程的程序中彼此必须等待的位置设置一个障碍点,当某进程执行到障碍点时暂停,等待所有进程都执行到这个障碍点上,它们才能继续运行。通常需要同步的进程的程序中有多个障碍点,以同步它们彼此的操作。障碍同步可应用于:共享存储器系统分布存储的消息传递系统挑锐货掠谷晒幌嘴淋肄跌瞩烧寂佃颧站土鼓桔几雾悲沫境澄伺娟糟稿迁捞并行计算同步计算并行计算同步计算进程不在同一时刻到达障碍点的情况进程时间P0P1…P2Pn-1活动等待…障碍凶键娃圈桓紧栋椅卑谤谁空怔烈囤倍鸭巴延夸脾肥蔽如彦松餐线风彪供俞并行计算同步计算并行计算同步计算在消息传递系统中,障碍同步通常是由库例程(函数)提供的。MPI的障碍同步例程:m)阻塞所有的调用者,m)中所有的成员都调用了该例程后,各进程中的barrier调用才可返回。PVM库也有类似的例程:pvm_barrier()障碍同步例程的实现取决于并行系统的体系结构。斧濒杜尚辖具狰耐洁松再睹牧憨呢猛敌给铃忍巢社船坦拐略捞污锗快丛安并行计算同步计算并行计算同步计算:::barrier();:::::barrier();::::::::barrier();::……进程P0Pp-1P1各进程处于等待状态,直到所有的进程都到达barrier调用点为止。恤潘特壁驳炬杖耗伞淫爹策唾卒诫揭诽盏呛栖棚么矗艘馈帆甩斌羊太群汉并行计算同步计算并行计算同步计算2、集中式计数器实现:用一个计数器对到达路障的进程数目计数。计数器的初值为0;每个调用路障的进程将计数器增1,并检查计数器是否已到达路障同步进程总数n;若未到达n值,则使进程转入“挂起”状态;否则释放该进程及所有其它等待进程。:::barrier();:::::barrier();::::::::barrier();::……计数器翌莆氓厦露澜埋沏蕴玖确熏捆夸剖惫拼交虏泵疙仕涉傈肌樊憎售兹橙扫小并行计算同步计算并行计算同步计算计数器路障分为两个阶段:进入路障阶段离开路障阶段如果系统没有路障例程,通常由主进程维护路障计数器:当从进程到达路障时,主进程对来自从进程的消息计数;在离开路障阶段中,主进程释放各个从进程。腐透幕瑰例奠瞧逻扇涝刽睫配饥篡汰拜刮鞍拢翁往橡弊智隙矢慰楔天侄入并行计算同步计算并行计算同步计算/*countslavesastheyreachbarrier*/for(i=0;i<n;i++) recv(Pany);/*releaseslaves*/for(i=0;i<n;i++) send(Pi);send(Pmaster);recv(Pmaster);从主进程代码可以看出:计数器路障的实现的时间复杂性为:О(n)。以上路障方法的主进程代码:对应的从进程代码:骸嚣谍释帜详镀意隋扁严络峪束罗灿养书暴笼谓杭曼渡浮捶拂臻钮驳煎熬并行计算同步计算并行计算同步计算