互连网络拓扑结构概述

1、第八章互连网络拓扑结构概述1.互连网络的基本概念本章主要介绍高性能并行计算机系统互连网络的基本知识，这里包括了相关 的背景、作用，互连网络的特性与指标，互连网络分类的依据与方法，互连网络 的参数特性与表示方法等。1-1、互连网络的背景与作用从目前高性能计算机系统各组成部分的性能来看，由于 VLSI技术的发展， 器件的速度和集成度越来越高，价格越来越低，而连接各个结点形成高性能计算 机系统的互连网络速度却越来越跟不上结点的速度，互连网络已成为制约高性能 并行计算机系统性能发挥的瓶颈。互连网络的应用十分广泛，从 VLSI电路的内部总线到底板总线，计算机机 中的处理器/存储器互连，系统局域网（SAN

2、）,电话交换网，用于ATM交换的内 部网络，局域网，城域网，工业应用的网络，广域网直至今天的并行计算机系统 互连，包括多处理机、多计算机系统和网络工作站。 互连网络如此广泛的应用不 仅推动了相应领域的进步，也奠定了互连网络在高性能并行计算机系统中的关键 技术地位，并保证了它的不断发展。高性能计算机系统互连网络的研究始于多计算机系统的互连，也是研究其它 高性能计算机系统的基础。标准的缺乏以及对高性能网络的追求极大地推动了多 计算机系统互连网络技术的发展，这些新技术反过来又被应用到分布共享主存的 多处理机系统中，用以提高多处理机系统的可扩展性。这些技术包括应用局域网 形成一类新型的高性能计算机系统

3、：网络工作站。在商用并行计算机系统中，高 效互连网络推动着高性能计算机系统的发展：如Intel公司的ASIC Red, IBM的“Blue Pacific，以及SGI的“Blue Mountain”，计划等，这些TF级的超级计算 机系统都是经极高性能的互连网络将数以千计的处理器连接成的系统，用以支持挑战性科学计算对高性能计算能力的需求。目前高性能计算机系统各类互连网络 的研究已很深入，所追求的目标是高带宽、低延迟。1-2、互连网络的定义互连网络是由开关元件按照一定的拓补结构和控制方式构成的网络，用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接。互连系统是构成高性能计算机系统和决定系

4、统通信性能的关键部分，其主要功能是实现系统中大量结点之间的消息传送，因而其通信带宽和延迟将直接影响 高性能计算机系统计算能力和效率的发挥。1-3、互连网络的特性与常用指标互连网络的特性关系到并行计算系统能否行之有效地工作，当我们考虑某一 互连网络的特性时主要从一下几个因素进行比较：1）构造这种网络的复杂程度和代价；2）网络直径的大小及由此带来的延迟，延迟的均匀或不均匀性；3）网络的对分带宽，即用一截面将网络划分成对等的两半时穿过该截面的最大传输率；4）网络可伸缩性好不好，物理实现时组装是否方便；5）网络中从一节点至另一节点是否存在多个通路的可选择性，可否会造成死锁，解决死锁的算法对网络交通的影

5、响如何；6）网络负载的均衡率，这是衡量网络在运行过程中通过每一个链路的信息量是否均衡的标志。1-4、互连网络的分类互连网络的拓扑结构可以分为静态网络和动态网络两大类。其中静态网络包括：线性阵列和环、树和星网、k元n方网络等。其中动态网络又包括：总线、 多级网络、交叉开关。多级网络又包括：蝶式网络、 Q网等。实际中拓扑结构高性能计算机系统使用的互连网络既有动态互连网络，又静态互连网络还有两种网络的混合。1-5、互连网络的结构参数不管动态互连网络还是静态互连网络都有描述它的结构参数。1)动态互连网络的结构参数对动态互连网络一般关心其输入输出端数，当互连网络用来互连的结点 数小于网络输入或输出端数的

