第6章 互连网络.ppt

第6章 互连网络 6.1 互连网络的基本概念 6.2 静态互连网络 6.3 动态互连网络 6.4 消息传送与控制 6.1 互连网络的基本概念 6.1.1 互连网络的功能与特征 6.1.2 互连函数 6.1.1 互连网络的功能与特征 6.1.2 互连函数 6.2 静态互连网络 6.2.1 静态互连网络结构 6.2.2 静态互连网络特性 6.2.1 静态互连网络结构 6.2.2 静态互连网络特性 6.3 动态互连网络 6.3.1 总线互连方式 6.3.2 交叉开关互连方式 6.3.3 多级网络互连方式 6.3.1 总线互连方式 6.3.2 交叉开关互连方式 6.3.3 多级网络互连方式 6.4 消息传送与控制 6.4.1 消息寻径方式 6.4.2 虚拟通道与死锁 6.4.3 流控制策略 6.4.1 消息寻径方式 6.4.2 虚拟通道与死锁 6.4.3 流控制策略 （2）存储转发寻径（Store and forward） 这里要求每个结点有一个包缓冲区，包经多次转发后到达目标结点。当一个包到达中间结点时首先存入，在下一结点接通后发往下一结点，其示意如图6.37所示。 存储转发网络的时延与源/目标结点之间的距离成正比。传输时延表示如下： T=(L/B)×D+L/B=(D+1)×L/B 存储转发寻径方式的不足是当包缓冲区过大时不利于VLSI的实现，网络距离很大时转发时延增大。 图6.37 存储转发寻径方式 （3）虚拟直通（Virtual cut through） 虚拟直通是不必等到整个消息（包）全部接收完成后再作下一步的路由选择，只要接收到头部导径信息之后即可进行下一结点的判断与连接。传输时延表示如下： T=(Lh/B)×D+L/B=(Lh×D+L)/B 其中Lh是头部导径信息的长度。一般来说LLh，所以公式可近似为T≈L/B。也就是说，时延与结点数近似于无关。 （4）虫孔寻径（Wormhole） 也称为虫蚀寻径，是把包分成更小的数据片，称为Flit。而在每个结点中设有硬件寻径器及片缓冲区，Flit以流水线的方式顺序，不间断地从源结点传送到目标结点，象一条小虫在小孔中蠕动，因此称为虫孔寻径。由于只有头部Flit知道包传送到何处，因此允许不同包交叉传送，但不允许不同包中的Flit混在一起。 图6.38所示是小孔寻径示意图，其中L表示包长，Lf表示数据片Flit长。B是通道带宽，D是结点距离。这样，传输时延如下： T=Lf/B×D+L/B=(Lf×D+L)/B 显然，当LLf时，T≈L/B，与D无关。 第一台采用虫孔寻径方式的计算机是Ametek 2010（二维互连网络）。以后Intel的Paragon多级系统(二维网络)、MIT的J多级系统(三维网络)以及我国的曙光1000采用的都是虫孔寻径方式。 图6.38 虫孔寻径方式 1.虚拟通道 虚拟通道是指两个结点之间的逻辑连链，由源结点的片缓冲区、结点间的物理通道及目标结点的片缓冲区组成。如图6.39所示，4条虚拟通道共享一条物理通道，且源/目结点各有4个片缓冲区。 在使用时，只有物理通道分配给这一对缓冲区时，源/目缓冲区之间才能传送数据。物理通道由所有虚拟通道分时共享。 图6.39 虚拟通道的组成示意图 9.带环立方体网络结构 是把立方体中每一个结点用一个包含多个结点的环代替。如图6.16 所示，是把3-立方体中的顶角结点换成包含3个结点的环，而构成的带环立方体结构，简称3-CCC(Cube Connected Cycles)。若要组成带环k-立方体，只需将k-立方体的每一个顶角结点用k个结点组成的环代替，这样就构成一个有N=k×2k个结点的带环k-立方体。 图6.16 带环3-立方体 在构成带环立方体网络时，环中的结点数k一般与立方体的维数相等。 10.k元n-立方体网络结构 在k元n-立方体网络中，k表示基数，即每一方向上的结点数，n表示立方体的维数。这样，网络中的结点数N=kn(n=logkN)。 图6.17是一种4元3-立方体的网络结构(隐藏部分的结点没有画出)，每个方向上有一条双向通信链路。实际上，环型、网格型、环网型、二元n维立方体(超立方体)以及Omega网络都是k元n-立方体（k-ary n-cube network）系列的拓扑同构体。 按照习惯，低维k元n-立方体称为环网，高维二元n-立方体称为超立方体。 图6.17 4元3-立方体网络结构 各种阵列机或大规模并行处理机系统中的静态互