第八章 互连网络拓扑结构概述 1.互连网络的基本概念 本章主要介绍高性能并行计算机系统互连网络的基本知识,这里包括了相关的背景、作用,互连网络的特性与指标,互连网络分类的依据与方法,互连网络的参数特性与表示方法等. 互连网络的背景与作用 从目前高性能计算机系统各组成部分的性能来看,由于VLSI技术的发展,器件的速度和集成度越来越高,价格越来越低,而连接各个结点形成高性能计算机系统的互连网络速度却越来越跟不上结点的速度,互连网络已成为制约高性能并行计算机系统性能发挥的瓶颈. 互连网络的应用十分广泛,从VLSI电路的内部总线到底板总线,计算机机中的处理器/存储器互连,系统局域网(SAN),电话交换网,用于ATM交换的内部网络,局域网,城域网,工业应用的网络,广域网直至今天的并行计算机系统互连,包括多处理机、多计算机系统和网络工作站.互连网络如此广泛的应用不仅推动了相应领域的进步,也奠定了互连网络在高性能并行计算机系统中的关键技术地位,并保证了它的不断发展. 高性能计算机系统互连网络的研究始于多计算机系统的互连,也是研究其它高性能计算机系统的基础.标准的缺乏以及对高性能网络的追求极大地推动了多计算机系统互连网络技术的发展,这些新技术反过来又被应用到分布共享主存的多处理机系统中,用以提高多处理机系统的可扩展性.这些技术包括应用局域网形成一类新型的高性能计算机系统:网络工作站.在商用并行计算机系统中,高效互连网络推动着高性能计算机系统的发展:如Intel公司的ASIC Red,IBM的"Blue Pacific",以及SGI的"Blue Mountain",计划等,这些TF级的超级计算机系统都是经极高性能的互连网络将数以千计的处理器连接成的系统,用以支持挑战性科学计算对高性能计算能力的需求.目前高性能计算机系统各类互连网络的研究已很深入,所追求的目标是高带宽、低延迟. 互连网络的定义 互连网络是由开关元件按照一定的拓补结构和控制方式构成的网络,用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接. 互连系统是构成高性能计算机系统和决定系统通信性能的关键部分,其主要功能是实现系统中大量结点之间的消息传送,因而其通信带宽和延迟将直接影响高性能计算机系统计算能力和效率的发挥. 互连网络的特性与常用指标 互连网络的特性关系到并行计算系统能否行之有效地工作,当我们考虑某一互连网络的特性时主要从一下几个因素进行比较: 构造这种网络的复杂程度和代价; 网络直径的大小及由此带来的延迟,延迟的均匀或不均匀性; 网络的对分带宽,即用一截面将网络划分成对等的两半时穿过该截面的最大传输率; 网络可伸缩性好不好,物理实现时组装是否方便; 网络中从一节点至另一节点是否存在多个通路的可选择性,可否会造成死锁,解决死锁的算法对网络交通的影响如何; 网络负载的均衡率,这是衡量网络在运行过程中通过每一个链路的信息量是否均衡的标志. 互连网络的分类 互连网络的拓扑结构可以分为静态网络和动态网络两大类.其中静态网络包括:线性阵列和环、树和星网、k元n方网络等.其中动态网络又包括:总线、多级网络、交叉开关.多级网络又包括:蝶式网络、Ω网等. 实际中拓扑结构高性能计算机系统使用的互连网络既有动态互连网络,又静态互连网络还有两种网络的混合. 互连网络的结构参数 不管动态互连网络还是静态互连网络都有描述它的结构参数. 动态互连网络的结构参数 对动态互连网络一般关心其输入输出端数,当互连网络用来互连的结点数小于网络输入或输出端数的最小值时,并不要求输入输出端数相当.只当被互连结点数等于输入或输出端数的最大时才要求输入输出端数相等.动态互连网络还有单级和多级之分,某些单级网络可能需要使数据多次通过并每次配合不同的开关状态控制才能完成特定的互连操作.这样的单级互连网络也叫循环网络,其循环次数与具体操作有关,也与网络的连接特性有关,互连能力越强,循环次数越少.交叉开关和多级互连网络都是一次通过的网络.除关心网络的输入输出端数和级数外,我们还关心网络的互连模式,开关元件类型和控制方式等,因为通过这些特性和参数并结合开关器件的性能不仅可以明了网络的功能,还可估计网络的性能和性能价格比. 对于动态互连网络常使用互连函数来进行描述,首先介绍一下排列和置换的概念. 排列: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 方体函数: 洗牌函数: 即输入端的二进制地址循环左移一位. 均匀洗牌: 即先进行基本的洗牌函数,然后再经过一个方体函数. 子洗牌: 即最低k位循环左移一位. 超洗牌: 即最高k-1位循环左移一位. 逆均匀洗牌:即输入端的二进制地址循环右移一位. 蝶式: 输入端二进制地址的最高位和最低位互换位置. PM2i函数: 把输入端数组循环移动2i的位置,得到输出端地址. 静态互连网络的结构参数 静态互连网络不象动态互连网络通过开关的转换完成不同结点间的连接和通信,而是在结点间固定连接形成的拓扑中,按路由算法借助源和目的结点间结点到目的结点的寻径过程.消息进行寻径以及在它们之间一系列相邻路由器的协助下完成由源到目的结点的互连和通信,即静态互连网的寻径功能是分布的.静态互连网络也叫直径互连网络.连接通路是在寻路由过程中被动形成的,因此连接通路也叫被动连接通路.静态互连网络可按其拓扑维数,网络形状和结点等进一步分类.在并行计算机系统中多按网络形状分,如长线、线性陈列、环、树、网格、立方体等.由于静态互连网络中结点和链路确定后其拓扑结构对应一个有向图G(V, E).其中V代表点(结点)集,E代表边集(链路)集.所以可用图论知识对静态互连网络进行分析,并因此引入相应结构参数. 度G(V, E)中一个结点向外连接的弧数,叫该结点的出度,连向该结点的弧数叫该结点的入度.出度与入度的和叫该结点的度.结点集合中度的最大值叫该网络的度.由于链路是由硬件形成,因此度越大,设备量也越大,当然互连性能也越好. 距离和直径 网络中任意两结点间的最短路径所经边数或跳步数叫做该二结点间的距离;而距离的最大值叫该网络的直径.显然,直径越大,网络通信的平均起步时间越长.因此希望网络直径小.但对结点数一定互连网络,直径和度是矛盾的,直径小将导致度的增加.在选择网拓扑结构时需进行合理折衷.一个可以接受的办法是找出二者乘积的极小值. 等分带宽 将N个结点的网络分成两个个结点的子网,其最小割集对应的链路带宽叫网络的等分带宽.等分带宽越高,网络通信能力越强. 传输起步时间 长度为一个传输宽度的消息在网络中传送时的最短传送时间叫起步时间,也等于二结点间跳步(hop)数与每步时间的乘积.当消息传送受阻时所需时间叫传输延迟. 网络吞吐率 单位时间内网络处理或传输的消息总量叫网络吞吐率.它与网络中能同时容纳的消息有关. 热点 热点指一对不按比例地过多占用网络通信总量的结点.热点引起通信线路阻塞,过多的热点将导致网络性能的下降. 热点吞吐率 网络的热点吞吐率是指消息从热点中的一个结点到另一个结点的最大传输速率. 规则性和对称性 结点间具有同一互连规律的网络叫规则性网络,规则性网络各结点的地位是对称的.但对称的网络不一定是规则的.如树型网络可能是对称的,但不是规则的.规则的网络控制简单,且有利于网络负载的平衡. 单工、半双工和全双工 结点间互连通信只有一个方向的通信是单工的.有两个方向但只能分时使用的是半双工的.既有两个方向又能同时使用的是全双工的.全双工相当于两个方向相反的单工,因此具有更高的带宽. 互连网络的表示方法 为了在输入结点与输出结点之间建立对应关系,互连网络有三种表示方法: (1) 互连函数表示法:如,自变量和函数可以用二进制表示,也可以用十进制等表示. (2) 图形表示法 . (3) 输入输出对应表示法. 2.静态与动态互连网络 高性能并行计算机系统一般用图2.1所示的框图表示,它指出N个结点机~,通过互连网络IN互连,IN可能是动态互连网络也可能是静态互连网络.(i = 0~N-1)与IN的无.向互连一般表示全双工互连,既可通过IN向其它结点发送信息,也可从IN接收其它结点发来的信息.一般,设二有向链路分别对应IN的某号输入和输出端时,IN为动态互连网络,而当二有向链路分别对应IN内某个路由器R,的输入和输出端时,IN为静态互连网络.图2.2给出了二种互连网络的具体连接举例. 静态互连网络 静态互连网络也叫直接互连网络,静态互连网络是结点之间直接相连,是结点之间直接相连,每个开关元件固定与一个结点相连,以建立该结点与邻近结点之间的被动通路.这种网络一旦构成后,就固定不变了,比较适合于构成通信模式可预测的并行处理系统和分布计算机系统.它构造的不是单级或多级开关元件的集中互连网络,而是路由器间的某种直接互连模式,路由功能分布的互连网络.决定消息传送的路径分布在相应的路由器上,由消息的源和目的地址以及采用的路由算法决定,连接通路的形成是被动的,并称其为被动连接通路.由于静态互连网络本质上是对动态互连网络集中功能的分散及其拓扑结构上的特点,使得静态互连网络具有极好的规模可扩展性和很好的性能可扩展性,可以将成千上万个处理结点互连成解决挑战性应用的高性能MPP系统. 对于静态互连网络,结点间不同连接方法可以构成不同的网络拓扑结构.由于静态互连网络不一定所有结点对间都直接互连,也不存在动态互连网络对不同结点对根据的动态连接支持,所以非直接互连结点间的通信需要传输路径上其它结点的帮助.常见的静态互连网络有线性阵列、环、树、星形网,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,在高性能并行计算机系统中有广泛应用. 线性阵列和环 线性阵列是用N-1个半双工或全双工的链路连接N个结点形成的一维非对称互连网络.见图2.3.半双工连接的N结点线性阵列,结点度为2,链路数为N-1,网络直径为N-1 ,等分带宽为1.而全双工链路连接时,结点度为4,链路数为2(N-1),网络直接仍为N-1等分带宽为2.因线性阵列两个端结点都有空闲链路,可在不影响现存结构的基础上支持结点的增加,所以系统有较好的规模可扩展性.线性阵列可支持相邻结点间并行通信而不象总线同时只支持一对结点通信.因此它比总线有更高的网络带宽,但线性阵列的网络直径几乎随结点数增加而线性增加且结点间无冗余通信通路,所以网络的性能可扩展性和可靠性都相对较低. 当把线性阵列两个端结点的空闲链路对接时,便形成对称的环网,环网的结点度与形成环的线性阵列的结点度相同.并双工的链路数为N,网络直径为,等分带宽为2.全双工时的链路数为2N,网络直径为,等分带宽为4.环网与线性阵列相比,不仅网络直径小了,等分带宽高了,且结点间存在冗余通信电路,因此环网有更高的网络性能和更高的系统可靠性. 因为环网是环形连接的,环的链路采用单向通道同样可以达到结点间的通信目的.单向环的网络直径为N-1,通道数为N,等分带宽为2.单向通道比半双工和全双工通道结构简单,代价低,但和线性阵列一样,当有一条通道故障时便不能完成结点间的通信,因此系统的可靠性较低. 树和星网 树,一般指拓扑结构对应于图论中二叉树的静态互连网络.见图2.4.一个k层或树高为h=k-1的完全平衡二叉树的结点数为N=-1,结点度为3,网络直径为2h,等分带宽为1,链路数为-2.由于结点度为3是定数,所以树有相对好的规模可扩展性,但树的任二结点间只有唯一一条通路,任一链路故障都会破坏网络的连通性,所以系统的可靠性较差.此外,不难看出,越靠近根结点的链路,承受的消息流量越大.如不采取措施,这种不平衡,可能使靠近根结点的链路因带宽不够成为系统通信的瓶颈.为了解决这个问题,可把结点间的链路从叶结点所在层开始逐层增多,形成所谓胖树.理想胖树结点上层的链路带宽为下层链路带宽之和,树高为h的二元树从底层开始,链路数依次为1, 2,…,.不同层结点的度也相应增加.等分带宽为,链路数为h.实际应用中,为了提高胖树的互连性能,胖树除叶结点配置计算结点和I/O结点外,高层结点均为路由器.即胖树只为叶结点间的通信提供通信支持.此时树高为h的胖树,其结点数为N=,路由器数为-1,且各层的路由器是有不同的带宽.胖树不只有二元胖树还有多元胖树,CM-5用的是4元胖树,Origin2000用的也是多元胖树. 为了进一步挖掘树的性能潜力,也可用增加二元树树结点链路的办法来减小网络直径,提高网络等分带宽和可靠性.当把同一父结点的二子结点相连时,便构成所谓半环树.此时结点度由3增为4,网络直径由2h,成为2h-1,等分带宽由1增为2,链路数由-2增为3(-1),链路数的增加提供了冗余通路,提高了网络的可靠性.当把同一层的结点环接时,便构成全环树,此时结点度为5,网络直径为,等分带宽为2h+1,链路数为3(-1)+h.星形网:星形网是树高为1的多元树,对结点数为N的星形网,见图2.5其根结点度为N-1,叶结点度为1,网络直径为2,等分带宽为视根结点带宽而异,可从1到. k元n方网络 k元n方网络这样一种拓扑结构,它有n维,每维有k个结点相连.同一维上相距最远的二结点可环接,也可不环接.环接时叫n维环网nD-torus,不环接叫n维网格nD-mesh.见图2.5.在nD-toms中结点间的互连通道可以是双向的,也可是单向的,二者都能达到结点间通信的目的,但在nD-mesh中因同一维上的结点不是环接的,结点间的互连通道只能是双向的,单向通道不能实现结点间相互通信的功能.nD-torus网络的结点数N=,并有n=和K=.结点度d=2n,网络直径D=n,等分带宽BW=2=2,互连通道数C=nN=n. nD-mesh网络的结点数和结点度与nD-torus相同,但网络直径D=n(k-1),等分带宽BW=,通道数c=n(K一1) =D·BW. 我们希望网络是"带宽、低延迟和低代价的,因此可用来衡量网络的性能价格比PCR,即PCR一类.对nD-mesh., , 对结点数N一定的nD-mesh,维数n越高,性能价格比越高. 当然,高维网络比低维网络的代价和实现难度大.选择互连网络时,我们希望它的结点度小且固定,直径小且随结点数的增加而缓慢增加,等分带宽大且随结点数的增加而较快增加.nD-mesh互连网络在上述相互矛盾的指标中有较好的折衷.其结点度d=2n不随结点数N的增加而改变.所以,有很好的规模可扩展性.网络直径D=,等分带宽BW=,而,,,当n=2时,,n=3时. 所以3D-mesh的性能可扩展性优于2D-mesh的性能可扩展性.或者说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 =, k=2时,nD-mesh变成N结点的n立方体. 动态互连网络 动态互连网络主要由所采用的开关元件,拓扑结构和控制方式决定.它一般用有源开关元件来构造支持特定算法的拓扑结构,并实现互连模式下开关元件的控制.决定互连模式的网络输入到输出的动态连接由开关元件的控制状态决定,其连接通路称为主动连接通路.动态互连网络结构在逻辑和物理上都是集中的,因此所能互连的规模不能很大,可扩展性较差.虽随着VLST技术的进步,其互连规模有所改善,但其可扩展性差的本质并未改变,一般只适合于规模不大的SMP系统和对通信性能要求不高的计算机系统的互连. 动态互连网络是通过仲裁器集中控制网络开关元件的接通状态来实现程序要求的所有互连模式.常用的动态互连网络有最简单的总线和最复杂的交叉开关以及介于二者之间有不同连接特性的各种多级互连网络. 总线 总线可以通过接口互连多个部件或结点并对其进行分时服务.在处理机内部处理器、存储器和外设接口部件的互连多用称作系统总线的总线互连.在多处理机和多计算机中,结点也可用总线互连.由于多个源结点在总线上的信号会相互影响,所以每次通信只能有一个源结点和几个目的结点连通,其它结点处于断开状态.多个结点通过总线进行通信需分时占用总线.因此总线也叫时分总线.总线的仲裁部件应按一定的优先规则对多个请求进行仲裁并将总线控制权交给其中一个请求.获得控制权的结点首先要测试目的结点的状态,建立连接关系,完成选址,然后进行通信.完成通信后,放弃控制权释放总线,以便其它结点使用.仲裁可是集中的也可是分布的,但功能是一致的. 总线具有简洁实用,设备量小的特点.N个结点的总线设备量为O(N).总线所能连接的部件或互连的结点数以及总线的工作频率与总线接口电路的速度、驱动能力、总线长度和负载大小都有关. 总线并不是一条简单的传输线,它应当是传输线和总线接口构成的系统.尽管接口一般都与被连接的设备做在一起,但分析总线时应把接口归在传输线一方.见图2.6总线上的结点度,网络直径和等分带宽均为1,N结点的设备量级为O(N). 交叉开关 交叉开关是动态互连网络中连接特性最好,设备量最大,但利用率较低跳网络.它和总线是动态网络中的两个极端.交叉开关如图2.7所示.N条垂直输入线与N条水平输出线的个交点由开关控制是否接通,且个交点接通与否是独立的.因此,N*N交叉开关的设备量级为侧O(),开关的状态数为.即使不包括选播在内的输入到输出的单值映射也有个互连状态,其中存在多到一的不被利用的状态.而真正有意义的互连是一对一映射,互连状志数为N!·因此交叉开关的使用效率很低,分别为和.一对一的映射一般不用个开关构成,而用N个N选一的选择开关构成.尽管这一网络设备量仍然很大,但由于其连接特性好,选址方便,控制简单,且能一次通过.所以某些对通信能力要求较高,又规模不大的系统仍愿选择这种网络互连. 网络的互连能力是指输入输出之间同时实现连接的最大数.而不是网络互能提供的连接数.典型的N*N交叉开关的度为2N,直径为1,等分带宽为N,设备量级为O(). 多级网络 多级网络由a*b交叉开关构成,其代价和性能介于总线和交叉开关之间.a*b开关多为2*2开关.如图2.8所示.2*2开关的连接状态中有意义的连接有四种:直送,交换,上播和下播.而多数多级网络只用直送和交换两种功能.四状态时有两位控制线,二状态时,有一位控制线. 一个N输入和N输出的多级网络,因表征端口号(或被连结点号)的二进制地址位数为n=,所以多级网络的级数为,每级2*2开关数为,因此多级网络的开关数为于,设备量量级为0(N ),网络延迟为单级开关延迟的n=倍,简称延迟为.见图2.9,图中各开关.单元的控制视互连模式的要求可以采用每个单元独立控制共n·,个信号,每级独立控制共n个信号,介于二者之间的部分级控制即第i(i=0, 1, … , n-1)级分配i+1个控制信号共个信号.合理选择控制信号的状态,便可实现输入到输出的相应连接.对于总线完成一次NN的通信至少需N次占用总线,延迟为O(N),而交叉开关是一次通过的,延迟为O(1),因此多级网络的设备和延迟均在总线与交叉开关之间,在性能和代价上作了折衷.总线、多级网络和交叉开关的延迟和设备的量级关系分别为O(N)>O()>O(1)和O(N)
>N!,所以交叉开关的功能利用率很低.加之设备的量为伏O(),因此交叉开关并不适合大系统互连.为了降低设备代价,并保持网络的无阻塞连接特性,己经提出了多种无阻塞网络,其中有代表性的是clos网. 小结 互连网络可分为静态互连网络和动态互连网络.静态网络使用直接链路,适合于构造通讯模型可预测或可用静态连接实现的计算机;动态网络是由开关和通道实现的,它可动态地改变结构,使之与用户程序中的通讯要求匹配,动态网络能根据程序要求实现所有的通讯模式,它不用固定连接,而是沿着连接通路使用开关与仲裁器以提供动态连接特性. 总线结构: 在MPP互连网络中,总线结构(bus)是一种最简单、最廉价的结构,它用一条公共链路将所有N个节点连接在一起.由于任何时刻只能有一对节点发生连接关系,因而对分带宽最低,即总线本身能提供的带宽.传输及延迟在无竞争的情况下是很好的,但总线竞争造成的瓶颈效应随节点数的增加而严重.因而,总线结构较多应用在节点数较少的场合,如果要把更多的节点用总线连接起来,可以采用多层总线的结构,即上有主总线,下有子总线,一些通用的总线协议,如Futurebus+,通过设计一定的适配器以支持构造多层总线. 交叉开关结构: 在MPP互连网络结构中,交叉开关结构(crossbar)是另一个极端,它为N个节点的任意两个节点都提供一个连接,是性能最好,代价最高的一种结构.性能最好体现在任意两点间的逻辑距离相等且最小(即网络直径等于1),同时对分带宽最高.由于交叉开关结构的复杂性及代价很高,因而这种结构更多地被应用于某些MPP机的子集中. 二维网络结构: 在MPP互连网络结构中,应用比较普遍的是二维、三维及超立方体结构,其中二维网络连接简单,每个节点伸出上下左右四个通道与相邻节点相连,伸缩性好,便于扩展,便于组装.但在靠近网络中心线的通道的交通量高于周边通道的交通量,这是二维网络作为非对称网络的缺陷之一,但在选择路径方面无死锁. 三维网络结构: 在MPP互连网络中,三维网络是另一种非对称性结构,并已成为近年来采用较多的拓扑结构之一.其原因是因为二维网络在节点数较多时网络直径过大,对分带宽随节点数的增加增长较慢;另一方面,半导体工艺的发展,使制造更复杂、有更多通路的路由器成为可能,三维网络的连接代价较之二维网络增加的比例不高,但网络直径大大缩短,延迟和对分带宽也都比二维网络有较大的改进,三维网络存在的一个显著问题是设计上的困难及组装的难度. 3.实际应用中的互连网络 大数并行处理系统MPP主要是为解决科学与工程计算中具有重大挑战性的应用课程而进行研制的,它应是当时技术和工艺条件下速度最快的系统.MPP多用当时速度最快的微处理器构成,以便在相同规模下系统具有更高的峰值速度.但峰值速度并不是系统的实际使用速度,实际使用速度还与应用特点有关.应用除共同需要高结点计算速度和大存储容量外,有些应用还需要高通信能力和高I/O能力的支持,这便需要MPP系统有一个满足应用要求,确保系统高效的高带宽、低延迟互连网络的支持.即使结点速度再高,由于通信性能支持不够,系统的效率可能极低,极端情况可能低于单个结点的速度.如果没有高速1/O的支持,即使计算的再快,而不能及时提供数据或计算结果输出时间过长,高计算速度便失去了意义.重大挑战性应用提出的1 Terafops计算能力,1 Terabyte主存容量和1 Terabyte/s的1/O能力.所谓3T性能己经达到,目前,美、日正在研制高两至三个数量级的系统. 目前基于硅器件的高性能微处理器的计算能力匹配于它的I/O能力,用于工程与科学计算的MPP系统,其结点计算能力远高于互连网络的通信能力.互连网络既是MPP系统的关键部件,又是成为限制该类MPP系统性能进一步提高的瓶颈.所以如何做到网络的高带宽和低延迟便至关重要,也异常困难.无疑把大量处理器互连在一起,需要高性能互连网络技术的支持,正如前面已经提到过的,需要研究拓扑结构,切换技术、流控技术和路由算法,下面就对支持MPP系统的拓扑结构进行讨论. 互连网络拓扑结构定义或规定了MPP系统中结点间的互连方式,它在很大程度上决定了系统的互连网络带宽、延迟、系统的可扩展性、可靠性和对算法的适应性.从系统的可扩展性、可靠性、性价比和易大规模集成电路实现考虑,MPP系统多采用静态互连网络进行结点互连. 在设计MPP系统选择其互连网络时,需要在已有的丰富拓扑结构基础上,针对应用要求和现有的技术条件,设计满足性能要求的互连网络.互连网络的直径、结点的度、等分带宽、对称性和可扩展性是选择互连网络时需考虑的因素,一般希望:1)网络直径小,且随结点数目的增加而缓慢增大;2)对称性好;3)结点的度小且固定;4)可扩展性好;5)网络应有一定的冗余路径,使得局部出现故障时系统可继续工作,满足一定容错能力的要求;6)布线少而短;7)便于大规模集成. 在当前技术条件下,动态互连网络中结点间不论相邻与否均通过开关进行互连,存在可扩展性较差、硬件实现较困难且开关元件成本昂贵的缺点,而相比之下静态互连网络具有可伸缩性好、实现简单、易于大规模集成的优点,因而大多数MPP系统均采用直接互连网络. 对于直接网络拓扑结构的维数选取问题,人们己进行了大量研究,在不同的假设限制条件下有不同的结论,最初的研究中用消息所经过的跳步数来评价网络延迟,得出超立方体最优的结论,从而导致第一代MPP系统大多采用超立方体作为互连网络拓扑结构,典型的如nCUBE公司推出的nCUBE系列;其后,Dally考虑线上传输延迟,在相同等分带宽的情况下对不同网络性能进行分析,得出低维网络延迟较低的结论:Agarwal在相同结点数的情况下对不同网络的性能进行研究,得出三维网格形网络延迟最低、性能最优的结论,后两种结论的得出导致了第二代MPP系统大多从超立方体转向低维的Mesh或Torus拓扑结构,典型的有Cray Research公司的Cray T-3D系统采用了三维环网(3D-Torus)结构,Intel公司的Intel Paragon系统采用了二维网格(2D-Mesh )结构,国防科大银河Ⅲ系统采用3D-torus,曙光-1000采用2D-Mesh.由于这类低维直接网络具有可伸缩性好、对称性好、设计简单、算法高效等优点,因此目前MPP系统中仍以这类网络结构为首选结构.近来又有不少研究者在新的限制条件下对网络特性进行研究,得出了新的结论.其中最为引人注目的是近来S.L.Scott基于用流水通道进行结点互连的研究中又得出高维网络性能更优的结构,但高维网络会占用更多的集成电路总位引脚和更多的片外连线以及流水通道对工艺和技术的更高要求,但在今后随着工艺和技术的进步将会得到发展. 总结 互连的问题随着高性能计算机系统处理能力的不断增强,而越来越突现出来的.大规模并行处理系统由多个微处理器组成,其峰值处理速度由处理机个数决定,故所需的互连带宽更加巨大.这就对高性能计算机系统的互连性能提出了更高要求. 互连系统是构成高性能计算机系统和决定系统通信性能的关键部分,它包括连接高性能计算机系统中连接结点的互连网络和互连网络到结点的接口等完成整个消息通信的所有软、硬件功能结构.其主要功能是实现系统中大量结点机间的消息传送—通信.因而其通信带宽和延迟将直接影响高性能计算机系统计算能力的发挥.我们希望互连系统的带宽和延迟相对结点机的速度和应用程序的通信粒度是高带宽和低延迟的,以充分发挥高性能计算机系统的计算能力和效率. 参考文献: [1] Kai Hwang 著 王鼎兴 沈美明 郑纬民 温冬婵 译 《高等计算机系统结构-并行性 可扩展性 可编程性》 清华大学出版社 广西科学技术出版社 [2] 《高等计算机系统结构》 课堂讲义 [3] 邓波《高性能计算机互连系统研究》 国防科技大学计算机学院工学博士学位论文 [4] 杨联纲 吴军《高端计算机技术发展特点及趋势》 计算机与现代化 2001年第6期[5] 汪小平 《几类互连网络上平行路径的寻径算法》 电子科技大学硕士学位论文
下载该文档
文档格式：DOC
更新时间：2013-06-22
下载次数：0
点击次数：1
第八章 互连网络拓扑结构概述 1.互连网络的基本概念 本章主要介绍高性能并行计算机系统互连网络的基本知识,这里包括了相关的背景、作用,互连网络的特性与指标,互连网络分类的依据与方法,互连网络的参数特性与表示方法等. 互连网络的背景与作用 从目前高性能计算机系统各组成部分的性能来看,由于VLSI技术的发展,器件的速度和集成度越来越高,价格越来越低,而连接各个结点形成高性能计算机系统的互连网络速度却越来越跟不上结点的速度,互连网络已成为制约高性能并行计算机系统性能发挥的瓶颈. 互连网络的应用十分广泛,从VLSI电路的内部总线到底板总线,计算机机中的处理器/存储器互连,系统局域网(SAN),电话交换网,用于ATM交换的内部网络,局域网,城域网,工业应用的网络,广域网直至今天的并行计算机系统互连,包括多处理机、多计算机系统和网络工作站.互连网络如此广泛的应用不仅推动了相应领域的进步,也奠定了互连网络在高性能并行计算机系统中的关键技术地位,并保证了它的不断发展. 高性能计算机系统互连网络的研究始于多计算机系统的互连,也是研究其它高性能计算机系统的基础.标准的缺乏以及对高性能网络的追求极大地推动了多计算机系统互连网络技术的发展,这些新技术反过来又被应用到分布共享主存的多处理机系统中,用以提高多处理机系统的可扩展性.这些技术包括应用局域网形成一类新型的高性能计算机系统:网络工作站.在商用并行计算机系统中,高效互连网络推动着高性能计算机系统的发展:如Intel公司的ASIC Red,IBM的"Blue Pacific",以及SGI的"Blue Mountain",计划等,这些TF级的超级计算机系统都是经极高性能的互连网络将数以千计的处理器连接成的系统,用以支持挑战性科学计算对高性能计算能力的需求.目前高性能计算机系统各类互连网络的研究已很深入,所追求的目标是高带宽、低延迟. 互连网络的定义 互连网络是由开关元件按照一定的拓补结构和控制方式构成的网络,用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接. 互连系统是构成高性能计算机系统和决定系统通信性能的关键部分,其主要功能是实现系统中大量结点之间的消息传送,因而其通信带宽和延迟将直接影响高性能计算机系统计算能力和效率的发挥. 互连网络的特性与常用指标 互连网络的特性关系到并行计算系统能否行之有效地工作,当我们考虑某一互连网络的特性时主要从一下几个因素进行比较: 构造这种网络的复杂程度和代价; 网络直径的大小及由此带来的延迟,延迟的均匀或不均匀性; 网络的对分带宽,即用一截面将网络划分成对等的两半时穿过该截面的最大传输率; 网络可伸缩性好不好,物理实现时组装是否方便; 网络中从一节点至另一节点是否存在多个通路的可选择性,可否会造成死锁,解决死锁的算法对网络交通的影响如何; 网络负载的均衡率,这是衡量网络在运行过程中通过每一个链路的信息量是否均衡的标志. 互连网络的分类 互连网络的拓扑结构可以分为静态网络和动态网络两大类.其中静态网络包括:线性阵列和环、树和星网、k元n方网络等.其中动态网络又包括:总线、多级网络、交叉开关.多级网络又包括:蝶式网络、Ω网等. 实际中拓扑结构高性能计算机系统使用的互连网络既有动态互连网络,又静态互连网络还有两种网络的混合. 互连网络的结构参数 不管动态互连网络还是静态互连网络都有描述它的结构参数. 动态互连网络的结构参数 对动态互连网络一般关心其输入输出端数,当互连网络用来互连的结点数小于网络输入或输出端数的最小值时,并不要求输入输出端数相当.只当被互连结点数等于输入或输出端数的最大时才要求输入输出端数相等.动态互连网络还有单级和多级之分,某些单级网络可能需要使数据多次通过并每次配合不同的开关状态控制才能完成特定的互连操作.这样的单级互连网络也叫循环网络,其循环次数与具体操作有关,也与网络的连接特性有关,互连能力越强,循环次数越少.交叉开关和多级互连网络都是一次通过的网络.除关心网络的输入输出端数和级数外,我们还关心网络的互连模式,开关元件类型和控制方式等,因为通过这些特性和参数并结合开关器件的性能不仅可以明了网络的功能,还可估计网络的性能和性能价格比. 对于动态互连网络常使用互连函数来进行描述,首先介绍一下排列和置换的概念. 排列: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 方体函数: 洗牌函数: 即输入端的二进制地址循环左移一位. 均匀洗牌: 即先进行基本的洗牌函数,然后再经过一个方体函数. 子洗牌: 即最低k位循环左移一位. 超洗牌: 即最高k-1位循环左移一位. 逆均匀洗牌:即输入端的二进制地址循环右移一位. 蝶式: 输入端二进制地址的最高位和最低位互换位置. PM2i函数: 把输入端数组循环移动2i的位置,得到输出端地址. 静态互连网络的结构参数 静态互连网络不象动态互连网络通过开关的转换完成不同结点间的连接和通信,而是在结点间固定连接形成的拓扑中,按路由算法借助源和目的结点间结点到目的结点的寻径过程.消息进行寻径以及在它们之间一系列相邻路由器的协助下完成由源到目的结点的互连和通信,即静态互连网的寻径功能是分布的.静态互连网络也叫直径互连网络.连接通路是在寻路由过程中被动形成的,因此连接通路也叫被动连接通路.静态互连网络可按其拓扑维数,网络形状和结点等进一步分类.在并行计算机系统中多按网络形状分,如长线、线性陈列、环、树、网格、立方体等.由于静态互连网络中结点和链路确定后其拓扑结构对应一个有向图G(V, E).其中V代表点(结点)集,E代表边集(链路)集.所以可用图论知识对静态互连网络进行分析,并因此引入相应结构参数. 度G(V, E)中一个结点向外连接的弧数,叫该结点的出度,连向该结点的弧数叫该结点的入度.出度与入度的和叫该结点的度.结点集合中度的最大值叫该网络的度.由于链路是由硬件形成,因此度越大,设备量也越大,当然互连性能也越好. 距离和直径 网络中任意两结点间的最短路径所经边数或跳步数叫做该二结点间的距离;而距离的最大值叫该网络的直径.显然,直径越大,网络通信的平均起步时间越长.因此希望网络直径小.但对结点数一定互连网络,直径和度是矛盾的,直径小将导致度的增加.在选择网拓扑结构时需进行合理折衷.一个可以接受的办法是找出二者乘积的极小值. 等分带宽 将N个结点的网络分成两个个结点的子网,其最小割集对应的链路带宽叫网络的等分带宽.等分带宽越高,网络通信能力越强. 传输起步时间 长度为一个传输宽度的消息在网络中传送时的最短传送时间叫起步时间,也等于二结点间跳步(hop)数与每步时间的乘积.当消息传送受阻时所需时间叫传输延迟. 网络吞吐率 单位时间内网络处理或传输的消息总量叫网络吞吐率.它与网络中能同时容纳的消息有关. 热点 热点指一对不按比例地过多占用网络通信总量的结点.热点引起通信线路阻塞,过多的热点将导致网络性能的下降. 热点吞吐率 网络的热点吞吐率是指消息从热点中的一个结点到另一个结点的最大传输速率. 规则性和对称性 结点间具有同一互连规律的网络叫规则性网络,规则性网络各结点的地位是对称的.但对称的网络不一定是规则的.如树型网络可能是对称的,但不是规则的.规则的网络控制简单,且有利于网络负载的平衡. 单工、半双工和全双工 结点间互连通信只有一个方向的通信是单工的.有两个方向但只能分时使用的是半双工的.既有两个方向又能同时使用的是全双工的.全双工相当于两个方向相反的单工,因此具有更高的带宽. 互连网络的表示方法 为了在输入结点与输出结点之间建立对应关系,互连网络有三种表示方法: (1) 互连函数表示法:如,自变量和函数可以用二进制表示,也可以用十进制等表示. (2) 图形表示法 . (3) 输入输出对应表示法. 2.静态与动态互连网络 高性能并行计算机系统一般用图2.1所示的框图表示,它指出N个结点机~,通过互连网络IN互连,IN可能是动态互连网络也可能是静态互连网络.(i = 0~N-1)与IN的无.向互连一般表示全双工互连,既可通过IN向其它结点发送信息,也可从IN接收其它结点发来的信息.一般,设二有向链路分别对应IN的某号输入和输出端时,IN为动态互连网络,而当二有向链路分别对应IN内某个路由器R,的输入和输出端时,IN为静态互连网络.图2.2给出了二种互连网络的具体连接举例. 静态互连网络 静态互连网络也叫直接互连网络,静态互连网络是结点之间直接相连,是结点之间直接相连,每个开关元件固定与一个结点相连,以建立该结点与邻近结点之间的被动通路.这种网络一旦构成后,就固定不变了,比较适合于构成通信模式可预测的并行处理系统和分布计算机系统.它构造的不是单级或多级开关元件的集中互连网络,而是路由器间的某种直接互连模式,路由功能分布的互连网络.决定消息传送的路径分布在相应的路由器上,由消息的源和目的地址以及采用的路由算法决定,连接通路的形成是被动的,并称其为被动连接通路.由于静态互连网络本质上是对动态互连网络集中功能的分散及其拓扑结构上的特点,使得静态互连网络具有极好的规模可扩展性和很好的性能可扩展性,可以将成千上万个处理结点互连成解决挑战性应用的高性能MPP系统. 对于静态互连网络,结点间不同连接方法可以构成不同的网络拓扑结构.由于静态互连网络不一定所有结点对间都直接互连,也不存在动态互连网络对不同结点对根据的动态连接支持,所以非直接互连结点间的通信需要传输路径上其它结点的帮助.常见的静态互连网络有线性阵列、环、树、星形网,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,在高性能并行计算机系统中有广泛应用. 线性阵列和环 线性阵列是用N-1个半双工或全双工的链路连接N个结点形成的一维非对称互连网络.见图2.3.半双工连接的N结点线性阵列,结点度为2,链路数为N-1,网络直径为N-1 ,等分带宽为1.而全双工链路连接时,结点度为4,链路数为2(N-1),网络直接仍为N-1等分带宽为2.因线性阵列两个端结点都有空闲链路,可在不影响现存结构的基础上支持结点的增加,所以系统有较好的规模可扩展性.线性阵列可支持相邻结点间并行通信而不象总线同时只支持一对结点通信.因此它比总线有更高的网络带宽,但线性阵列的网络直径几乎随结点数增加而线性增加且结点间无冗余通信通路,所以网络的性能可扩展性和可靠性都相对较低. 当把线性阵列两个端结点的空闲链路对接时,便形成对称的环网,环网的结点度与形成环的线性阵列的结点度相同.并双工的链路数为N,网络直径为,等分带宽为2.全双工时的链路数为2N,网络直径为,等分带宽为4.环网与线性阵列相比,不仅网络直径小了,等分带宽高了,且结点间存在冗余通信电路,因此环网有更高的网络性能和更高的系统可靠性. 因为环网是环形连接的,环的链路采用单向通道同样可以达到结点间的通信目的.单向环的网络直径为N-1,通道数为N,等分带宽为2.单向通道比半双工和全双工通道结构简单,代价低,但和线性阵列一样,当有一条通道故障时便不能完成结点间的通信,因此系统的可靠性较低. 树和星网 树,一般指拓扑结构对应于图论中二叉树的静态互连网络.见图2.4.一个k层或树高为h=k-1的完全平衡二叉树的结点数为N=-1,结点度为3,网络直径为2h,等分带宽为1,链路数为-2.由于结点度为3是定数,所以树有相对好的规模可扩展性,但树的任二结点间只有唯一一条通路,任一链路故障都会破坏网络的连通性,所以系统的可靠性较差.此外,不难看出,越靠近根结点的链路,承受的消息流量越大.如不采取措施,这种不平衡,可能使靠近根结点的链路因带宽不够成为系统通信的瓶颈.为了解决这个问题,可把结点间的链路从叶结点所在层开始逐层增多,形成所谓胖树.理想胖树结点上层的链路带宽为下层链路带宽之和,树高为h的二元树从底层开始,链路数依次为1, 2,…,.不同层结点的度也相应增加.等分带宽为,链路数为h.实际应用中,为了提高胖树的互连性能,胖树除叶结点配置计算结点和I/O结点外,高层结点均为路由器.即胖树只为叶结点间的通信提供通信支持.此时树高为h的胖树,其结点数为N=,路由器数为-1,且各层的路由器是有不同的带宽.胖树不只有二元胖树还有多元胖树,CM-5用的是4元胖树,Origin2000用的也是多元胖树. 为了进一步挖掘树的性能潜力,也可用增加二元树树结点链路的办法来减小网络直径,提高网络等分带宽和可靠性.当把同一父结点的二子结点相连时,便构成所谓半环树.此时结点度由3增为4,网络直径由2h,成为2h-1,等分带宽由1增为2,链路数由-2增为3(-1),链路数的增加提供了冗余通路,提高了网络的可靠性.当把同一层的结点环接时,便构成全环树,此时结点度为5,网络直径为,等分带宽为2h+1,链路数为3(-1)+h.星形网:星形网是树高为1的多元树,对结点数为N的星形网,见图2.5其根结点度为N-1,叶结点度为1,网络直径为2,等分带宽为视根结点带宽而异,可从1到. k元n方网络 k元n方网络这样一种拓扑结构,它有n维,每维有k个结点相连.同一维上相距最远的二结点可环接,也可不环接.环接时叫n维环网nD-torus,不环接叫n维网格nD-mesh.见图2.5.在nD-toms中结点间的互连通道可以是双向的,也可是单向的,二者都能达到结点间通信的目的,但在nD-mesh中因同一维上的结点不是环接的,结点间的互连通道只能是双向的,单向通道不能实现结点间相互通信的功能.nD-torus网络的结点数N=,并有n=和K=.结点度d=2n,网络直径D=n,等分带宽BW=2=2,互连通道数C=nN=n. nD-mesh网络的结点数和结点度与nD-torus相同,但网络直径D=n(k-1),等分带宽BW=,通道数c=n(K一1) =D·BW. 我们希望网络是"带宽、低延迟和低代价的,因此可用来衡量网络的性能价格比PCR,即PCR一类.对nD-mesh., , 对结点数N一定的nD-mesh,维数n越高,性能价格比越高. 当然,高维网络比低维网络的代价和实现难度大.选择互连网络时,我们希望它的结点度小且固定,直径小且随结点数的增加而缓慢增加,等分带宽大且随结点数的增加而较快增加.nD-mesh互连网络在上述相互矛盾的指标中有较好的折衷.其结点度d=2n不随结点数N的增加而改变.所以,有很好的规模可扩展性.网络直径D=,等分带宽BW=,而,,,当n=2时,,n=3时. 所以3D-mesh的性能可扩展性优于2D-mesh的性能可扩展性.或者说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 =, k=2时,nD-mesh变成N结点的n立方体. 动态互连网络 动态互连网络主要由所采用的开关元件,拓扑结构和控制方式决定.它一般用有源开关元件来构造支持特定算法的拓扑结构,并实现互连模式下开关元件的控制.决定互连模式的网络输入到输出的动态连接由开关元件的控制状态决定,其连接通路称为主动连接通路.动态互连网络结构在逻辑和物理上都是集中的,因此所能互连的规模不能很大,可扩展性较差.虽随着VLST技术的进步,其互连规模有所改善,但其可扩展性差的本质并未改变,一般只适合于规模不大的SMP系统和对通信性能要求不高的计算机系统的互连. 动态互连网络是通过仲裁器集中控制网络开关元件的接通状态来实现程序要求的所有互连模式.常用的动态互连网络有最简单的总线和最复杂的交叉开关以及介于二者之间有不同连接特性的各种多级互连网络. 总线 总线可以通过接口互连多个部件或结点并对其进行分时服务.在处理机内部处理器、存储器和外设接口部件的互连多用称作系统总线的总线互连.在多处理机和多计算机中,结点也可用总线互连.由于多个源结点在总线上的信号会相互影响,所以每次通信只能有一个源结点和几个目的结点连通,其它结点处于断开状态.多个结点通过总线进行通信需分时占用总线.因此总线也叫时分总线.总线的仲裁部件应按一定的优先规则对多个请求进行仲裁并将总线控制权交给其中一个请求.获得控制权的结点首先要测试目的结点的状态,建立连接关系,完成选址,然后进行通信.完成通信后,放弃控制权释放总线,以便其它结点使用.仲裁可是集中的也可是分布的,但功能是一致的. 总线具有简洁实用,设备量小的特点.N个结点的总线设备量为O(N).总线所能连接的部件或互连的结点数以及总线的工作频率与总线接口电路的速度、驱动能力、总线长度和负载大小都有关. 总线并不是一条简单的传输线,它应当是传输线和总线接口构成的系统.尽管接口一般都与被连接的设备做在一起,但分析总线时应把接口归在传输线一方.见图2.6总线上的结点度,网络直径和等分带宽均为1,N结点的设备量级为O(N). 交叉开关 交叉开关是动态互连网络中连接特性最好,设备量最大,但利用率较低跳网络.它和总线是动态网络中的两个极端.交叉开关如图2.7所示.N条垂直输入线与N条水平输出线的个交点由开关控制是否接通,且个交点接通与否是独立的.因此,N*N交叉开关的设备量级为侧O(),开关的状态数为.即使不包括选播在内的输入到输出的单值映射也有个互连状态,其中存在多到一的不被利用的状态.而真正有意义的互连是一对一映射,互连状志数为N!·因此交叉开关的使用效率很低,分别为和.一对一的映射一般不用个开关构成,而用N个N选一的选择开关构成.尽管这一网络设备量仍然很大,但由于其连接特性好,选址方便,控制简单,且能一次通过.所以某些对通信能力要求较高,又规模不大的系统仍愿选择这种网络互连. 网络的互连能力是指输入输出之间同时实现连接的最大数.而不是网络互能提供的连接数.典型的N*N交叉开关的度为2N,直径为1,等分带宽为N,设备量级为O(). 多级网络 多级网络由a*b交叉开关构成,其代价和性能介于总线和交叉开关之间.a*b开关多为2*2开关.如图2.8所示.2*2开关的连接状态中有意义的连接有四种:直送,交换,上播和下播.而多数多级网络只用直送和交换两种功能.四状态时有两位控制线,二状态时,有一位控制线. 一个N输入和N输出的多级网络,因表征端口号(或被连结点号)的二进制地址位数为n=,所以多级网络的级数为,每级2*2开关数为,因此多级网络的开关数为于,设备量量级为0(N ),网络延迟为单级开关延迟的n=倍,简称延迟为.见图2.9,图中各开关.单元的控制视互连模式的要求可以采用每个单元独立控制共n·,个信号,每级独立控制共n个信号,介于二者之间的部分级控制即第i(i=0, 1, … , n-1)级分配i+1个控制信号共个信号.合理选择控制信号的状态,便可实现输入到输出的相应连接.对于总线完成一次NN的通信至少需N次占用总线,延迟为O(N),而交叉开关是一次通过的,延迟为O(1),因此多级网络的设备和延迟均在总线与交叉开关之间,在性能和代价上作了折衷.总线、多级网络和交叉开关的延迟和设备的量级关系分别为O(N)>O()>O(1)和O(N)