6、最小值时，并不要求输入输出端数相当。只当被互连结点数等于输入或输出端数的最大时才要求输入输出端数相等。动态互连网络还有单级和多级之分，某些单级网络可能需要使数据多次通过并每 次配合不同的开关状态控制才能完成特定的互连操作。这样的单级互连网络也叫循环网络，其循环次数与具体操作有关，也与网络的连接特性有关，互 连能力越强，循环次数越少。交叉开关和多级互连网络都是一次通过的网络。 除关心网络的输入输出端数和级数外，我们还关心网络的互连模式，开关元件类型和控制方式等，因为通过这些特性和参数并结合开关器件的性能不仅 可以明了网络的功能，还可估计网络的性能和性能价格比。对于动态互连网络常使用互连函数来进行

7、描述，首先介绍一下排列和置 换的概念。排列：N个数的每一种有确定次序的放置方法叫做一个 N排列。置换：把一个N排列变成另一个N排列的变换叫做N阶置换。在有N个输入端和N个输出端的网络中，输入端和输出端的连接关系 可以用置换来表示(输入端与输出端一一对应)。这种置换的方式可以用函 数的形式来表示，这样的函数就是互连函数。下面介绍几种基本的互连函数。.恒等函数：I(xn-1xn-2 x1x0)= xn-1xn-2 - x1x0. 交换函数： E(xn-1xn-2-x1x0)= xn-1xn-2-x1x0. 方体函数：Cubek(Xn 1Xn 2L XkL X。)(Xn 1Xn 2L XkL X0)

8、.洗牌函数：即输入端的二进制地址循环左移一位。Sh(Xn 1Xn 2L XkL X0) (Xn 2L XkL XXn 1)a,均匀洗牌：即先进行基本的洗牌函数，然后再经过一个方体函数。b.子洗牌：即最低k位循环左移一位。Sh.(Xn1L Xk iXkXkiL Xo) (Xn1L XkiXkiL XXk)c.超洗牌：即最高k-1位循环左移一位。kSh (Xn iXn 2L Xn k N kL X。)(X。2L X。k N N J X。) d.逆均匀洗牌：即输入端的二进制地址循环右移一位。1Sh (Xn iL X1X0) (XoXn iL Xi). 蝶式：输入端二进制地址的最高位和最低位互换位置。

9、(XniXn 2L X1X0) (XoXn 2L XiXni).PM2,函数：把输入端数组循环移动2的位置，得到输出端地址。PM 2 i(j) j 2i mod NPM 2 i(j) j 2i mod N其中，0 j N 1,0 i n 1, n log2N2)静态互连网络的结构参数静态互连网络不象动态互连网络通过开关的转换完成不同结点间的连 接和通信，而是在结点间固定连接形成的拓扑中， 按路由算法借助源和目的 结点问结点到目的结点的寻径过程。消息进行寻径以及在它们之间一系列相 邻路由器的协助下完成由源到目的结点的互连和通信，即静态互连网的寻径功能是分布的。静态互连网络也叫直径互连网络。 连接

10、通路是在寻路由过程 中被动形成的，因此连接通路也叫被动连接通路。 静态互连网络可按其拓扑 维数，网络形状和结点等进一步分类。在并行计算机系统中多按网络形状分， 如长线、线性陈列、环、树、网格、立方体等。由于静态互连网络中结点和 链路确定后其拓扑结才对应一个有向图 G(V, E)。其中V代表点(结点)集，E 代表边集(链路)集。所以可用图论知识对静态互连网络进行分析，并因此引 入相应结构参数。G(V, E)中一个结点向外连接的弧数，叫该结点的出度，连向该结点的弧 数叫该结点的入度。出度与入度的和叫该结点的度。结点集合中度的最大值 叫该网络的度。由于链路是由硬件形成，因此度越大，设备量也越大，当然

11、 互连性能也越好。距离和直径网络中任意两结点间的最短路径所经边数或跳步数叫做该二结点间的 距离;而距离的最大值叫该网络的直径。显然，直径越大，网络通信的平均 起步时间越长。因此希望网络直径小。但对结点数一定互连网络，直径和度 是矛盾的，直径小将导致度的增加。在选择网拓扑结构时需进行合理折衷。 一个可以接受的办法是找出二者乘积的极小值。等分带宽将N个结点的网络分成两个 N个结点的子网，其最小割集对应的链路 2带宽叫网络的等分带宽。等分带宽越高，网络通信能力越强。传输起步时间长度为一个传输宽度的消息在网络中传送时的最短传送时间叫起步时 问，也等于二结点间跳步(hop)数与每步时间的乘积。当消息传送

