中国科学技术大学分布式算法课件研究生课程.ppt

第二部分第二部分 分布式算法分布式算法汪炀汪炀第二次课第二次课中国科学技术大学计算机系中国科学技术大学计算机系 国家高性能计算中心（合肥）国家高性能计算中心（合肥）坎噎庙籽唾偿休泻保茁扛狭梨粉捻污逛靖别佰荣涎帽腆见亮账睡酪嚏陕摈中国科学技术大学分布式算法课件研究生课程中国科学技术大学分布式算法课件研究生课程12.1.1 系统系统2.异步系统异步系统n异异步步：msg传传递递的的时时间间和和一一个个处处理理器器的的两两个个相相继继步步骤骤之之间间的的时间无固定上界时间无固定上界例例如如，Internet中中，email虽虽然然常常常常是是几几秒秒种种到到达达，但但也也可可能能要要数数天天到到达达。当当然然msg延延迟迟有有上上界界，但但它它可可能能很很大大，且且随随时时间而改变。间而改变。因因此此异异步步算算法法设设计计时时，须须使使之之独独立立于于特特殊殊的的计计时时参参数数，不不能能依赖于该上界。依赖于该上界。n执行片断执行片断一一个个异异步步msg传传递递系系统统的的一一个个执执行行片片断断是是一一个个有有限限或或无无限限的序列：的序列：C0,1,C1,2,C2,3,(C0不一定是初始配置不一定是初始配置)这这里里Ck是是一一个个配配置置，k是是一一个个事事件件。若若是是有有限限的的，则则它它须结束于某个配置，且须满足下述条件：须结束于某个配置，且须满足下述条件：烟些恢共茁坞潞曳苯荚救岁按蜒岛锥岂刷聚晴凸秸琐水释炭蔽粕悉波啼卞中国科学技术大学分布式算法课件研究生课程中国科学技术大学分布式算法课件研究生课程22.1.1 系统系统v若若k=del(i,j,m)，则则m必必是是Ck-1里里的的outbufill的的一一个个元元素素，这这里里ll是是pi的信道的信道pi,pj的标号的标号从从Ck-1到到Ck的的唯唯一一变变化化是是将将m从从Ck-1里里的的outbufill中中删删去去，并并将将其加入到其加入到Ck里的里的inbufjh h中，中，h是是pj的信道的信道pi,pj的标号。的标号。即即：传传递递事事件件将将msg从从发发送送者者的的输输出出缓缓冲冲区区移移至至接接收收者者的的输输入入缓冲区。缓冲区。v若若k=comp(i)，则从，则从Ck-1到到Ck的变化是的变化是改改变变状状态态：转转换换函函数数在在pi的的可可访访问问状状态态(在在配配置置Ck-1里里)上上进进行操作，清空行操作，清空inbufill，(1llr)发发送送msg：将将转转换换函函数数指指定定的的消消息息集集合合加加到到Ck里里的的变变量量outbufi上。上。(Note:发送发送send，传递，传递delivery之区别之区别)即即：pi以以当当前前状状态态(在在Ck-1中中)为为基基础础按按转转换换函函数数改改变变状状态态并并发发出出msg。恳观丘尤讨歇箔倡陪疫妻法桓箍乓阿港动甩彭羌任仕巨整泞遗舵集剂日也中国科学技术大学分布式算法课件研究生课程中国科学技术大学分布式算法课件研究生课程32.1.1 系统系统n执执行行：一一个个执执行行是是一一个个执执行行片片断断C0,1,C1,2,这里这里C0是一个初始配置。是一个初始配置。n调调度度：一一个个调调度度(或或调调度度片片段段)总总是是和和执执行行(或或执执行行片片断断)联联系系在在一一起起的的，它它是是执执行行中中的的事事件件序序列列：1,2,。并并非非每每个个事事件件序序列列都都是是调调度度。例例如如，del(1,2,m)不不是是调度，因为此事件之前，调度，因为此事件之前，p1没有步骤发送没有步骤发送(send)m。若若局局部部程程序序是是确确定定的的，则则执执行行(或或执执行行片片断断)就就由由初初始始配配置置C0和和调调度度(或或调调度度片片断断)唯唯一一确确定定，可可表表示示为为exec(C0,)。彭邮柱镣钉埠变鲤幼控注额氯岩痛袱朗振器恕浓翌剪粟屯拢坊敢师籽傣旺中国科学技术大学分布式算法课件研究生课程中国科学技术大学分布式算法课件研究生课程42.1.1 系统系统n容许执行：容许执行：(满足活跃性条件满足活跃性条件)异异步步系系统统中中，若若某某个个处处理理器器有有无无限限个个计计算算事事件件，每每个发送的个发送的msg都最终被传递，则执行称为容许的。都最终被传递，则执行称为容许的。Note:无无限限个个计计算算事事件件是是指指处处理理器器没没有有出出错错，但但它它不蕴含处理器的局部程序必须包括一个无限循环不蕴含处理器的局部程序必须包括一个无限循环非非形形式式地地说说：一一个个算算法法终终止止是是指指在在某某点点后后转转换换函函数数不改变处理器的状态。不改变处理器的状态。n容许的调度：容许的调度：若它是一个容许执行的调度。若它是一个容许执行的调度。绚奄沃畸用蝉犊闹潭瞎伪噎谷沸债咱锦坠豹驯废淀菇究徘畜赐忿蜂韭娟扮中国科学技术大学分布式算法课件研究生课程中国科学技术大学分布式算法课件研究生课程52.1.1 系统系统3.同步系统同步系统在同步模型中，处理器按锁步骤在同步模型中，处理器按锁步骤(lock-step)执行：执行：执执行行被被划划分分为为轮轮，每每轮轮里里，每每个个处处理理器器能能够够发发送送一一个个msg到到每每个个邻邻居居，这这些些msg被被传传递递。每每个个处处理理器器一一接接到到msg就进行计算。就进行计算。虽虽然然特特殊殊的的分分布布系系统统里里一一般般达达不不到到，但但这这种种模模型型对对于于设设计计算算法法非非常常方方便便，因因为为无无需需和和更更多多的的不不确确定定性性打打交交道道。当当按按此模型设计算法后，能够很容易模拟得到异步算法。此模型设计算法后，能够很容易模拟得到异步算法。n轮轮：在在同同步步系系统统中中，配配置置和和事事件件序序列列可可以以划划分分成成不不相相交交的的轮轮，每每轮轮由由一一个个传传递递事事件件(将将outbuf的的消消息息传传送送到到信信道道上上使使outbuf变变空空)，后后跟跟一一个个计计算算事事件件(处处理理所所有有传传递递的的msg)组组成。成。率乒蕉袍口补堡曾彬钟迹抿塘忱屯星履诫瞳捉映眯砾犬惺夹盐潦蔗讫党喻中国科学技术大学分布式算法课件研究生课程中国科学技术大学分布式算法课件研究生课程62.1.1 系统系统n容许的执行：容许的执行：指无限的执行。指无限的执行。因为轮的结构，所以因为轮的结构，所以每个处理器执行无限数目的计算步，每个处理器执行无限数目的计算步，每个被发送的每个被发送的msg最终被传递最终被传递n同步与异步系统的区别同步与异步系统的区别在一个无错的同步系统中，一个算法的执行只取决在一个无错的同步系统中，一个算法的执行只取决于初始配置于初始配置但在一个异步系统中，对于相同的初始配置及无错但在一个异步系统中，对于相同的初始配置及无错假定，因为处理器步骤间隔及消息延迟均不确定，假定，因为处理器步骤间隔及消息延迟均不确定，故同一算法可能有不同的执行。故同一算法可能有不同的执行。修线爽辐榆尸毗妈往偶督掐嘱薛啤粪贾绥爹箩耗沙薪御戈钩寿脱踌屉含掘中国科学技术大学分布式算法课件研究生课程中国科学技术大学分布式算法课件研究生课程72.1.2 复杂性度量复杂性度量n分布式算法的性能：分布式算法的性能：msg个数和时间。个数和时间。最坏性能、期望性能最坏性能、期望性能n终终止止：假假定定每每个个处处理理器器的的状状态态集集包包括括终终止止状状态态子子集集，每每个个的的pi的的转转换换函函数数对对终终止止状状态态只只能能映映射射到到终终止止状状态态当当所所有有处处理理机机均均处处于于终终止止状状态态且且没没有有msg在在传传输输时时，称系统称系统(算法算法)已终止。已终止。n算算法法的的msg复复杂杂性性(最最坏坏情情况况)：算算法法在在所所有有容容许许的的执行上发送执行上发送msg总数的最大值总数的最大值(同步和异步系统同步和异步系统)慢旋间褥灭彪誓份磅验锡扳斜柿惯喇拌惋闽上妒祟曲雁颧厦嘿赐赚董埠骑中国科学技术大学分布式算法课件研究生课程中国科学技术大学分布式算法课件研究生课程82.1.2 复杂性度量复杂性度量n时间复杂度时间复杂度同同步步系系统统：最最大大轮轮数数，即即算算法法的的任任何何容容许许执执行行直直到到终终止止的的最大轮数。最大轮数。异异步步系系统统：假假定定任任何何执执行行里里的的msg延延迟迟至至多多是是1个个单单位位的的时时间，然后计算直到终止的运行时间间，然后计算直到终止的运行时间n计时执行计时执行(timed execution)指指：每每个个事事件件关关联联一一个个非非负负实实数数，表表示示事事件件发发生生的的时时间间。时时间间起起始始于于零零，且且须须是是非非递递减减的的。但但对对每每个个单单个个的的处处理理器器而而言言是严格增的是严格增的。若若执执行行是是无无限限的的，则则执执行行的的时时间间是是无无界界的的。因因此此执执行行中中的的事件可根据其发生时间来排序事件可根据其发生时间来排序不不在在同同一一处处理理器器上上的的多多个个事事件件可可以以同同时时发发生生，在在任任何何有有限限时间之前只有有限数目的事件发生。时间之前只有有限数目的事件发生。馏削攘丢毫瓤槐瘩晋贪鹰移驶衣脱刘域棱恩郴脏带祖缝敖溪牌漳芭毫渺剧中国科学技术大学分布式算法课件研究生课程中国科学技术大学分布式算法课件研究生课程92.1.2 复杂性度量复杂性度量n消息的延迟消息的延迟发送发送msg的计算事件和处理该的计算事件和处理该msg的计算事件之间所逝去的计算事件之间所逝去的时间的时间它主要由它主要由msg在发送者的在发送者的outbuf中的等待时间和在接收者中的等待时间和在接收者的的inbuf中的等待时间所构成。中的等待时间所构成。n异步算法的时间复杂性异步算法的时间复杂性异步算法的时间复杂性是所有计时容许执行中直到终止的最异步算法的时间复杂性是所有计时容许执行中直到终止的最大时间，其中每个大时间，其中每个msg延时至多为延时至多为1。糟寥仙饲沂捍争荔偿臼汤就闸碎舒溪悸被介爸扰躬靛璃酌菏瘤敝钧苗枉同中国科学技术大学分布式算法课件研究生课程中国科学技术大学分布式算法课件研究生课程102.1.3 伪代码约定伪代码约定在在形形式式模模型型中中，一一个个算算法法将将根根据据状状态态转转换换来来描描述述。但但实实际际上上很很少少这这样样做做，因因为为这这样样做做难于理解。难于理解。实际描述算法有两种方法：实际描述算法有两种方法：叙述性：对于简单问题叙述性：对于简单问题 伪码形式：对于复杂问题伪码形式：对于复杂问题石迂原趴标芽掣匠勤匣寐是妓漳缓嗅诗窿佯娥痒擂充锚杉懂邓山梦惶钒茶中国科学技术大学分布式算法课件研究生课程中国科学技术大学分布式算法课件研究生课程112.1.3 伪代码约定伪代码约定n异步算法：异步算法：对每个处理器，用对每个处理器，用中断驱动中断驱动来描述异步算法。来描述异步算法。在在形形式式模模型型中中，每每个个计计算算事事件件1次次处处理理所所有有输输入入缓缓冲冲区区中中的的msgs。而而在在算算法法中中，一一般般须须描描述述每每个个msg是是如如何何逐逐个个处处理理的的异异步步算算法法也也可可在在同同步步系系统统中中工工作作，因因为为同同步步系系统统是是异异步步系系统统的一个特例。的一个特例。一一个个计计算算事事件件中中的的局局部部计计算算的的描描述述类类似似于于顺顺序序算算法法的的伪伪代代码码描述描述。n同步算法：同步算法：逐轮描述逐轮描述n伪代码约定：伪代码约定：在在pi的的局局部部变变量量中中，无无须须用用i做做下下标标，但但在在讨讨论论和和证证明明中中，加上下标加上下标i以示区别。以示区别。“/”后跟注释后跟注释恫吴叙对犁屋柏璃淮描拱钻夏奋脐佛屠请晒剿亨菩风漆国舍柑帧给邮室舟中国科学技术大学分布式算法课件研究生课程中国科学技术大学分布式算法课件研究生课程122.2 生成树上的广播和汇集生成树上的广播和汇集 信信息息收收集集及及分分发发是是许许多多分分布布式式算算法法的的基基础础。故故通通过过介介绍绍这这两两个个算算法法来来说说明明模模型型、伪伪码码、正正确确性性证证明明及及复复杂杂性性度度量量等等概念。概念。2.2.1 广播广播(Broadcast)假假定定网网络络的的生生成成树树已已给给定定。某某处处理理器器pr希希望望将将消消息息M发发送至其余处理器。送至其余处理器。假假定定生生成成树树的的根根为为pr，每每个个处处理理器器有有一一个个信信道道连连接接其其双亲双亲(pr除外除外)，有若干个信道连接其孩子。，有若干个信道连接其孩子。由于分布式系统中，每个节点并不知道全局拓扑，但某些算法需要由于分布式系统中，每个节点并不知道全局拓扑，但某些算法需要在特定结构下才能达到最优，比如广播在特定结构下才能达到最优，比如广播/敛播在树结构下才能达到敛播在树结构下才能达到消息复杂度最优，因此构造生成树是必要的，是其他算法的基础。消息复杂度最优，因此构造生成树是必要的，是其他算法的基础。织庶欣炬六林铡截钻妄翅瞥卯穆柒梳肄锁残患丈瞬哀疚滇妹困驶峭眠瑶剁中国科学技术大学分布式算法课件研究生课程中国科学技术大学分布式算法课件研究生课程132.2.1 广播广播l根根pr发发送送M给给所所有孩子。有孩子。(a)l当当某某结结点点收收到到父父结结点点的的M时时，发发送送M到到自自己己的所有孩子的所有孩子(b)。荤思记盼潘边茁啡希隔富红灼阶败蛮葫雍睛舵叠腰剥坏花翼匣拧敏剪阐脉中国科学技术大学分布式算法课件研究生课程中国科学技术大学分布式算法课件研究生课程142.2.1 广播广播1.伪码算法伪码算法Alg2.1 Broadcast pr:/发动者。假设初始化时发动者。假设初始化时M已在传输状态已在传输状态1.upon receiving no msg:/pr发送发送M后执行终止后执行终止2.terminate;/将将terminated置为置为true。pi(ir,0i n-1):3.upon receiving M from parent:4.send M to all children;5.terminate;2.用状态转换来分析算法用状态转换来分析算法n每个处理器每个处理器pi包含状态包含状态变量变量parenti：表示处理器：表示处理器pi双亲结点的标号或为双亲结点的标号或为nil(若若i=r)变量变量childreni：pi的孩子结点标号的集合的孩子结点标号的集合布尔变量布尔变量terminatedi：表示：表示pi是否处于终止状态是否处于终止状态撰骏闽辨彝蔚录晓惮圾屋叠吏衔位时坯遵确团杯挚慕懦尘晰嗽道制少抵子中国科学技术大学分布式算法课件研究生课程中国科学技术大学分布式算法课件研究生课程152.2.1 广播广播n初始状态初始状态vparent和和children的值是形成生成树时确定的的值是形成生成树时确定的v所有所有terminated的值均为假的值均为假voutbufr j,jchildrenr持持有有消消息息M，注注意意j不不是是信信道道标标号号，而而是是r的的邻邻居居号号。（任任何何系系统统中中，均假定各节点标号互不相等）均假定各节点标号互不相等）v所有其他结点的所有其他结点的outbuf变量均为空。变量均为空。ncomp(i)的结果的结果若若 对对 于于 某某 个个 k，M在在 inbufik里里，则则 M被被 放放 到到outbufi j 里，里，jchildreni献嗽剪眶旷攒祟芦阶可匿谬屋粘拳禾蹬涅取哟阵脐裳十昭涸吩波炽芜植焊中国科学技术大学分布式算法课件研究生课程中国科学技术大学分布式算法课件研究生课程162.2.1 广播广播npi进入终止状态进入终止状态将将terminatedi置置为为true；若若i=r且且terminatedr为为false，则，则terminatedr立即置为立即置为true，否则空操作。，否则空操作。n该该算算法法对对同同步步及及异异步步系系统统均均正正确确，且且在在两两模模型型中，中，msg和时间复杂度相同。和时间复杂度相同。nMsg复杂度复杂度无无论论在在同同步步还还是是异异步步模模型型中中，msg M在在生生成成树树的的每每条边上恰好发送一次。条边上恰好发送一次。因此，因此，msg复杂性为复杂性为n-1。墒媒家美吮能点礁诅憨毅嘿绞阴苟圭染荡甭亚傍摇鄙漳狙拾圆盔扼烛寿赐中国科学技术大学分布式算法课件研究生课程中国科学技术大学分布式算法课件研究生课程172.2.1 广播广播n时间复杂性：时间复杂性：同步模型：同步模型：时间由轮来度量。时间由轮来度量。Lemma2.1 在在同同步步模模型型中中，在在广广播播算算法法的的每每个个容容许许执执行行里，树中每个距离里，树中每个距离pr为为t的处理器在第的处理器在第t轮里接收消息轮里接收消息M。pf：对距离对距离t使用归纳法。使用归纳法。归归纳纳基基础础：t=1，pr的的每每个个孩孩子子在在第第1轮轮里里接接收收来来自自于于pr的消息的消息M归归纳纳假假设设：假假设设树树上上每每个个距距pr为为t-11的的处处理理器器在在第第t-1轮轮里已收到里已收到M。归归纳纳步步骤骤：设设pi到到pr距距离离为为t，设设pj是是pi的的双双亲亲，因因pj到到pr的的距距离离为为t-1，由由归归纳纳假假设设，在在第第t-1轮轮pj收收到到M。由由算算法法描述知，在第描述知，在第t轮里轮里pi收到来自于收到来自于pj的消息的消息MTh2.2 当当生生成成树树高高度度为为d时时，存存在在一一个个消消息息复复杂杂度度为为n-1，时间复杂度为，时间复杂度为d的同步广播算法的同步广播算法砧憋骗篙竹铲夜契耐陪譬讶沾悲葵腿心臣开卸唬乏词蝉涧境才燥召月揣湖中国科学技术大学分布式算法课件研究生课程中国科学技术大学分布式算法课件研究生课程182.2.1 广播广播异步异步模型模型Lemma2.3 在在异异步步模模型型的的广广播播算算法法的的每每个个容容许许执执行行里里，树中每个距离树中每个距离pr为为t的处理器至多在时刻的处理器至多在时刻t接收消息接收消息M。pf：对距离对距离t做归纳。做归纳。对对t=1，初初始始时时，M处处在在从从pr到到所所有有距距离离为为1的的处处理理器器pi的的传传输输之之中中，由由异异步步模模型型的的时时间间复复杂杂性性定定义义知知，pi至至多在时刻多在时刻1收到收到M。pi 距距pr为为t的的处处理理器器，设设pj是是pi的的双双亲亲，则则pj与与pr的的距距离离为为t-1，由由归归纳纳假假设设知知，pj至至多多在在时时刻刻t-1收收到到M，由算法描述知，由算法描述知，pj发送给发送给pi的的M至多在至多在t时刻到达。时刻到达。Th2.4 同同Th2.2摧次饭那式酪娱嘉淡芯仍旧路倦诽刀纬仗钾抬弃盆啄寨簧耕郭恐烩谤愉赋中国科学技术大学分布式算法课件研究生课程中国科学技术大学分布式算法课件研究生课程19下次继续！下次继续！砌脏宗沥谣谜任丧严扣迪晒举倾觉湘跳占洋素刨斜啄夸拣劝盗猫恨计蹭庶中国科学技术大学分布式算法课件研究生课程中国科学技术大学分布式算法课件研究生课程20