高级体系结构-4.ppt

高性能计算机系统的结构，计算机科学和技术系研究生课程，第四章互联与通信，4.1互联网络的作用4.2静态网络4.3动态网络4.4通信问题，4.1互联网络的作用，定义：开关元件由一定的拓扑结构和控制方式构成的网络操作方式：同步通信(SynchronousCommunication )异步通信(AsynchronousCommunication )控制策略：集中控制(Centralizedcontrol )分散控制(Distributedcontrol ) 交换方式：电路交换分组交换wormhole交换网络拓扑：静态网络动态网络(Dynamicnetwork )网络第4章互联和通信4.1互联网的作用4.2静态网络4.2.1静态网络的特征和指标4.2.2典型静态网络4.3动态网络4.4通信问题、4.2静态网络、4.2.1静态网络的特征和指标1 .静态网络如图所示，当节点表示交换机和通信链路时，(1)节点之间的链路是被动的，(2)交换机元件和处理器连接的(3)不直接连接的节点之间的通信需要通过中间节点进行中继。 2 .静态网络的指示节点速度：连接到该节点的边(链路或信道)的数目表示该节点所需的I/O端口号，并且模块化请求节点速度是恒定的。 根据从信道向节点的方向，节点度用节点度=入度输出度中，入度用进入节点的信道数表示，输出度用从节点输出的信道数表示。 距离：两个节点之间的最小边数。 网络直径：网络中任意两个节点之间的距离的最大值。 网络规模：显示网络中的节点数、该网络功能连接部件的数量。 等分宽度：某网络被切成相等的一半时，沿着切口的最小边缘数称为该网络的等分宽度。 节点之间的线长：两个节点之间的线的长度。 对称性：从任何节点来看拓扑都相同，这样的网络的实现和编程很容易。 节点是否是同体的。 过道上有没有缓冲。 4.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。 4 .全链路全链路是带弦环的特殊情况。 所有链路的每一节点与其他节点之间有单个直接链路。 下图的8个节点的全部链路：是28条链路，直径为1，度为7，对称，等分宽度为16。，5 .树，4层的完全二叉树，k层的完全二叉树需要N=2K-1个节点，大多数节点的节点度为3，直径为2(K-1 ) (即从右任一叶节点到左任一叶节点)。 不对称，等分为1。 因为节点度是常数，所以树是可扩展的系统结构。 树的扩展：，循环树，任何结构都可以缓和根节点的瓶颈问题。 6 .星形、星形实际上是双重的树(右图)。 具有n个节点的星型网络有N-1条链路，直径为2，最大节点度为N-1，非对称，均等宽度为1。、7 .网格，具有n个节点的RR网格(其中，2N-2r链接、直径2(r-1 )、节点度4、不对称、等距宽度r。、网格的变形： a.Illiac网格，具有n个节点的rr网格(其中，直径r-1，节点度4，2n个链路、，b .环形网络(2DTorus )，拥有n个节点的RRR网络(其中有2N条链路，直径为2r/2，节点度为4，对称。、 1-立方体，2-立方体，3-立方体，4-立方体，一个n-立方体由N=2n个节点组成，它们分布在n维上，每一维有两个节点。 直径为n，节点度为n，对称。 因为节点度按维线性增加，所以超立方体不是可扩展的结构。 例如，Intel的iPSC/1、iPSC/2、nCUBE、9 .带环立方体，一个带环n-立方体由N=2n个节点环构成，各节点环是具有n个节点的环，所以节点总数为n2n个。 直径通常为2n，节点度为3，对称。 带环3-立方体，10.k元n-，立方体网络，4元3-立方体(不描绘隐藏的节点和连接)，在1个k元n-立方体网络中，节点的数量N=kn，即：中，k k元n-立方体的节点可以用基数k的n比特地址A=a0a1a2.an表示，其中ai表示第I维节点的位置。 传统环网等价于4元2-立方体。，第四章相互连接和通信，4.1相互连接网络的作用4.2静态网络4.3.2多级相互连接网络4.4通信问题，4.3动态网络，特征：网络的开关元件是主动的。 只有网络边界上的开关元件才能连接到处理器。 4.3.1互连函数的排列：将按n个个数确定顺序的配置方法称为一个n排列。 置换：从一个n数组到另一个n数组的变换称为n次置换。 在具有n个输入端和n个输出端的网络中，输入端和输出端的连接关系可用置换表示(输入端和输出端一对一对应)。 一些常用的替换方法可以用以下函数表示：1.恒等函数。 其中Xn-1Xn-2XkX0是PE的地址(通常是二进制)。 n为3的情况下的恒等函数的连接状况为：000，001，010，011，100，101，110，111，000，001，010，101，110，2 .立方体函数(cube0，cube1，cube 例如，在n为3的情况下，3-立方体的各节点地址为，y，z，x，010，011，110，000，111，001，100，101，000，001，010，011，100，101，101 101，110，111， Cube0:0，1，2，3，4，5，6，7，000，001，010，101，111，001，010，011，100，100，100 0，1，2，3，4，5，6，7，000，001，011，100，101，110，111，Cube2:0，1，2，3，4，5，6 、000，001，010，011，001，010，011，100，101，110，101，110，3 .混乱函数，、0，1，1 6，7，0，1，2，3，4，5，6，7，b.k个子洗牌，即最下位k位向左循环一个。、000，001，010，011，100，101，110，111，100，101，110，111，4 .逆乱函数，、0，1，2，3，4，5，5 001，010，011，100，101，110，111，000，001，010，011，100，110，111，5 .蝶形式，0，1，2，3，4，5，6，7，6.PM2I j=0，1，7。六个PM2I函数包括PM2 0:(01234567 )、0、1、2、3、4、5、6、7、PM2-0:(76543210 )、0、1、2、3、4、5、6、7、pm21: (02 ，PM2-1:(6420)(7531 )，PM22:(04)(15)(26)(37 )，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，上的网络可以用4个PM2I函数表示。 PM2 0:(01215 )、PM2-0:(1514130 )、pm 22: (04 ) 15、26、37、48、59、610、711、913、1014、1115、120、131、142、153 4.3.2多级互连网络1 .多级网络的三要素(1)交换机单元：将a个输入a个输出的交换机单元记为aa的交换机单元。 其中，a是2的整数倍。 常见的有22、44、88等。 根据交换单元的功能，22可分为两个功能和四个功能。 下图所示： 0，1，0，1，直送，0，1，0，1，交叉，2 )级间相互连接模式(InterStageConnection ) :均匀洗牌、蝶泳、多重洗牌(例如，四路洗牌把卡平均分成四个(3)控制方式等级控制：每个等级1个控制信号单元控制：每个开关1个控制信号部分等级控制：多个开关共享1个控制信号，2.网：、0、1、2、3、4、5、6、等、0、1、2、3、4、5、6、7、0级、1级、2级、网的特征：开关单元： 22四功能开关ISC :洗牌转换恒等转换控制方式：采用单元控制方式。 当从目的地址码的高位起第I位(0至)为0时，第I级中的22开关的输入端与上输出端连接，否则输入端与下输出端连接。 例如： UIUC的CedarIBM的RP3NYU的Ultracomputer，、0，1，2，3，4，5，6，7第0级，第1级，第2级，非阻塞的实现置换1=(07642 ) (13 ) 、0，1，2，3，4，5，6，7，0级，1级，2级，置换2=(06473)(15)(2)开关f 网是块网：发生冲突时，可以通过几次的方法解决冲突。、0，1，2，3，4，5，6，7，0段，第一段，第二段，网的广播功能： 001