第二部分 分布式算法 汪炀 第二次课 中国科学技术大学计算机系 国家高性能计算中心(合肥)

Slides:



Advertisements
Similar presentations
渡黑水溝 郁永河. 2 戎克船:是明末清初時期往返兩岸的主要交通工具 ∗ 1. 關於台灣的開發歷史,我們到底了解多少呢?不妨試著說出 就我們所知有關台灣開發史的故事、小說、電影、音樂與大 家分享。 ∗ 2. 什麼是黑水溝?黑水溝為什麼會成為大陸移民渡海來臺時最 大的威脅? ∗ 3. 有聽過「六死三留一回頭」、「有唐山公,無唐山嬤」這兩.
Advertisements

历尽九九八十一难, 唐僧四人终于到达天竺, 取得真经,完成任务。 四人想着难得到天竺一趟, 不如在此游览一番。
2007 年 6 月 楚雄师范学院计科系 离 散 数 学 第三章 逻辑代数 ( 上 ) 命题演算.
一、中国湿地面临的威胁 目前,湿地污染严重,湖泊 富营养化问题突出。随着社 会经济的快速发展,湿地污 染在很长时期内依然严重。 湿地污染 1.
中共盘县发展和改革局党组主体责任落实情况报告
我们毕业了 毕业留念册 再见老师 姓名:黄巧灵 班级:六(1)班 毕业时间:2012年6月.
专题二:城市化与城乡规划 授课教师:周栋文.
食物安全計劃 — 刺身/壽司 訓練資料 食物安全中心.
第二章 城市轨道交通系统的构成 城市轨道交通系统的分类 2.1 2.2 车辆与车辆段 2.3 轨道交通限界
延庆县“十二五”时期城乡基础设施 建设规划 2011年03月.
2011届高三地理高考复习课件 拉丁美洲 高三地理备课组.
滚 滚 长 江 安匠初中:李艳阁.
长江的开发 惠州市河南岸中学 谢国文.
新編多元性向測驗 測驗說明 輔導室
白海豚的分布范围.
什么是伸展? 无论你是久坐的生活型态或是爱好运动的人,伸展可让你身体柔软,为接下来的动作做好准备,也可以让运动后的肌肉柔缓放松。
愛情路上慢慢走 賴佳琳
超视距安保防范系统 克拉玛依市格恩赛电子科技有限公司 2015年8月.
合能锦城项目招商手册 合能地产
在《命运交响曲》 音乐声中 安静我们的心 迎接挑战.
-矿产资源勘查开采的有关法律知识介绍 四川省国土资源厅 陈东辉
第二十章 第3节 电磁铁 电磁继电器.
盘江煤层气公司 页岩气、煤层气基础知识培训
101年國中畢業生多元進路宣導 國中部註冊組 100年10月29日.
高中職優質化專題 教育研究博士班二年級 游宗輝.
海星國中部直升方案說明 報告人:教務處 陳博文主任
颈椎移位.
101年度十二年國民基本教育 國民中學校長專業研習 校長落實補救教學、適性輔導 中輟生的預防與復學輔導之實務作為
长江.
歡迎各位老師 蒞校參訪 召集人、各位委員、同仁大家好,我是林淑玟,負責教務行政進行簡報 報告人:林淑玟 中華民國九十九年三月二十三日.
大學甄選入學 選填志願輔導說明會 曾文農工輔導室.
陆路交通发达,公路、铁路交通为主,基本上没有水运
一所具有悠久歷史與優良傳統的 優質學校 強調生活教育與精緻教學 是您有心向學的最佳選擇.
第二章 工程造价计价依据第一节 施工定额 概 述 工作时间的研究分析 劳动定额 材料消耗定额
國立嘉義高級工業職業學校 101年度綜合高中宣導研習 國立嘉義高工 教務主任 林章明
103年高雄市自然與生活科技學習領域教學研習 動物單元的 教學理念與實踐 講師:屏東縣和平國小 周鳳文.
神 山 圣 湖.
世界地理总论 人文地理概况.
第四章 水域生物群.
东京城市建设史简述.
海軍軍官學校 士官二專班 招生簡報 、 第1頁,共30頁.
海軍軍官學校 士官二專班 103學年度 招生簡報.
贵州讲解.
院系:政史学院历史系 班级:10级4班 学号: 姓名:蒋阿晴
有大权炳的天使 (18:1-3) 巴比伦大城倾倒了!倾倒了! 天上的声音 (18:4-20) (4-8) 一天之内,她的灾殃要一齐来到。
合肥公交集团 营运效能分析报告 营 运 服 务 部.
小白兔愛跳舞,月夜光下學跳舞 時光一去不回,不要耽誤快快快 朋友們呀大家快來,不要耽誤快快快
企业引进顶级人才之门, 人才跨上顶级职业之路 。
新疆旅游资源 ——伊犁哈萨克自治州.
中学生心理健康讲座 打开心灵之门 开启阳光之路 主讲人:范荃.
路程、时间与速度 ——北师大版四年级数学上册 成都市武顺街小学 漆智妮.
沟壑纵横的 沟壑纵横的黄土高原(用稿) 黄土高原.
员工培训制度设计方案 相关内容可参照“派力营销思想库” 《销售培训手册》 《培训学习手册》 《培训游戏大全》 《培训控密》
Minimum Spanning Trees
教育部宣導專員 國立臺中家商 許敏政主任 101年2月23日製作 #201~203
程式語言Visual Basic 重複結構 黃瀧輝 老師 Long Hwai,Huang.
进程操作.
第二部分 分布式算法 汪炀 第二次课 中国科学技术大学计算机系 国家高性能计算中心(合肥)
中国科学技术大学计算机系 国家高性能计算中心(合肥)
十二年國民基本教育 103學年度高中高職及五專 入學方式與就學區規劃 (草案諮詢稿)
经典算法之 冒 泡 排 序.
高中職多元進路 家長說明會 主講人: 東莞台商子弟學校 麥馨月 日 期:
98年度兒童課後照顧學程 修課名單確認暨課程說明會 2009/09/15(二) 08:40~09:20.
河口生態系 紅樹林.
中国科学技术大学计算机系 国家高性能计算中心(合肥)
國立嘉義高級工業職業學校 101年度雲嘉區綜合高中宣導研習 國立嘉義高工 綜高高中學務組長 呂明欣
99年基測暨直升、原藝班、 申請、甄選入學報名作業說明
臺灣北區102學年度高級中等學校 舞蹈班暨聯合甄選入學術科測驗 暨甄選入學說明會
台中市黎明國中105學年度 學生報考 一般智能暨學術性向資賦優異學生鑑定 報名流程說明
Presentation transcript:

第二部分 分布式算法 汪炀 第二次课 中国科学技术大学计算机系 国家高性能计算中心(合肥) 第二部分 分布式算法 汪炀 第二次课 中国科学技术大学计算机系 国家高性能计算中心(合肥)

§2.1.1 系统 2.异步系统 异步:msg传递的时间和一个处理器的两个相继步骤之间的时间无固定上界 例如,Internet中,email虽然常常是几秒种到达,但也可能要数天到达。当然msg延迟有上界,但它可能很大,且随时间而改变。 因此异步算法设计时,须使之独立于特殊的计时参数,不能依赖于该上界。 执行片断 一个异步msg传递系统的一个执行片断α是一个有限或无限的序列: C0, Φ1, C1, Φ2, C2, Φ3, … , (C0不一定是初始配置) 这里Ck是一个配置, Φk是一个事件。若α是有限的,则它须结束于某个配置,且须满足下述条件:

§2.1.1 系统 若Φk =del(i,j,m),则m必是Ck-1里的outbufi[l]的一个元素,这里l是pi的信道{pi,pj}的标号 从Ck-1到Ck的唯一变化是将m从Ck-1里的outbufi[l]中删去,并将其加入到Ck里的inbufj[h]中,h是pj的信道{pi,pj}的标号。 即:传递事件将msg从发送者的输出缓冲区移至接收者的输入缓冲区。 若Φk =comp(i),则从Ck-1到Ck的变化是 ①改变状态:转换函数在pi的可访问状态(在配置Ck-1里)上进行操作,清空inbufi[l],(1≤l≤r) ②发送msg:将转换函数指定的消息集合加到Ck里的变量outbufi上。(Note:发送send,传递delivery之区别) 即: pi以当前状态(在Ck-1中)为基础按转换函数改变状态并发出msg。

§2.1.1 系统 执行:一个执行是一个执行片断C0, Φ1, C1, Φ2, … ,这里C0是一个初始配置。 调度:一个调度(或调度片段)总是和执行(或执行片断)联系在一起的,它是执行中的事件序列:Φ1, Φ2, … 。 并非每个事件序列都是调度。例如,del(1,2,m)不是调度,因为此事件之前,p1没有步骤发送(send)m。 若局部程序是确定的,则执行(或执行片断)就由初始配置C0和调度(或调度片断)σ唯一确定,可表示为exec(C0 , σ)。