12、受阻时所 需时间叫传输延迟。网络吞吐率单位时间内网络处理或传输的消息总量叫网络吞吐率。它与网络中能同 时容纳的消息有关。热肯八、八、热点指一对不按比例地过多占用网络通信总量的结点。热点引起通信线路阻塞，过多的热点将导致网络性能的下降。热点吞吐率网络的热点吞吐率是指消息从热点中的一个结点到另一个结点的最大 传输速率。规则性和对称性结点间具有同一互连规律的网络叫规则性网络，规则性网络各结点的地 位是对称的。但对称的网络不一定是规则的。 如树型网络可能是对称的，但 不是规则的。规则的网络控制简单，且有利于网络负载的平衡。单工、半双工和全双工结点间互连通信只有一个方向的通信是单工的。 有两个方向但只能

13、分时 使用的是半双工的。既有两个方向又能同时使用的是全双工的。 全双工相当 于两个方向相反的单工，因此具有更高的带宽。1-6、互连网络的表示方法为了在输入结点与输出结点之间建立对应关系，互连网络有三种表示方法：(1)互连函数表示法：如 f(Xn iXn 2L XkL X0) (Xn 2L XkL XfXnl), 自变量和函数可以用二进制表示，也可以用十进制等表示。(2)图形表小法。(3)输入输出对应表示法。2.静态与动态互连网络高性能并行计算机系统一般用图 2.1所示的框图表示，它指出 N个结点机n。nN 1,通过互连网络IN互连，IN可能是动态互连网络也可能是静态互连网络。ni（i = 0N

14、-1）与IN的无.向互连一般表示全双工互连，m既可通过IN向其它结点发送信息，也可从IN接收其它结点发来的信息。一般，设二有向链路分别 对应IN的某号输入和输出端时，IN为动态互连网络，而当二有向链路分别对应 IN内某个路由器R,的输入和输出端时，IN为静态互连网络。图2.2给出了二 种互连网络的具体连接举例。图2.1 N节点高性能并行计算机a）动态互连（交叉开关）b）静态互连（2D-mesh）图2.24节点系统互连2-1、 静态互连网络静态互连网络也叫直接互连网络，静态互连网络是结点之间直接相连，是 结点之间直接相连，每个开关元件固定与一个结点相连，以建立该结点与邻近 结点之间的被动通路。这

15、种网络一旦构成后，就固定不变了，比较适合于构成通信模式可预测的并行处理系统和分布计算机系统。它构造的不是单级或多级 开关元件的集中互连网络，而是路由器间的某种直接互连模式，路由功能分布 的互连网络。决定消息传送的路径分布在相应的路由器上，由消息的源和目的 地址以及采用的路由算法决定，连接通路的形成是被动的，并称其为被动连接 通路。由于静态互连网络本质上是对动态互连网络集中功能的分散及其拓扑结 构上的特点，使得静态互连网络具有极好的规模可扩展性和很好的性能可扩展 性，可以将成千上万个处理结点互连成解决挑战性应用的高性能MPP系统。对于静态互连网络，结点间不同连接方法可以构成不同的网络拓扑结构。

16、由于静态互连网络不一定所有结点对间都直接互连，也不存在动态互连网络对 不同结点对根据的动态连接支持，所以非直接互连结点间的通信需要传输路径 上其它结点的帮助。常见的静态互连网络有线性阵列、环、树、星形网， k元n 立方体k-ary, n-cube的特例n维网格nD-mesh, n维环nD-torus和n立方体n-cube 等。特别 2D-mesh,3D-mesh,2D-torus,3D-torus和胖树 fat tree,在高性能并行计 算机系统中有广泛应用。1)线性阵列和环线性阵列是用N-1个半双工或全双工的链路连接N个结点形成的一维非 对称互连网络。见图2.3。半双工连接的N结点线性阵列，

