高等计算机系统结构.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,高等计算机系统结构,高等计算机系统结构,第一章 高等计算机的核心技术,并行处理,第二章 加速比性能模型与可扩展性分析,第三章 互连与通信,第四章 划分与调度,第五章 并行存储器系统,第六章,Cache Coherence,第七章,Memory Consistency,第八章 指令级并行处理,第三章 互连与通信,3.1,互连网络的作用,3.2,静态网络,3.3,动态网络,3.4,通信问题,(2)开关元件与处理机相连,流控制（Flow Control）,一个带环n-立方体由N=2n个结点环构成，每个结点环是一个有n个结点的环，所以结点总数为n 2n个。,结点度为3：链路数为18，直径4（比如红色结点），度为3，不对称，等分宽度为2。,第六章 Cache Coherence,阻塞时延Tb：消息传递过程中其他所有可能的时延（主要原因是资源冲突）。,两种确定寻径算法（维序寻径）,当消息的头片到达一个结点A的寻径器后，寻径器根据头片的寻径信息立即做出路由选择：,在开关F、G、H、I和J上发生阻塞,对N个结点的线性阵列，有N-1条链路，直径为N-1（任意两点之间距离的最大值），度为2，不对称，等分宽度为1。,(3)不直接相连结点间的通信需通过中间结点中转。,消息（Message）：是在多计算机系统的处理结点之间传递包含数据和同步消息的信息包。,确定性算法：路径的选择只依赖于它所发送的消息的源结点和目的结点。,互连网络接收源处理结点发来的消息包，并采用一定的寻径算法和流控制技术将它送到目的处理结点。,网络时延与发送消息所经历的结点数成正比,3.1,互连网络的作用,定义：,由开关元件按一定拓扑结构和控制方式构成的网络以实现计算机系统内部多个处理机或多个功能部件间的相互连接。,操作方式：,同步通信（,Synchronous Communication,),异步通信,(,Asynchronous Communication,),控制策略：,集中控制,(,Centralized control,),分布控制,(,Distributed control,),交换方式：,电路交换,(,Circuit switching,),分组交换,(,Packet switching,),Wormhole,交换,(,Wormhole switching,),网络拓扑结构：,静态网络,(,Static network,),动态网络,(,Dynamic network,),第三章 互连与通信,3.1,互连网络的作用,3.2,静态网络,3.2.1,静态网络的特点与指标,3.2.2,典型的静态网络,3.3,动态网络,3.4,通信问题,3.2,静态网络,3.2.1,静态网络的特点与指标,1.,静态网络的特点,静态网络,由点,点直接相连而成，这种连结方式在程序执行过程中不会改变,。,如果用图来表示，结点代表开关，边代表通信链路，则,(1),结点间的链路无源，不能重构,(2),开关元件与处理机相连,(3),不直接相连结点间的通信需通过中间结点中转。,2.,静态网络的指标,结点度,：与结点相连接的边（链路或通道）数，表示节点所需要的,I/O,端口数，模块化要求结点度保持恒定。根据通道到结点的方向，结点度可以进一步表示为：,结点度,=,入度,+,出度,其中入度是进入结点的通道数，出度是从结点出来的通道数。,距离,：与两个结点之间相连的最少边数。,网络直径,：网络中任意两个结点间距离的最大值。,网络规模,：网络中结点数，表示该网络功能连结部件的多少。,等分宽度,：某一网络被切成相等的两半时，沿切口的最小边数称为该网络的等分宽度。,结点间的线长,：两个结点间的线的长度。,对称性,：从任何结点看，拓扑结构都一样，这种网络实现和编程都很容易。,结点是否同构。,通道是否有缓冲。,3.2.2,典型的静态网络,1.,线性阵列,对,N,个结点的线性阵列，有,N-1,条链路，直径为,N-1,（任意两点之间距离的最大值），度为,2,，不对称，等分宽度为,1,。,N,很大时，通信效率很低。,线性阵列与总线的区别：,线性阵列,：允许不同的源结点和目的结点对并发使用系统的不同部分。,总线,：通过切换与其相连的许多结点来实现时分特性，同一时刻只有一对结点在传送数据。,2.,环,对,N,个结点的环，考虑相邻结点数据传送方向：,双向环,：链路数为,N,，直径,N/2,，度为,2,，对称，等分宽度为,2,。比如,KSR-1,（,1990,）。,单向环,：链路数为,N,，直径,N-1,，度为,2,，对称，等分宽度为,2,。,3.,带弦环,对上图中,12,个结点的带弦,双向,环，,结点度为,3,：链路数为,18,，直径,4,（比如红色结点），度为,3,，不对称，等分宽度为,2,。,结点度为,4,：链路数为,24,，直径,3,（比如红色结点），度为,4,，对称，等分宽度为,8,。,度为,3,的带弦环,度为,4,的带弦环,4.,全链接,全链接是带弦环的一种特殊情形。全链接中的每个结点和其他结点之间都有单一的直接链路。如下图中,8,个结点的全链接：,有,28,条链路，直径为,1,，度为,7,，对称，等分宽度为,16,。,5.,树形,4,层的二叉树,一棵,K,层完全二叉树应有,N=2,K,-1,个结点，大多数结点的结点度为,3,，直径为,2,（,K-1,）,（即右边任意一个叶子结点到左边任意一个叶子结点）。不对称，等分度为,1,。,由于结点度为常数，所以树是一种可扩展的系统结构。,树形的扩展：,带环树,二叉胖树,这两种结构都可以缓解根结点的瓶颈问题。,6.,星形,星形实际上是一种二层树（如右图）。有,N,个结点的星形网络，有,N-1,条链路，直径为,2,，最大结点度为,N-1,，非对称，等分宽度为,1,。,7.,网格,有,N,个结点的,r,r,网格（其中,),，有,2N-2r,条链路，直径为,2,（,r-1),，,结点度为,4,，非对称，等分宽度为,r,。,网格的变形：,a.Illiac,网,有,N,个结点的,r,r,网格（其中,),，有,2N,条链路，直径为,r-1,，,结点度为,4,。,b.,环形网（,2DTorus,）,有,N,个结点的,r,r,网（其中,),，有,2N,条链路，直径为,2,r/2,，,结点度为,4,，对称。,c.,搏动式阵列（,Systolic Array,）,8.,超立方体,0-,立方体,1-,立方体,2-,立方体,3-,立方体,4-,立方体,一个,n,-,立方体由,N=2,n,个结点构成，它们分布在,n,维上，每维有两个结点。直径为,n,，,结点度为,n,，对称。由于结点度随维数线性增加，所以超立方体不是一种可扩展结构。,例子：,Intel,的,iPSC/1,、,iPSC/2,、,nCUBE,9.,带环立方体,一个带环,n,-,立方体由,N=2,n,个结点环构成，每个结点环是一个有,n,个结点的环，所以结点总数为,n 2,n,个。直径通常为,2n,，结点度为,3,，对称。,带环,3-,立方体,元,n-,立方体网络,4,元,3-,立方体,（隐藏的结点与连接没有画出,),在一个,k,元,n,-,立方体网络中，结点的数目,N=k,n,，即：,其中，,k,称为基数（,radix,），,n,称为维数（,dimension,）。,k,元,n,-,立方体的结点可以用基数为,k,的,n,位地址,A=a,0,a,1,a,2,.,a,n,来表示，其中,a,i,代表第,i,维结点的位置。,传统的环网等价于,4,元,2,-,立方体。,第三章 互连与通信,3.1,互连网络的作用,3.2,静态网络,3.3,动态网络,3.3.1,互连函数,3.3.2,多级互联网络,3.4,通信问题,3.3,动态网络,特点：,网络的开关元件有源，链路可通过设置这些开关的状态来重构。,只有在网络边界上的开关元件才能与处理机相连。,3.3.1,互连函数,排列：,N,个数的每一种有确定次序的放置方法叫做一个,N,排列。,置换：,把一个,N,排列变成另一个,N,排列的变换叫做,N,阶置换。,在有,N,个输入端和,N,个输出端的网络中，输入端和输出端的连接关系可以用置换来表示（输入端与输出端一一对应）。,一些常见的置换方式可以用下面的函数表示：,1.,恒等函数,其中，,X,n-1,X,n-2,X,k,X,0,是,PE,的地址（通常为二进制）。,n,为,3,时的恒等函数的连接情形如下：,000,001,010,011,100,101,110,111,000,001,010,011,100,101,110,111,2.,方体函数（,cube,0,，,cube,1,，,，,cube,n-1,),方体函数是由,n,个互连函数组成，其中,0,kn,。,比如，,n,为,3,时，,3,-,立方体各结点地址如下：,Y,Z,X,010,011,110,000,111,001,100,101,000,001,010,011,100,101,110,111,000,001,010,011,100,101,110,111,Cube,0,:,0,1,2,3,4,5,6,7,双向环：链路数为N，直径N/2，度为2，对称，等分宽度为2。,虚拟通道：使实现自适应寻径更经济和更灵活。,阻塞时延Tb：消息传递过程中其他所有可能的时延（主要原因是资源冲突）。,均匀洗牌（Shuffle-Exchange),寻径按照从维1到维4的顺序进行。,其中，Lc是为消息建立物理通路所传递的控制信息的长度。,电路交换(Circuit switching),东南：(0,7)(4,2)西北：(6,3)(1,5),由UC Berkeley开发。,全链接是带弦环的一种特殊情形。,有28条链路，直径为1，度为7，对称，等分宽度为16。,（b）中的选播方式对存储转发比较好，,（a）没有虚拟通道的原型网络,双向环：链路数为N，直径N/2，度为2，对称，等分宽度为2。,d=dn-1 dn-2 d1 d0,广播模式（Broadcast）：一个源结点全体结点。,1=（0 7 6 4 2）（1 3）（5）,000,001,010,011,100,101,110,111,000,001,010,011,100,101,110,111,Cube,1,:,0,1,2,3,4,5,6,7,000,001,010,011,100,101,110,111,000,001,010,011,100,101,110,111,Cube,2,:,0,1,2,3,4,5,6,7,000,001,010,011,100,101,110,111,000,001,010,011,100,101,110,111,3.,洗牌函数,0,1,2,3,4,5,6,7,洗牌函数的变形：,a.,均匀洗牌（,Shuffle-Exchange),是,洗牌函数,与,Cube,0,函数的组合。,0,1,2,3,4,5,6,7,：,Cube,0,：洗牌,b.,第,k,个子洗牌,即最低,k,位循环左移一位。,c.,第,k,个超洗牌,即最高,k-1,位循环左移一位。,000,001,010,011,100,101,110,111,000,001,010,011,100,101,110,111,4.,逆洗牌函数,0,1,2,3,4,5,6,7,000,001,010,011,100,101,110,111,000,001,010,011,100,101,110,111,5.,蝶式,0,1,2,3,4,5,6,7,6.PM2I,函数（加减,2,i,）,共有,2n,个互连函数，对,N,个结点的网络为,例,1,：,N=8,（,8,个结点），则,n=log,2,8=3,，所以：,i=0,，,1,，,2,；,j=0,，,1,，,，,7,。,6,个,PM2I,函数如下：,PM2,+0,:(0 1 2 3 4 5 6 7,）,0,1,2,3,4,5,6,7,PM2,-0,:(7 6 5 4 3 2 1 0,）,0,1,2,3,4,5,6,7,PM2,+1,:(0 2 4 6,）（,1 3 5 7,）,0,1,2,3,4,5,6,7,PM2,-1,:(6 4 2 0,）（,7 5 3 1,）,0,1,2,3,4,5,6,7,PM2,2,:(0 4,）（,1 5,）（,2 6,）（,3 7,）,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,例,2,：,8,9,10,11,12,13,14,15,上面的网络可以用四个,PM2I,函数表示。,PM2,+,0,:,(0 1 2 15),PM2,-,0,:,(15 14 13 0),PM2,2,:,(0 4,）（,1 5,）（,2 6,）（,3 7,）,(4 8,）（,5 9,）（,6 10,）（,7 11,）,(8 12,）（,9 13,）（,10 14,）（,11 15,）,(12 0,）（,13 1,）（,14 2,）（,15 3,）,3.3.2,多级互连网络,1.,多级网络的三要素,（,1,）开关单元：,a,个输入,a,个输出的开关单元记做,a,a,的开关单元，其中，,a,是,2,的整数倍,。常见的有,2,2,、,4,4,、,8,8,等。,根据开关单元功能的多少，,2,2,又可以分为,两功能,和,四功能,开关。如下图所示：,0,1,0,1,直送,0,1,0,1,交叉,0,1,0,1,上播,0,1,0,1,下播,（,2,）级间互连模式（,I,nter,S,tage,C,onnection,）：,均匀洗牌,、,蝶式,、,多路洗牌,（比如四路洗牌即是把牌平均分成,4,份，然后,4,堆分别进行均匀洗牌）、,纵横开关,（,Cross Switch),及,立方体连结,等。,（,3,）控制方式,级控制：,每级只有一个控制信号,单元控制：,每个开关一个控制信号,部分级控制：,几个开关合用一个控制信号,2.,网,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,第,0,级,第,1,级,第,2,级,网的特点：,开关单元,：,2,2,四功能开关,ISC,：,洗牌变换,+,恒等变换,控制方式,：采用单元控制方式。当目的地址编码从高位开始的第,i,位（从,0,开始）为,0,时，第,i,级的,2,2,开关的输入端与上输出端连接，否则输入端与下输出端连接。,例子：,UIUC,的,Cedar,IBM,的,RP3,NYU,的,Ultracomputer,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,第,0,级,第,1,级,第,2,级,无阻塞的实现置换,1,=,（,0 7 6 4 2,）（,1 3,）（,5,）,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,第,0,级,第,1,级,第,2,级,置换,2,=,（,0 6 4 7 3,）（,1 5,）（,2,）,在开关,F,、,G,、,H,、,I,和,J,上发生阻塞,F,G,H,J,I,网的特点,(2),：,并不是所有的置换在,网中一次通过便可以实现。,网是阻塞网络：出现冲突时，可以采用几次通过的方法来解决冲突。,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,第,0,级,第,1,级,第,2,级,网的广播功能：,001,8,个输出端,0,1,第,1,级,4,4,开关构成的,网：多路洗牌,如,16,输入,4,路洗牌：网路级数为,log,4,16=2,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,第,0,级,网的特点,(3),：,当采用,k,k,开关元件时，则可以定义,k,路洗牌函数来构造更大的级数为,log,k,n,的,网络。,3.,蝶式网络（,Butterfly switch network,）,蝶式网络的开关不允许广播功能，它实际上是,Omega,网的一个子集。,两级,64,64,的蝶式网络如下图所示：它采用,16,个,8,8,交叉开关构成，两级间采用,8,路洗牌连接。,8,8,8,8,8,8,0,.,.,.,7,8,8,8,8,8,8,第,1,级,第,0,级,8,.,.,.,15,56,.,.,.,63,.,.,.,.,.,.,.,.,.,0,7,8,15,56,63,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,两级,64,64,的蝶式网络,4.,其他连接方式,总线,交叉开关,第三章 互连与通信,3.1,互连网络的作用,3.2,静态网络,3.3,动态网络,3.4,通信问题,3.4.1,基本术语与性能指标,3.4.2,寻径算法,3.4.3,虚拟通道与死锁,3.4.4,包冲突的解决,3.4.5,维序寻径,3.4.6,通信模式,3.4,通信问题,基本术语与性能指标,1.,消息、包和片,消息（,Message,）,：是在多计算机系统的处理结点之间传递包含数据和同步消息的信息包。它是一种逻辑单位，可由任意数量的包构成。,包（,Packet,）,：包的长度随协议不同而不同，它是信息传送的最小单位，,64-512,位。,片（,Flit,）,：片的长度固定，一般为,8,位。,它们的相互关系如下图：,包,消息,包,片,据,片,头片,尾片,顺序号,数,b,b,b,b,b,b,b,b,2.,互连网络,互连网络用来在多计算机系统的处理结点之间传递消息。互连网络的描述：,拓扑（,Topology,）,寻径算法（,Routing,）,流控制（,Flow Control,）,互连网络性能的两个重要指标：,传输时延（,Transmission Latency,）,吞吐量（,Throughput,）,3.,传输时延与吞吐量,一个消息的传输时延,：从它在源结点进行发送初始化到它在目的结点完整的被接收所耗费的时间。,一个网络的传输时延,：在一定条件下发送消息的平均时延。,网络的吞吐量,：单位时间内网络所能传输的消息数目或长度。,4.,传输时延的公式,其中，,T,s,称为,建立时延,，,T,n,称为,网络时延,，,T,b,称为,阻塞时延,。,它们具体定义如下：,建立时延,T,s,：一个消息在源结点和目的结点上装配和分解、从存储器拷贝到通信缓冲区以及正确性验证等所耗费的时间。它和机器本身的硬件、软件技术有关。,其中：,T,ss,称为,源结点时延,：从发送进程开始消息发送初始化到消息的头部进入网络所经历的时间。,T,sd,称为,目的结点时延,：从消息的尾部到达目的结点到消息完全被接收进程接收所经历的时间。,网络时延,T,n,：消息头部从源结点进入网络到消息的尾部到达目的结点的时间间隔。,其中：,T,p,D,称为,结点时延,：其中,T,p,是消息在它所经过的路径上的每个中间结点上的平均时延，,D,为中间结点或源结点与目的结点之间的距离。,L/B,称为,线路时延,：其中,L,为消息长度，,B,为结点之间的通道带宽。,阻塞时延,T,b,：消息传递过程中其他所有可能的时延（主要原因是资源冲突）。,5.,网络的拓扑结构,第一代并行计算机,：,HyperCube,第二代并行计算机,：,nMesh,6.,网络的寻径算法,决定发送一个消息到其目的地所经过的路径。,可以分为：,最短路径算法,非最短路径算法,或者：,确定性算法,：路径的选择只依赖于它所发送的消息的源结点和目的结点。,可适应算法,：消息从结点,A,到结点,B,可以由几条不同的路径。,7.,网络的流控制,当一个消息在网络中沿着某条路径传送时，互连网络如何来为它分配通道和缓冲器。,寻径算法,我们介绍四种寻径方式：,存储转发（,Store-and-Forward,）,虚拟直通（,Virtual cut through,）,线路交换（,Circuit Switching,）,Wormhole,交换（,Wormhole Switching,),1.,存储转发,当一个消息到达中间结点,A,时，,A,把整个消息放入其通信缓冲器中，然后在寻径算法的控制下选择下一个相邻结点,B,，当从,A,到,B,的通道空闲并且,B,的通信缓冲器可用时，把消息从,A,发向,B,。,缺点,：,每个结点必须对整个消息进行缓冲，缓冲器较大。,网络时延与发送消息所经历的结点数成正比,2.,虚拟直通,中间结点没有必要等到整个消息全部被缓冲后再作出路由选择，只要消息的目的信息域可用后，就可以作出路由选择。,其中，,L,h,为消息头部开始到其目的信息域的长度，显然有,L L,h,，所以,D,的影响比较小。,而当通向下一结点的通道忙或结点的缓冲器非空闲时，必须把整个消息缓冲起来，这时和存储转发一样。,3.,线路开关,在传递一个消息之前，就为它建立一条从源结点到目的结点的物理通道。在传递的全部过程中，线路的每一段都被占用，当消息的尾部经过网络后，整条物理链路才被废弃。,其中，,L,c,是为消息建立物理通路所传递的控制信息的长度。当,L L,h,时，,D,的影响较小。,缺点,：,物理通道非共享,传输过程中物理通道一直被占用,Dally,于,1986,年提出。,首先把一个消息分成许多片，消息的,头片,包含了这个消息的所有寻径信息。,尾片,是一个其最后包含了消息结束符的片。中间的片均为,数据片,。,片是最小信息单位。每个结点上只需要缓冲一个片就能满足要求。,用一个头片直接开辟一条从输入链路到输出链路的路径的方法来进行操作。每个消息中的片以流水的方式在网络中向前“蠕动”。每个片相当于,Worm,的一个节，“蠕动”以节为单位顺序的向前爬行。,当消息的头片到达一个结点,A,的,寻径器,后，寻径器根据头片的寻径信息立即做出路由选择：,（,1,）,如果所选择的通道空闲而且所选择的结点,B,的通信缓冲器可用，那么这个头片就不必等待，直接通过结点,A,传向下一个结点,B,；随后的其它片跟着相应的向前“蠕动”一步。当消息的尾片向前“蠕动”一步后，它刚才所占用的结点就被放弃了。,（,2,）,如果所选择的通道非空闲或者所选择的结点的通信缓冲器非可用，那么这个头片就必须在此结点的通信缓冲器中等待，直到上述两者都可用为止；其它片也在原来的结点上等待。此时，被阻塞的消息不从网络中移去，片不放弃它所占有的结点和通道。这是,Wormhole,技术和其它流控制技术都不同的地方。,优点,：,（,1,）每个结点的缓冲器的需求量小,，易于用,VLSI,实现。,（,2,）较低的网络传输延迟,。所有的片以流水方式向前传送，,时间并行性,。而在存储转发中，消息是整个的从一个结点“跳”向另一个结点，通道的使用时串行的。所以它的传输延迟基本上正比于消息在网络中传输的距离。,Wormhole,与线路开关的网络传输延迟正比于消息包的长度，传输距离对它的影响很小（消息包较长时的情况）。,（,3,）通道共享性好、利用率高。,对通道的预约和释放是结合在一起的一个完整的过程：占有一段新的通道后将立即放弃用过的一段旧通道。,（,4,）易于实现,Multicast,和,Broadcast,。,允许寻径器复制消息包的片并把它们从多个输出通道输出。,Wormhole,方式中，同一个包中所有的片象不可分离的同伴一样以流水方式顺序的传送。包可看作是一列火车，由火车头（头片）和被牵引的车厢（数据片）组成。,5.,几种寻径技术的时空图,S,时间,I1,I2,D,L/B,D,存储转发（,Store-and-forward,）寻径技术,S,时间,I1,I2,D,电路开关寻径技术,S,时间,I1,I2,D,L/B,D,Wormhole,寻径技术,包头,数据,死锁和虚拟通道,1.,虚拟通道,特点：,是两个结点间的逻辑链。,由源结点的片缓冲区、结点间的物理通道和接收结点的缓冲区组成。,物理通道由所有虚拟通道分时共享。,比如,在下例中，四条虚拟通道以片传递为基础分时的共享一条物理通道。,物理通道,源结点中的片缓冲区,目的结点中的片缓冲区,四条虚拟通道以片传递为基础分时共享一条物理通道,2.,死锁的产生,缓冲区产生死锁：,D,D,D,D,D,D,包缓冲区,D,D,D,D,D,D,包缓冲区,D,D,D,D,D,D,包缓冲区,D,D,D,D,D,D,包缓冲区,结点,A,结点,D,结点,B,结点,C,采用存储转发，四个包占用了四个结点的四个缓冲,区，将导致循环等待。,通信产生死锁：,结点,A,结点,D,结点,B,结点,C,寻径器,A,寻径器,B,寻径器,C,寻径器,D,消息,4,消息,1,消息,3,消息,2,m4,m3,m1,m2,片缓冲区,采用,Wormhole,，四个结点之间出现通道死锁，,4,个,消息的四个片同时占用了,4,个通道。,2.,死锁的避免,C1,结点表示通道，带方向的箭头表示通道之间的,依赖关系。,A,B,C3,D,C,C2,C4,通道死锁,C4,C1,C3,C2,包含循环的通道相关图,C1,利用虚拟通道将通道相关图中的环路变成螺旋线,来比避免死锁。,A,B,C3,D,C,C4,增加两条虚拟通道,V3,V4,C4,C1,C3,C2,利用虚拟通道后的通道相关图,V4,V3,V3,V4,包冲突的解决,1.,问题的提出,两个相邻结点间要传送包，必须具备下列三个条件：,（,1,）,源缓冲区已存该包,（,2,）,通道已分配好,（,3,）,接收缓冲区准备接收,当两个包到达同一个结点时，可能请求同一个接收缓冲区或用同一个输出通道：,（,1,）,把通道分配给哪个包,？,（,2,）,没有分配到通道的包怎么办,？,2.,四种解决方法,（,1,）用缓冲实现虚拟直通寻径,包缓冲区,包,2,包,1,输出通道,片缓冲区,将通道分配给包,1,，缓冲包,2,好处,：不会浪费已经分配的资源,缺点,：需要一个能存放整个包的缓冲区，包缓冲区不可能做在寻径芯片上，要用存储器作为缓冲区，会有较大的存储延迟。,（,2,）阻塞流控制（,Wormhole,寻径）,包,2,包,1,输出通道,片缓冲区,第二个包被阻塞不再前进，但没有被扬弃,控制,门,（,3,）扬弃并重发,包,2,包,1,输出通道,片缓冲区,第二个包被扬弃,（,3,）阻塞后绕道,包,2,包,1,输出通道,片缓冲区,第二个包绕道：被转发到其它的寻径器,绕道通道,维序寻径,1.,寻径方式,确定寻径（,deterministic routing,）,：,通信路径完全由源和目的地址确定。（换句话说，寻找的路径是预先唯一确定的，与网络的状况无关）。,自适应寻径（,adaptive routing,）,：,与网络的状况有关，可能会有几条路径。（需要消除死锁的算法）。,2.,两种确定寻径算法（维序寻径）,（,1,）二维网格中的,X-Y,寻径,：,首先沿着,X,维方向确定路径，然后沿着,Y,维方向选择路径。,假定从任意源结点,s=(X1 Y1),到任意目的结点,d=(X2 Y2),。,寻径从,s,开始，首先沿着,X,方向前进一直到,d,所在的第,X2,列为止，然后沿,Y,方向前进直到,d,。,四种模式,：,东,北,，,东,南,，,西,北,，,西,南,。,下面是一个例子：,0,7,1,7,2,7,3,7,4,7,4,6,7,6,1,5,4,5,7,5,1,4,2,4,3,4,4,4,5,4,7,4,1,3,2,3,3,3,4,3,5,3,6,3,7,3,2,2,4,2,7,2,2,1,3,1,4,1,5,1,6,1,7,1,2,0,Y,X,东,北：,(2,1),(7,6),西,南：,(5,4),(2,0),东,南：,(0,7),(4,2),西,北：,(6,3),(1,5),特点,：,总是先沿,X,维方向寻径，然后再沿,Y,维方向寻径，寻径不会出现死锁或循环等待现象。,可以扩充到,n,维网络，如,X-Y-Z,等等。,可用于存储转发或,Wormhole,寻径网络，在源和目的结点之间形成一条距离最短的路径。,（,2,）立方体网络中的,E,立方体寻径,：,假设有一个,N=2,n,个结点的,n,方体。每个结点的二进制编码为：,b=b,n-1,b,n-2,b,1,b,0,s=s,n-1,s,n-2,s,1,s,0,d=d,n-1,d,n-2,d,1,d,0,如何确定一条从,s,到,d,的步数最小的路径,？,将,n,维表示成,i=1,2,n,，其中第,i,维对应结点地址中的第,i-1,位。设,v=v,n-1,v,n-2,v,1,v,0,是路径中的任一结点。,方法,：,（,1,）,计算方向位。,使,i=1,v=s,，开始下面的步骤。,（,2,）,如果,r,i,=1,，则从当前结点,v,寻径到下一结点 ；,如果,r,i,=0,，则跳过这一步。,（,3,）,i=i+1,，如果,i,n,，则转第,（,2,）,步，否则退出。,如下面的例子：,0110,0010,0000,0100,0111,0001,0011,0101,1110,1010,1000,1100,1111,1001,1011,1101,4,维立方体网络,n=4,，,s=0110,，,d=1101,寻径,：,（,1,）,计算方向位。,i=1,，,v=s,0,1,1,r,4,1,1,0,r,3,1,0,1,r,2,0,1,1,r,1,（,R=,）,（,2,）,r,1,=1,，,（,3,）,r,2,=1,，,（,4,）,r,3,=0,，,（,5,）,r,4,=1,，,路径为：,0110,011101011101,0110,0010,0000,0100,0111,0001,0011,0101,1110,1010,1000,1100,1111,1001,1011,1101,特点,：,寻径按照从维,1,到维,4,的顺序进行。,如果,s,和,d,的第,i,位相同，则沿维,i,的方向不需要寻径，否则从当前结点沿着这一维方向走向下一结点（立方体中，每维包括两个结点）。重复这一过程直到到达目的结点。,3.,自适应寻径,目的：,避免死锁,虚拟通道,：使实现自适应寻径更经济和更灵活。,方法,：网格网络中，同一维的所有连接都使用虚拟通道。,如下图所示：,02,12,22,01,11,21,00,10,20,（,a,）没有虚拟通道的原型网络,02,12,22,01,11,21,00,10,20,（,b,）,Y,维方向有两对虚拟通道,02,12,22,01,11,21,00,10,20,（,c,）向西方向传递消息,（,d,）向东方向传递消息,02,12,22,01,11,21,00,10,20,通信模式,1.,通信模式,单播模式（,Unicast,）：,一个源结点,一个目的结点。,选播模式（,Multicast,）：,一个源结点,多个目的结点。（多播、组播）,广播模式（,Broadcast,）：,一个源结点,全体结点。,会议模式（,Conference,）：,多个源结点,多个目的结点。,2.,寻径效率,通信流量（,Channel traffic,）：,用传输有关消息所使用的通道数来表示。,通信时延（,Communication latency,）：,用包的最长传输时间来表示。,在,Wormhole,寻径方式下，网络流量这个参数比较重要。,在存储转发网络中，时延是最重要的问题。,例,：,网格连接计算机中的选播和广播。,3,4,网格上实现选播寻径。,D2,D1,S,（,a,）,5,次单播，流量等于,13,，距离等于,4,D3,D4,D5,在一个中间结点上复制所传送的包，然后把该包的多个拷贝送到目的结点，这样可以减少通道流量。,D2,D1,S,（,b,）一种流量等于,7,，距离等于,4,的选播,D3,D4,D5,（,b,）,中的选播方式对存储转发比较好，,而,（,c,）,中的选播方式对,Wormhole,寻径较好。,D2,D1,S,（,c,）流量等于,6,，距离等于,5,的选播,D3,D4,D5,结点中的数字表示树的层次号，该树称为广播树。,3,2,3,2,1,2,1,S,1,（,d,）通过树结构广播所有结点,4,3,2,3.Active Message,由,UC Berkeley,开发。,背景,：互连网络的硬件开销已经相当小了，通信和计算机不能相互重叠，消息发生和接收原语带来过大的系统软件开销。,互连网络接收源处理结点发来的消息包，并采用一定的寻径算法和流控制技术将它送到目的处理结点。消息包到达后，用一个中断信号去通知目的处理结点。此时目的处理结点会调用相应的中断处理函数来处理到达的消息包。,这是一个完全异步的过程。,传统的通信机制之所以会有比较大的软件开销，其实质上的原因就是过多的采用了与上述异步过程不相匹配的同步协议。,Active Message,：消息发送方来指明消息处理函数的地址，当消息到达时，这一函数就自动的被调用。,简单得几乎没有任何协议的异步通信机制。,好处,：,不需要任何缓冲,实现简单,消息格式,：,消息头,源地址,指向消息处理函数的指针,参数,数据,Active Message,的消息格式,4.,通信系统的现状,高速网络发展迅速：,Ethernet,：,10M,100M 1G 10G,ATM,：,Myrinet,：,InfinBand:10G,峰值带宽增长幅度大,通信协议基本不变,