§2.1.1 系统 容许执行:(满足活跃性条件) 异步系统中,若某个处理器有无限个计算事件,每个发送的msg都最终被传递,则执行称为容许的。 Note: 无限个计算事件是指处理器没有出错,但它不蕴含处理器的局部程序必须包括一个无限循环 非形式地说:一个算法终止是指在某点后转换函数不改变处理器的状态。 容许的调度: 若它是一个容许执行的调度。

§2.1.1 系统 3.同步系统 在同步模型中,处理器按锁步骤(lock-step)执行: 执行被划分为轮,每轮里,①每个处理器能够发送一个msg到每个邻居,这些msg被传递。②每个处理器一接到msg就进行计算。 虽然特殊的分布系统里一般达不到,但这种模型对于设计算法非常方便,因为无需和更多的不确定性打交道。当按此模型设计算法后,能够很容易模拟得到异步算法。 轮:在同步系统中,配置和事件序列可以划分成不相交的轮,每轮由一个传递事件(将outbuf的消息传送到信道上使outbuf变空),后跟一个计算事件(处理所有传递的msg)组成。

§2.1.1 系统 容许的执行:指无限的执行。 因为轮的结构,所以 每个处理器执行无限数目的计算步, 每个被发送的msg最终被传递 同步与异步系统的区别 在一个无错的同步系统中,一个算法的执行只取决于初始配置 但在一个异步系统中,对于相同的初始配置及无错假定,因为处理器步骤间隔及消息延迟均不确定,故同一算法可能有不同的执行。

§2.1.2 复杂性度量 分布式算法的性能: 终止:假定每个处理器的状态集包括终止状态子集,每个的pi的转换函数对终止状态只能映射到终止状态 消息复杂度 时间复杂度 空间复杂度 性能衡量:最坏性能、期望性能 终止:假定每个处理器的状态集包括终止状态子集,每个的pi的转换函数对终止状态只能映射到终止状态 当所有处理机均处于终止状态且没有msg在传输时,称系统(算法)已终止。

§2.1.2 复杂性度量 算法的msg复杂性(最坏情况):算法在所有容许的执行上发送msg总数的最大值(同步和异步系统) 消息复杂度度量 消息复杂度:消息总数/消息中总的位数长度 消息总数:4/4 消息位数总长度(位复杂度):14/8

§2.1.2 复杂性度量 时间复杂度 ①同步系统:最大轮数,即算法的任何容许执行直到终止的最大轮数。 ②异步系统:假设:①节点计算任何有限数目事件的时间为0;②一条消息发送和接收之间的时间至多为1个时间单位,定义为:所有计时容许执行中直到终止的最大时间。 计时执行(timed execution) 指:每个事件关联一个非负实数,表示事件发生的时间。时间起始于零,且须是非递减的。但对每个单个的处理器而言是严格增的。 若执行是无限的,则执行的时间是无界的。因此执行中的事件可根据其发生时间来排序 不在同一处理器上的多个事件可以同时发生,在任何有限时间之前只有有限数目的事件发生。

§2.1.2 复杂性度量 消息的延迟 异步算法的时间复杂性 ①一条消息发送和接收之间时间恰好为1个时间单位 发送msg的计算事件和处理该msg的计算事件之间所逝去的时间 它主要由msg在发送者的outbuf中的等待时间和在接收者的inbuf中的等待时间所构成 异步算法的时间复杂性 定义中,每个msg延时至多为1,但实际中,至多1个时间单位会很难计算,因此修改假设: ①一条消息发送和接收之间时间恰好为1个时间单位 ②一条消息发送和接收之间时间介于α和1之间(0< α<1) ③假设消息传递的延迟满足某种概率分布,并由此来计算

§2.1.3 伪代码约定 在形式模型中,一个算法将根据状态转换来描述。但实际上很少这样做,因为这样做难于理解。 实际描述算法有两种方法: ①叙述性:对于简单问题 ②伪码形式:对于复杂问题

§2.1.3 伪代码约定 异步算法:对每个处理器,用中断驱动来描述异步算法。 在形式模型中,每个计算事件1次处理所有输入缓冲区中的msgs。而在算法中,一般须描述每个msg是如何逐个处理的 异步算法也可在同步系统中工作,因为同步系统是异步系统的一个特例。 一个计算事件中的局部计算的描述类似于顺序算法的伪代码描述。 同步算法:逐轮描述 伪代码约定: —在pi的局部变量中,无须用i做下标,但在讨论和证明中,加上下标i以示区别。 —“//”后跟注释