17、结点度为2,链路 数为N-1,网络直径为N-1，等分带宽为1。而全双工链路连接时，结点度为 4,链路数为2(N-1),网络直接仍为N-1等分带宽为2。因线性阵列两个端结 点都有空闲链路，可在不影响现存结构的基础上支持结点的增加，所以系统 有较好的规模可扩展性。线性阵列可支持相邻结点间并行通信而不象总线同 时只支持一对结点通信。因此它比总线有更高的网络带宽，但线性阵列的网 络直径几乎随结点数增加而线性增加且结点间无冗余通信通路，所以网络的性能可扩展性和可靠性都相对较低。当把线性阵列两个端结点的空闲链路对接时，便形成对称的环网，环网 的结点度与形成环的线性阵列的结点度相同。并双工的链路数为N,网络

18、直径为 N，等分带宽为2。全双工时的链路数为2N,网络直径为-,等分 22 带宽为4。环网与线性阵列相比，不仅网络直径小了，等分带宽高了，且结 点间存在冗余通信电路，因此环网有更高的网络性能和更高的系统可靠性。因为环网是环形连接的，环的链路采用单向通道同样可以达到结点间的通信目的。单向环的网络直径为 N-1,通道数为N,等分带宽为2。单向通 道比半双工和全双工通道结构简单，代价低，但和线性阵列一样，当有一条 通道故障时便不能完成结点间的通信，因此系统的可靠性较低。图2.4 树2）树和星网树，一般指拓扑结构对应于图论中二叉树的静态互连网络。见图2.4。一个k层或树高为h=k-1的完全平衡二叉树的

19、结点数为 N=2k-1,结点度为3, 网络直径为2h,等分带宽为1,链路数为2k-2。由于结点度为3是定数，所 以树有相对好的规模可扩展性，但树的任二结点间只有唯一一条通路，任一 链路故障都会破坏网络的连通性，所以系统的可靠性较差。止匕外，不难看出， 越靠近根结点的链路，承受的消息流量越大。如不采取措施，这种不平衡，可能使靠近根结点的链路因带宽不够成为系统通信的瓶颈。为了解决这个问题，可把结点间的链路从叶结点所在层开始逐层增多，形成所谓胖树。理想 胖树结点上层的链路带宽为下层链路带宽之和，树高为h的二元树从底层开 始，链路数依次为1,2,，2h 1。不同层结点的度也相应增加。等分带宽为2h1,

20、链路数为h2h0实际应用中，为了提高胖树的互连性能，胖树除叶结 点配置计算结点和I/O结点外，高层结点均为路由器。即胖树只为叶结点问 的通信提供通信支持。此时树高为 h的胖树，其结点数为N=2h,路由器数 为2h-1,且各层的路由器是有不同的带宽。胖树不只有二元胖树还有多元胖 树，CM-5用的是4元胖树，Origin2000用的也是多元胖树。为了进一步挖掘树的性能潜力，也可用增加二元树树结点链路的办法来 减小网络直径，提高网络等分带宽和可靠性。当把同一父结点的二子结点相 连时，便构成所谓半环树。此时结点度由3增为4,网络直径由2h,成为2h-1, 等分带宽由1增为2,链路数由2h1-2增为3(

21、2h-1),链路数的增加提供了冗 余通路，提高了网络的可靠性。当把同一层的结点环接时，便构成全环树， 此时结点度为5,网络直径为2h1,等分带宽为2h+1,链路数为3(2h-1)+ho 星形网：星形网是树高为1的多元树，对结点数为N的星形网，见图2.5其 根结点度为N-1,叶结点度为1,网络直径为2,等分带宽为视根结点带宽而0图2.4 星行树k元n方网络k元n方网络这样一种拓扑结构，它有 n维，每维有k个结点相连。同 一维上相距最远的二结点可环接，也可不环接。环接时叫n维环网nD-torus, 不环接叫n维网格nD-mesh。见图2.5。在nD-toms中结点间的互连通道可 以是双向的，也可是

