13计算机系统结构52

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,5.3 路由选择和信息传递,互连网络的基本功能是.,源结点,和,目的结点,间通信时，信息经,中间结点,进行,传递,。,:,实现经中间结点,传,递功能的通信方法和算法，叫,(,或,),选择,。,寻径(算法）,网络结点间有,静态、动态,两种。,静态法:,在程序执行前预先配置好通路，并在程序执行过程中一直保持。程序需求事先已知。,动态法:,大部分情况，程序事先并不能预测，即按需求动态建立通信通路。需采用,动态法,.,1,寻径算法,寻径,决定发送一个消息到其目的地所经过的路径。分为：,确定性算法,：,路径选择只依赖于它所发送的消息的,源结点,和,目的结点,。,自适应算法,：消息从结点,A,到结点,B,有几条不同的路径。路径选择要根据,通信资源,或,网络情况,来定,.,优点是可以避开拥挤的或有故障的结点，改进网络资源的利用率,提高网络上的吞吐量。,2,实例,通路选择方法,确定性选择:,信息包,先沿X方向,传送，后,沿Y方向,传送。当一行有两个以上源结点时，通路选择可能发生冲突。,确定性,算法简单、路径短，但适应性不强。遇冲突或故障时，无法改选其他通路。,3,典型的确定性寻径算法,X-Y寻径算法,和,E-立方寻径算法,。前者用于二维网络，后者用于超立方互连网络。,(1) X-Y寻径算法,在二维互联网络中选择路由时，首先,沿着,X维方向,确定路径，,然后沿着,Y维方向,选择路径。,假定,源结点,s,=(X1，Y1)，,目的结点,d=(X2，Y2)。寻径从,s,开始，沿着,X方向前进一直到,d,所在的第,X2,列为止，然后沿,Y方向前进直到d。,X-Y,寻径有四种模式：,东,-北，东-南，西-北，西-南。,X-Y,算法在,源,和,目的结点,间形成最短路径。,X-Y,算法可扩充到,n维网络，如X-Y-Z三维寻径算法。,4,【例】,二维网格计算机,X-Y寻径,过程如图所示，确定,源结点,到,目标结点,的最短距离。,结点,(,2，1,)到结点,(7，6)， 东-北,路径。 结点,(,5，4),到结点,(,2，0,)，,西,-南,路径。 结点,(,0，7),到结点,(,4，2)， 东-南,路径。 结点,(,6，3,)到结点(,1，5,)，,西,-北,路径。,5,（,2） E-立方路由算法,确定一个n立方体上任意两结点的最小路径。,问题：假设一个n立方体的结点的码为,b=bn-1bn-2b1b0,。源结点,s=sn-1sn-2s1s0,，目的结点d,=dn-1dn-2d1d0,。,如何确定一条从s到d的最小路径？,6,E-立方路由算法,方法：,设,v=vn-1vn-2v1v0是路径中的任一结点。可根据以下算法确定路径：,1 .计算方向位 ri=si-1,di-1，其中i=1 ，n。令i=1，v=s。,-异或,2.若ri=1,则从当前结点v寻径到下一结点,。若ri=0，则跳过这一步。,3.i=i+1。若i0111-0101-1101,=d,。,8,信息传递方式,信息通常由,消息、包,和,片,组成,。,1 消息,：,节点之间通讯的,逻辑单位,，由任意数目、长度固定的,包,组成。消息长度是可变的,。,2 包,：,包含,寻径地址,的,基本单位，,包,包含一个标识数（进程ID），能把传递消息送到,目的结点,.,不同的包可异步到达，并重新组装。长度随协议而异，通常 64-512位。,3 片：,包进一步等分成更小的,“,片,”,，,长度一般为8位。片,是,通路,所能处理的,最小单位,。寻径信息和ID等信息形成,头片（,报头），其余为数据片。,9,消息、包和片的关系,10,一台机器发送消息,发送给,另一台机器时,发送方步骤：,发送数据拷贝到,操作系统缓冲区,。,把,发送数据,加到,消息中,，启动超时计数器。,缓冲区,消息送到网络接口,硬件，通知硬件开始发送。,接受方步骤：,从网络接口,接受数据并拷贝到系统缓冲区。,计算和检查发送来的数据,，无误则发回一个信号，并把接受数据拷贝到用户地址空间。,否则，删除消息。启动超时计数器。,信息传递方式,11,信息传递方式,信息传递分,线路交换,和,分组交换（包交换）,两类。,线路交换,传递信息之前，先建立一条从源结点到目的结点的物理通路，然后再传递信息。,分组交换有,：,存储转发,虚拟直通,虫孔方式,12,信息传递方式,(1) 线路交换 ：,传递信息之前，先建立一条从源结点到目的结点的物理通路。传输时延T公式表示为,T=(L+ Lt D)/B,L为消息包的长度,Lt为建立路径所需的,最小消息包,的长度,D为经过的结点数。 B,为带宽。,优点：,包经中间结点时不把,包,存储起来，实际通信时间较短，使用缓冲区少，适合于具有动态和突发特性的大规模并行处理数据传送,。,缺点：,1,物理通道非共享。传输过程中通道一直被占用。,2,若频繁建立,源,到,目的结点,的通路，时间开销大。,13,(2) 存储转发,“,包,” 经过中间结点时，中间结点先把“,包”,全部存储起来，然后再传递给下一个结点，直至到达,目的结点,。,时延,T公式：,T=(D+1)L/B,L为消息包的长度,存储转发中，网络时延与,源和目的地间距离,成正比。,第一代多计算机系统常采用,存储转发,方式,14,信息传递方式,存储转发中，,包是信息流的基本单位，每个结点有一个包缓冲存储器。,缺点：,1.包缓冲区大，不利于VLSI实现；,2.网络时延大，与结点距离成正比。,存储转发示意图,15,(3),虚拟直通,虚拟直通,:,思想是减少存储转发中,包存储时延,，包不必全部存入缓冲后再做路由判断，只要接收到用作寻径信息（头部），即进行路由选择。,如结点的输出链路空闲，包立即转送到,下一个结点,。如整个通路都空闲，包直达,目的结点,，如同,线路交换,如果没有空闲链路时或出现寻径阻塞时，再将整个信息全部存储在寻径结点中。等,同存储转发。,虚拟直通时延T公式：,T=(L+LhD)/BL/B (5.10),式中Lh是,信息包寻径头部的长度,。,LLhD，T,L/B。时延与结点数无关,（D的影响小）,16,虚拟直通,缺点：,1 每个结点中需要有缓冲。以便没有空闲链路时，要用缓冲器存储。,2 包缓冲区大，不利于VLSI实现；,示意图,17,信息传递方式,(4),虫孔(wormhole)方式,把信息包进一步分为更小的,“片”,(flit),。片是,通路能传输,的,最小单位,。数据片串行传输,(数据包流水传输)。,报头,部分为一个“,头片,”。头片,包含寻径信息,。“片“可减小结点中缓冲器的容量，缩短延迟时间。,特点：,“片“可减小结点中缓冲器的容量，传输延迟略大于线路交换，网络冲突较小。,18,T=TfD+L/B=(L+LfD)/BL/B (5.11),Lf是片的长度，Tf是,片,经过一个结点所需时间,LLfD。,通信时延与结点数无关。,优点：,1.结点缓冲器较小，易于VLSI实现；,2.传输时延低；,3.通道共享性好，利用率高；,4.易于实现选播和广播通信模式。,缺点,:,一个片被阻塞时，整个信息的所有片都将被阻塞在所在结点。,虫孔方式,时延,T,为：,19,虫孔,(wormhole)方式,每个结点上只需要,缓冲一个片,就能满足要求。,头片,开辟一条从,输入,链路到,输出,链路的路径。,消息中,片,以,流水方式,在网络中向前“蠕动”或爬行。,20,网络中通道缓冲区已满时，若各消息路径,构成闭环,时会产生,死锁。,称为,路由死锁：,两个结点间都向对方发送消息，两个结点之间抢占共享物理链路而导致,死锁,。,迎面死锁：,死锁的解决方法,-,虚拟通道技术,1 死锁,与,虚拟通道,21,虚拟通道,特点：,是两个结点间的逻辑链。,由源结点的片缓冲区、结点间的物理通道和接收结点的缓冲区组成。,物理通道由所有虚拟通道分时共享。比如在下例中，四条虚拟通道以片传递为基础分时的共享一条物理通道。,死锁,与,虚拟通道,22,虚拟通道,当物理通道分给某对缓冲区时，这对缓冲区即形成一条虚拟通道。四条虚拟通道共享一条物理通道。,23,某虚拟通道被阻塞时，选择其他虚拟通道传输，打破闭环,。,*只需在部分通道上设置,虚拟通道,（如,V3和V4）。,*,允许部分节点在,无法发送时仍可以接收消息,.,* 类似于,“,绕道,”,C4,C2,C1,C3,C1,C3,V3,C4,V4,C2,2,死锁,的产生与避免,24,死锁的产生与避免,使用通道,C2,后不再用,C3,、,C4,，从而将通道循环链变成,螺旋线,（图,(c),）避免死锁。,增加虚拟通道可能会降低每个请求可用的有效通道,频宽,。,25,5.4 流量控制策略和通信模式,两相邻结点间传送消息时，需具备三个条件：,1.,源缓冲区,已存有该片；,2.,通道,已分配好；,3.,接收缓冲区准备接受,该片。,流量控制策略：,两个,或,多个包,在某个结点为,竞争缓冲区,或,通道,资源而冲突时，须确定（解决冲突）的策略称为,流量控制策略,流量控制策略,的核心是要解决,接收缓冲区,或,输出通道,冲突的仲裁问题，通常有四种办法：,1,后一个包,暂存,(,在缓冲区,),：,2 阻塞,后一个包,3 丢弃,后一个包,：,4,后一个包,绕道：,26,流量控制策略,(1),暂存：,设置两个缓冲区，一个是片缓区，一个包缓冲区。第一个包送入,片缓冲区,以直接送出输出通道，第二个包,暂存在,包缓冲区,先不送出,。,(2) 阻塞：,第一个包送入片缓冲区，用门控拒绝第二个包（阻塞）。图(b),暂时存,27,流量控制策略,(3) 丢弃,：,第一个包送入片缓冲区，第二个包丢弃。图(c)。,(4) 绕道,：,第二个包,绕道（,或,通过其他通道）传输到目的地。图(d),28,通信模式,多计算机网络中有四种通信模式：,单播(unicast),：对应,一对一,的通信，即一个源结点发送消息到一个目的结点。,选播(multicast),：对应,一到多,的通信，即一个源结点发送同一个消息到多个目的结点。,通常在,中间结点上复制,所传送的,包,，然后把,多个,拷贝送到目的结点,。以减少通道的使用数（,通道流量,）,广播(broadcast),：,对应,一到全体,的通信，即一个源结点发送同一个消息到全部结点。是,选播,的特殊情况,会议,(conference),：对应,多到多,的通信。,注：没有多对一的情况,29,通信模式,的主要指标,主要指标是,通道流量,和,通信时延,。,通道流量：,用传输消息所使用的,通道数,来表示。,通信时延：,用包的最长传输时间来表示。,优化寻径以,最小,通道流量,和,最小,通信时延,为目标。但达到最小流量未必能达到最小时延，达到最小时延时也不一定能达到最小流量。,通常，在,存储转发网络,中,时延,是,重要指标,，在,虫孔网络,中,流量,对效率的,影响则更大,。,以网格连接为例来分析一下实现选播、广播或会议通信模式的要求和寻径方法。,30,例题： 如下网格上实现四种,寻径,。,把一个包从结点S送到D1,D2,D3,D4,D5.,图(a)是,5次单播,。流量,13，距离4,图 (b)和(c)给出了,两种选播寻径模式,，流量分别为,7和6，,距离分别是,4和5,。图 （,d)把一个包从结点S,广播,到所有的网格结点 。,流量角度，,图(c)的选播寻径模式较好（,流量少）,时延角度,，图(b)的寻径模式比较好（,时延少,）,31,本 章 小 结,互连网络的定义、功能、描述工具、拓扑结构、性能参数、寻径方法、流控制策略等问题。,重点是：,(1)静态网络，动态网络；(2)寻径方法；(3)消息传递方式。,互连网络可反映网络输入数组和输出数组之间的对应排列关系。常用的互连函数有,交换,、均匀洗牌、,蝶式函数,、反位序函数、,移数函,数等。,互连网络分为,静态互连网络,和,动态互连网络,。,静态网络,是指处理结点间有着固定连接的一类网络，程序执行期间，这种连接保持不变。,静态网络的特性参数有,网络规模,、,结点度,、,距离,、,网络直径,、,结点间线长,、,等分长度,、,对称性,等。,32,动态网络,是用交换开关构成的，可按执行程序的要求动态改变连接状态，通常分为,总线网络,、,多级互连网络、交叉开关网络,三类。,互连网络通信中常用的,消息传递,方式有四种，即,线路交换、存储转发、虚拟直通,和,虫孔方式,。,为了避免产生死锁，可以利用,虚拟通道,，并使用有效的寻径算法。,X-Y寻径法,、,E-立方路由算法,是确定性算法。,多计算机网络中有,单播、选播、广播、会议,四种通信模式，分别对应一对一、一对多、一对全体、多对多四种通信情况,33,作 业,P132： 4 6 8 9 11,课堂练习,P132：,11,34,