§2.2 生成树上的广播和汇集 为什么广播和汇集算法 信息收集(敛播/汇集)及分发(广播)是许多分布式算法的基础。故通过介绍这两个算法来说明模型、伪码、正确性证明及复杂性度量等概念。 为什么生成树上?  由于分布式系统中,每个节点并不知道全局拓扑状态,但某些算法需要在特定的结构下才能达到最优。例如:广播/敛播在树结构下才能达到消息复杂度最优,因此构造生成树是必要的,且是其他算法的基础。

§2.2 生成树上的广播和汇集 生成树 最小生成树 生成树一共有16棵 1 1 2 1 2 3 1 2 最小生成树 4 一个无向连通图G的生成树(Spanning Tree)是指满足下列条件的G的子图T: ①G和T具有相同的顶点数; ②在T中有足够的边能够连接G的所有顶点且不出现回路。 最小生成树 如果图的每一条边都指定有一个权,那么所有的边权最小的生成树,就成为最小代价生成树(Minimum Cost Spanning Tree, MCST) ,简称最小生成树(MST)。 生成树一共有16棵 1 1 2 1 2 3 1 2 最小生成树 4

假定网络的生成树已给定。某处理器pr希望将消息M发送至其余处理器。 §2.2 生成树上的广播和汇集 §2.2.1 广播 (Broadcast) 假定网络的生成树已给定。某处理器pr希望将消息M发送至其余处理器。 假定生成树的根为pr ,每个处理器有一个信道连接其双亲(pr除外),有若干个信道连接其孩子。

§2.2.1 广播 根pr发送M给所有孩子。(a) 当某节点收到父节点的M时,发送M到自己的所有孩子(b)。

§2.2.1 广播 1.伪码算法 2.用状态转换来分析算法 Alg2.1 Broadcast pr: //发动者。假设初始化时M已在传输状态 1. upon receiving no msg: //pr发送M后执行终止 2. terminate; //将terminated置为true。 pi(i≠r,0≤i ≤ n-1): 3. upon receiving M from parent: 4. send M to all children; 5. terminate; 2.用状态转换来分析算法 每个处理器pi包含状态 —变量parenti:表示处理器pi双亲节点的标号或为nil(若i=r) —变量childreni:pi的孩子节点标号的集合 —布尔变量terminatedi:表示pi是否处于终止状态

§2.2.1 广播 初始状态 comp(i)的结果 parent和children的值是形成生成树时确定的 所有terminated的值均为假 outbufr[ j ], j∈childrenr持有消息M,注意j不是信道标号,而是r的邻居号。(任何系统中,均假定各节点标号互不相等) 所有其他节点的outbuf变量均为空。 comp(i)的结果 若对于某个k,M在inbufi[k]里,则M被放到outbufi[ j ]里, j∈childreni

§2.2.1 广播 pi进入终止状态 该算法对同步及异步系统均正确,且在两模型中,msg和时间复杂度相同。 Msg复杂度 将terminatedi置为true;若i=r且terminatedr为false,则terminatedr立即置为true,否则空操作。 该算法对同步及异步系统均正确,且在两模型中,msg和时间复杂度相同。 Msg复杂度 无论在同步还是异步模型中,msg M在生成树的每条边上恰好发送一次。 因此,msg复杂性为n-1,即O(n)。 时间复杂度为h,即O(h),其中h为生成树的高度。

§2.2.1 广播 说明: 本算法中While并不代 表循环,而是代表满足 条件时,节点所做的动作 输入:根节点上的消息<m> Code for Pi Begin while (receiving no message) do (1) if i=r then \\此节点为根节点 (1.1) send <m> to all children (1.2) terminates end if end while while (receiving <m> from Pj) do (1) send <m> to all children (2) terminates end 说明: 本算法中While并不代 表循环,而是代表满足 条件时,节点所做的动作

§2.2.1 广播 时间复杂性: ①同步模型:时间由轮来度量。 Lemma2.1 在同步模型中,在广播算法的每个容许执行里,树中每个距离pr为t的处理器在第t轮里接收消息M。 pf:对距离t使用归纳法。 归纳基础:t=1,pr的每个孩子在第1轮里接收来自于pr的消息M 归纳假设:假设树上每个距pr为t-1≥1的处理器在第t-1轮里已收到M。 归纳步骤:设pi到pr距离为t,设pj是pi的双亲,因pj到pr的距离为t-1,由归纳假设,在第t-1轮pj收到M。由算法描述知,在第t轮里pi收到来自于pj的消息M Th2.2 当生成树高度为d时,存在一个消息复杂度为n-1,时间复杂度为d的同步广播算法

§2.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

下次继续!