22、单向的，二者都能达到结点间通信的目的，但在nD-mesh 中因同一维上的结点不是环接的，结点间的互连通道只能是双向的，单向通 道不能实现结点间相互通信的功能。nD-torus网络的结点数 N= Kn ,并有一1K n= 10g K N和 K= Nn o结 点 度 d=2n,网 络直径 D=n ,等分市范 2BW=2N=2Kn1,互连通道数C=nN=nKn。nD-mesh网络的结点数和结点 K度与nD-torus相同，但网络直径D=n(k-1)，等分带宽BW= Kn 1,通道数c=n(K1)Kn1 =D -我们希望网络是“带宽、低延迟和低代价的，因此可用W来衡量网络D C的性能价格比PCR,即P

23、CR -BW 一类。对nD-mesh.,D C2BW PCRBWD*C D*D*BWD211,n Nn 1对结点数N一定的nD-mesh,维数n越高，性能价格比越高。当然，高维网络比低维网络的代价和实现难度大。选择互连网络时，我们希望它的结点度小且固定，直径小且随结点数的增加而缓慢增加，等分带宽大且随结点数的增加而较快增加。nD-mesh互连网络在上述相互矛盾的指标中有较好的折衷。其结点度d=2n不随结点数N的增加而改变。所以，有很好的规模可扩展性。网络直径D 1 1NnNBWNBWNDN当n=2时，n=3 时(N8),1 一1N n所以3D-mesh的性能可扩展性优于2D-mesh的性能可扩

24、展性。或者说 3D-mesh随着结点数N的增加，带宽增加的速率大于直径增加的高速率。网络性能提高的更快。这一结论同样适用了nD-torus。k-ary n-cube互连网络在高性能并行计算机系统中有重要应用。在综合考虑性能、代价和实现难度后，特别在采用虫孔路由切换技术时网络直径对长 报文传输的影响已被流水特性所缓解，一般取n=3或2。而不是维数高越好。如著名的 T3D T30 是 3D-torus,曙光 1000 是 2D-mesh。在 k-ary n-cube 中，当 n=1 , k=N 时 nD-mesh 和 nD-torus 分别变成 N 结 点线性阵列和N结点环。当n =log 2 N

25、 , k=2时，nD-mesh变成N结点的n 立方体。2-2、动态互连网络动态互连网络主要由所采用的开关元件，拓扑结构和控制方式决定。它一 般用有源开关元件来构造支持特定算法的拓扑结构，并实现互连模式下开关元 件的控制。决定互连模式的网络输入到输出的动态连接由开关元件的控制状态 决定，其连接通路称为主动连接通路。动态互连网络结构在逻辑和物理上都是 集中的，因此所能互连的规模不能很大，可扩展性较差。虽随着 VLST技术的 进步，其互连规模有所改善，但其可扩展性差的本质并未改变，一般只适合于 规模不大的SMP系统和对通信性能要求不高的计算机系统的互连。动态互连网络是通过仲裁器集中控制网络开关元件的

26、接通状态来实现程序 要求的所有互连模式。常用的动态互连网络有最简单的总线和最复杂的交叉开 关以及介于二者之间有不同连接特性的各种多级互连网络。1)总线总线可以通过接口互连多个部件或结点并对其进行分时服务。在处理机内部处理器、存储器和外设接口部件的互连多用称作系统总线的总线互连。 在多处理机和多计算机中，结点也可用总线互连。由于多个源结点在总线上 的信号会相互影响，所以每次通信只能有一个源结点和几个目的结点连通， 其它结点处于断开状态。多个结点通过总线进行通信需分时占用总线。因此 总线也叫时分总线。总线的仲裁部件应按一定的优先规则对多个请求进行仲 裁并将总线控制权交给其中一个请求。获得控制权的结

27、点首先要测试目的结 点的状态，建立连接关系，完成选址，然后进行通信。完成通信后，放弃控 制权释放总线，以便其它结点使用。仲裁可是集中的也可是分布的，但功能 是一致的。总线具有简洁实用，设备量小的特点。N个结点的总线设备量为O(N)。总线所能连接的部件或互连的结点数以及总线的工作频率与总线接口电路 的速度、驱动能力、总线长度和负载大小都有关。总线并不是一条简单的传输线，它应当是传输线和总线接口构成的系 统。尽管接口一般都与被连接的设备做在一起，但分析总线时应把接口归在 传输线一方。见图2.6总线上的结点度，网络直径和等分带宽均为 1, N结 点的设备量级为O(N)。总畿图2.6总线及结点互连2)

28、交叉开关交叉开关是动态互连网络中连接特性最好，设备量最大，但利用率较低跳网络。它和总线是动态网络中的两个极端。交叉开关如图2.7所示。N条垂直输入线与N条水平输出线的N2个交点由开关控制是否接通，且N2个交 点接通与否是独立的。因此，N X N交叉开关的设备量级为侧 O(N2),开关 2的状态数为2N。即使不包括选播在内的输入到输出的单值映射也有 N N个互 连状态，其中存在多到一的不被利用的状态。而真正有意义的互连是一对一 映射，互连状志数为N ! 因此交叉开关的使用效率很低，分别为弟和二!。2nN一对一的映射一般不用N2个开关构成，而用N个N选一的选择开关构成。尽管这一网络设备量仍然很大，

29、但由于其连接特性好，选址方便，控制简单, 且能一次通过。所以某些对通信能力要求较高，又规模不大的系统仍愿选择这种网络互连。网络的互连能力是指输入输出之间同时实现连接的最大数。而不是网络互能提供的连接数。典型的NX N交叉开关的度为2N,直径为1,等分带宽为N,设备量级为O(N2)。精点图2.7交叉开关和结点互连3)多级网络多级网络由axb交叉开关构成，其代价和性能介于总线和交叉开关之 问。axb开关多为2X2开关。如图2.8所示。2X 2开关的连接状态中有意 义的连接有四种：直送，交换，上播和下播。而多数多级网络只用直送和交 换两种功能。四状态时有两位控制线，二状态时，有一位控制线。直送交换上

30、播节播图2.8 2X2开关功能一个N输入和N输出的多级网络，因表征端口号(或被连结点号)的二进 制地址位数为n=log2 N ,所以多级网络的级数为log2 N ,每级2X2开关数 为N，因此多级网络的开关数为于 N log2 N ,设备量量级为0(Nlog2N ), 网络延迟为单级开关延迟的n=log2N倍，简称延迟为log2 N 0见图2.9,图 中各开关。单元的控制视互连模式的要求可以采用每个单元独立控制共 n - 2n 1 ,个信号，每级独立控制共n个信号，介于二者之间的部分级控制即 第i(i=0,1，n-1)级分配i+1个控制信号共n 个信号。合理选择控制 信号的状态，便可实现输入到

31、输出的相应连接。对于总线完成一次N N的通信至少需N次占用总线，延迟为 O(N),而交叉开关是一次通过的，延迟 为0(1),因此多级网络的设备和延迟均在总线与交叉开关之间，在性能和代价上作了折衷。总线、多级网络和交叉开关的延迟和设备的量级关系分别为 0(N)0( 10g2 N )0(1)和 O(N)O(N 10g2 N )N!,所以交叉开关的功能利用率很低。加之设备的量为伏O(N2), 因此交叉开关并不适合大系统互连。为了降低设备代价，并保持网络的无阻 塞连接特性，己经提出了多种无阻塞网络，其中有代表性的是clos网。2-3、 小结互连网络可分为静态互连网络和动态互连网络。静态网络使用直接链路

32、， 适合于构造通讯模型可预测或可用静态连接实现的计算机；动态网络是由开关 和通道实现的，它可动态地改变结构，使之与用户程序中的通讯要求匹配，动 态网络能根据程序要求实现所有的通讯模式，它不用固定连接，而是沿着连接 通路使用开关与仲裁器以提供动态连接特性。总线结构：在MPP互连网络中，总线结构（bus）是一种最简单、最廉价的结构，它 用一条公共链路将所有N个节点连接在一起。由于任何时刻只能有一对节点发 生连接关系，因而对分带宽最低，即总线本身能提供的带宽。传输及延迟在无 竞争的情况下是很好的，但总线竞争造成的瓶颈效应随节点数的增加而严重。 因而，总线结构较多应用在节点数较少的场合，如果要把更多的

33、节点用总线连 接起来，可以采用多层总线的结构，即上有主总线，下有子总线，一些通用的 总线协议，如Futurebus+,通过设计一定的适配器以支持构造多层总线。交叉开关结构：在MPP互连网络结构中，交叉开关结构（crossbar）是另一个极端，它为 N个节点的任意两个节点都提供一个连接， 是性能最好，代价最高的一种结构。 性能最好体现在任意两点间的逻辑距离相等且最小（即网络直径等于1）,同时对分带宽最高。由于交叉开关结构的复杂性及代价很高，因而这种结构更多地 被应用于某些MPP机的子集中。二维网络结构：在MPP互连网络结构中，应用比较普遍的是二维、三维及超立方体结构， 其中二维网络连接简单，每个

34、节点伸出上下左右四个通道与相邻节点相连，伸 缩性好，便于扩展，便于组装。但在靠近网络中心线的通道的交通量高于周边 通道的交通量，这是二维网络作为非对称网络的缺陷之一，但在选择路径方面 无死锁。三维网络结构：在MPP互连网络中，三维网络是另一种非对称性结构，并已成为近年来采 用较多的拓扑结构之一。其原因是因为二维网络在节点数较多时网络直径过大, 对分带宽随节点数的增加增长较慢；另一方面，半导体工艺的发展，使制造更 复杂、有更多通路的路由器成为可能，三维网络的连接代价较之二维网络增加 的比例不高，但网络直径大大缩短，延迟和对分带宽也都比二维网络有较大的 改进，三维网络存在的一个显著问题是设计上的困

35、难及组装的难度。3.实际应用中的互连网络大数并行处理系统MPP主要是为解决科学与工程计算中具有重大挑战性的 应用课程而进行研制的，它应是当时技术和工艺条件下速度最快的系统。MPP多用当时速度最快的微处理器构成，以便在相同规模下系统具有更高的峰值速 度。但峰值速度并不是系统的实际使用速度，实际使用速度还与应用特点有关。应用除共同需要高结点计算速度和大存储容量外，有些应用还需要高通信能力和高I/O能力的支持，这便需要 MPP系统有一个满足应用要求，确保系统高效的 高带宽、低延迟互连网络的支持。即使结点速度再高，由于通信性能支持不够， 系统的效率可能极低，极端情况可能低于单个结点的速度。 如果没有高

36、速I/O的 支持，即使计算的再快，而不能及时提供数据或计算结果输出时间过长，高计算速度便失去了意义。重大挑战性应用提出的1 Terafops计算能力，1 Terabyte主存容量和1 Terabyte/s的I/O能力。所谓3T性能己经达到，目前，美、日正在研 制高两至三个数量级的系统。目前基于硅器件的高性能微处理器的计算能力匹配于它的I/O能力，用于工程与科学计算的MPP系统，具结点计算能力远高于互连网络的通信能力。互连 网络既是MPP系统的关键部件，又是成为限制该类MPP系统性能进一步提高的 瓶颈。所以如何做到网络的高带宽和低延迟便至关重要，也异常困难。无疑把大 量处理器互连在一起，需要高性

37、能互连网络技术的支持，正如前面已经提到过的， 需要研究拓扑结构，切换技术、流控技术和路由算法，下面就对支持MPP系统的拓扑结构进行讨论。互连网络拓扑结构定义或规定了 MPP系统中结点间的互连方式，它在很大 程度上决定了系统的互连网络带宽、 延迟、系统的可扩展性、可靠性和对算法的 适应性。从系统的可扩展性、可靠性、性价比和易大规模集成电路实现考虑， MPP系统多采用静态互连网络进行结点互连。在设计MPP系统选择其互连网络时，需要在已有的丰富拓扑结构基础上， 针对应用要求和现有的技术条件， 设计满足性能要求的互连网络。互连网络的直 径、结点的度、等分带宽、对称性和可扩展性是选择互连网络时需考虑的因素， 一般希望：1）网络直径小，且随结点数目的增加而缓慢增大；2）对称性好；3）结点的度小且固定；4）可扩展性好；5）网络应有一定的冗余路径，使得局部出现故障时系统可继续工作，满足一定容错能力的要求；6）布线少而短；7）便于大规模集成。在当前技术条件下，动态互连网络中结点间不论相邻与否均通过开关进行互