（通信与信息系统专业论文）新型rdt互连网络结构及性能分析.pdf

摘要：互连网络作为影响并行计算机性能的一个主要因素，已发展成为计算机组织和系统结构学的一个独立方向。本文对构成互连网络的交换开关、影响网络性能的参数以及网络路由和反死锁问题作了比较深入的分析。为适应1 0 0 0 个结点左右的网络应用，本文研究了r d t( r e c u r s i v ed i a g o n a lt o r u s ) 网络体系的特性，提出了一种新的网络构造r d t ( 2 ，2 ，1 ) o ，并且在该结构上实现了新的路由算法和反死锁路由方式。该网络没有太多的高阶连接，这使得网络有更好的灵活性，同时在1 0 0 0 个结点左右的规模下，也不失去高效性，是比较理想的中等规模互连网络结构。本文还在新的路由算法基础上，对于r d t ( 2 ，2 ，d a n 络的理论特性作了全面的分析。并且利用杨愚鲁教授实验室自行构建的互连网络模拟软件对r d t ( 2 ，2 ，1 ) a 进行了模拟。关键词：互连网络、r d t ( 2 ，2 ，1 ) a 、路由算法、死锁、模拟a b s t r a c t ：b e i n gt h em a i nf a c t o ra f f e c t i n gt h ep e r f o r m a n c eo fp a r a l l e lc o m p u t e r ,i n t e r c o n n e c t i o nn e t w o r kh a sb e c o m ea ni n d e p e n d e n tr e s e a r c hd i r e c t i o no fc o m p u t e ra r c h i t e c t u r e t h i sp a p e rm a k e sa ni n d e p t hs t u d ya b o u tt h es w i t c h e s ，w h i c hc o n s t r u c tt h ef r a m e w o r ko fi n t e r c o n n e c t i o nn e t w o r k ，p a r a m e t e r si n f l u e n c i n gn e t w o r kp e r f o r m a n c ea n dd e a d l o c k f r e ep r o b l e mi no r d e r t ob eu s e di nt h ea p p l i c a t i o no f10 0 0 一n o d e s i z e dn e t w o r k ，t h i sp a p e ra l s os t u d i e st h ec h a r a c t e r so fr d ta n dp r o p o s e san e ws t r u c t u r eo fr d t - 一r d t ( 2 ，2 ，1 ) a an e wr o u t i n ga l g o r i t h ma n dd e a d l o c k f r e ea l g o r i t h ma r ed e v i s e dt o o t h en e t w o r ko n l yc o n t a i n sr a n k 一0 ，r a n k 一1a n dr a n k - 2l i n k so fr d t t h i sm a k e sn e t w o r kv e r yf l e x i b l ea n de f f i c i e n t ，s oi t i sag o o dc h o i c ef o rm e d i u m - s i z e dn e t w o r k b a s e do nt h en e wr o u t i n ga l g o r i t h mt h i sp a p e rm a k e sa no v e r a l la n a l y s i so ft h ec h a r a c t e r so fr d t ( 2 ，2 ，1 ) a ，a n ds i m u l a t er d t ( 2 ，2 ，1 ) ou s i n gt h es i m u l a t i o ns o f t w a r ew r i t t e nb yp r o f e s s o ry a n g sl a bk e y w o r d s ：i n t e r c o n n e c t i o nn e t w o r k ，r d t ( 2 ，2 ，1 ) o ，r o u t i n ga l g o r i t h m ，d e a d l o c k ，s i m u l a t i o n第六章结论4 8图表目录图i 通用的大规模并行计算机模型中互连网络的构造模型。图2 简单的链路级握手，图3 交换开关图4m e s h t o r u s 和树( t r e e ) 型结构，图5 超立方体网络( h y p e r e u b e ) 图6 卜阶和2 一阶带环网络的拓扑结构( n = 2 ) 图7r d t ( 2 ，4 。1 ) a ，图8r d t ( 2 ，4 ，1 ) b ，图9r d t ( 2 ，2 。1 ) o 图i 0r d t 各阶网向量，图1 1 从( 1 ，2 ) 到( 5 ，9 ) 发送消息的路由过程图1 2p r d t ( 2 ，2 ) 的路由特征图1 3 从( 0 ，0 ) 到( 5 ，2 ) 的路由过程，图1 4 网络路由死锁图1 5 交换开关的多个虚拟通道图1 6 采用虚拟通道打破死锁循环，图1 7p r d t ( 2 ，2 ) 的方向定义图1 8 互连网络模拟软件包界面图1 9 互连网络模拟软件包构成，图2 0 模拟传输方式，图2 1 虫蚀方式下p r d t ( 2 ，2 ) 和r d t ( 2 ，2 ，1 ) a 的模拟平均距离，图2 2 虫蚀方式下p r d t ( 2 ，2 ) 和r d t ( 2 ，2 ，1 ) a 的平均响应时间图2 38 x 8 规模下发片概率对平均吞吐量的影响图2 48 x 8 规模下发片概率对平均响应时间的影响图2 53 2 x 3 2 规模下发片概率对平均吞吐量的影响，0m圬埔孙加毖捣撕拍四弛弘盯弘心舵“钙，图2 63 2 x 3 2 规模下发片概率对平均响应时间的影响表1 典型网络的直径( 度) ，表2r d t ( 2 ，2 ，1 ) o 与r d t ( 2 ，4 ，1 ) o 直径( 平均距离)表3p r i ) t ( z ，2 ) 与i d t ( 2 ，2 ，1 ) o 的直径( 平均距离) 。表4 不同路由算法在p r d t ( 2 ，2 ) 上的直径( 平均距离) 表5 互连网络模拟软件参数说明表6 ( a ) 虫蚀传输控制方式系统参数表6 ( b ) 不同规模下p r d t ( 2 ，2 ) 的运行结果( 虫蚀方式) 表6 ( c ) 不同规模下r d t ( 2 ，2 ，1 ) q 的运行结果( 虫蚀方式) 表7 ( a ) 存储转发传输控制方式系统参数，。，表7 ( b ) 不同规模下p r d t ( 2 ，2 ) 的运行结果( 存储转发方式)表7 ( c 不同规模下r d t ( 2 ，2 ，1 ) o 的运行结果( 存储转发方式)表8 发片概率对r d t ( 2 z ，i ) 0 网络性能的影响( 规模：8 x 8 ) ，表9 发片概率对r d t ( 2 2 ，1 ) a 网络性能的影响( 规模：3 2 3 2 )旨；孔叭钒们甜船甜蛎第一章绪言第一章绪言计算机发展5 0 多年里，计算机的体系结构发生了巨大的变化。并行处理已经发展成为现代计算机的关键技术之一。传统上，科学与工程计算领域对并行计算能力的要求总是水无止境的。美国高性能计算和通信计划( h i g hp e r f o r m a n c ec o m p u t i n ga n dc o m m u n i c a t i o n ，h p c c ) 曾提出科学与工程计算领域里具有深远影响的一些重大挑战性课题，其中包括中长期天气预报、湍流分析、海洋环流建模、空气动力学、三维等离子体研究、药物分子结构设计、全球气候变化、结构生物学、图像理孵等诸多方面。所有这些课题全都县有极大的计算量，因而无一不对计算机的性能提出了非常高的要求。在商业领域，大型数据库系统得到了广泛的应用，网络信息服务业快速扩展，电子商务也在日益普及。这些新的领域对计算能力的需求虽然不及科学计算，但是它们也需要大规模的数据存储系统以及大规模的计算能力，并且天生就具有很好的并行性。因此，它们也从市场的角度对并行计算提出了新的要求。“并行计算机是由一组处理单元组成的，这组处理单元通过相互之间的通信与协作，以更快的速度共同完成一项大规模的计算任务。”这是并行计算机的经典定义。从中可以看出并行计算机的两个最主要的组成部分：计算结点和结点间的通信与协作机制。并行计算机体系结构的发展变化非常快，而这种变化主要体现在计算结点性能的提高以及结点间通信技术的改进两方面。在对多处理机体系结构的研究中，有关m p p ( m a s s i v e l yp a r a l l e lp r o c e s s o r s ) 或m p c s( m a s s i v e l yp a r a l l e lc o m p u t e r s ) 的研究正是热点。m p p 或m p c s 是一种由成百上千乃至上万个微处理器所组成的大规模并行处理系统。其体系结构发展特点是：1 结点机型选用通用高性能r 1 s c 微处理器芯片。2 一般均在结点上设计一个功能较强的通信处理机构，尽量减轻处理器的通信开销，有的甚至在结点上增设一个处理器作为通信处理机。3 采用分布式存储方式，使系统容易扩充。4 连接处理结点和存储系统的部件称为互连网络( t n t e r c o n n e c t i o nn e t w o r k ) ，其传输性能直接影响到整个系统的性能。多处理机体系结构中最关键的部分之一就是互连网络，它的性能对于并行计算机的整体性能有着重要的影响。互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统内部多个处理单元( p u ) , n 或多个功能部件之间的相互连接，其三大要素是结点间的互连拓扑( 包括连接通路) 、开关元件和控制方式。互连网络的拓扑第章绪言结构决定了各处理单元间的通信结构、处理单元和存储器以及i o 设备部分之间的数据通路，直接影响着整个系统的信息传输的速度、容错能力、路由控制算法的复杂性以及整个系统的工作效率，从而对整个并行计算机系统的性能有着重要的影响，在一定程度上决定着整个系统的性能价格比。互连网络在形式描述理论、拓扑结构、分析方法、性能模拟、设计和实现技术以及实际应用等各个方面都取得了许多研究成果，为并行计算机提供了坚实的结构基础，是计算机组织和系统结构学的重要研究方向。按照网络的开关元件和处理单元结点的连接方式不同，互连网络可以分为静态互连网络和动态互连网络。静态互连网络是并行计算机体系结构常用的网络结构，通常应用在中等规模以上的并行计算机系统中。网络拓扑结构、路由算法、以及通信控制方式等决定了网络平均响应时间，是互连网络性能差异的根本。随着并行计算机的发展，已经有不少的静态互连网络被提案，其中包括h y p e r c u b e 、f a tt r e e 、m e s h t o m s 、d eb r u i j n 、i l l i a c 等等。这些网络结构为并行计算机的应用提供了理论和实用的基础。r e c u r s i v ed i a g o n a lt o r u s ( 下文简称r d t ) 是一系列网络构造的集合，在这个广泛的集会里，对于不同的应用规模和实际应用问题，可以产生不同的具体的网络构造形式。已经有的结构有r d t ( 2 ，4 ，1 ) o 和r d t ( 2 ，4 ，1 ) d ，这两种构造的适用于超大规模( 1 0 0 0 0 个结点左右)的应用系统。目前在商用上，中等规模( 1 0 0 0 个结点左右) 的并行计算机日益受到重视，成为比较实用的规模，雨在这样的规模下，目前的网络结构仍不是很理想，本文就是针对这样的需求，基于r d t 网络结构提出一种新的构造r d t ( 2 ，2 ，1 ) o ，并且提出了适合该网络构造的新的路由算法数值判断路由算法和反死锁路由方式。通过理论分析，1 0 0 0 结点左右规模下，r d t ( 2 ，2 ，l y o 的两络直径、平均距离在可埋入m e s h 的网络结构中达到最小，同时，r d a ( 2 ，2 ，1 ) a 的结点度在目前制造工艺的能力下也是可以实现的。相对于向量路由算法，数值判断路由算法虽然在路由平均距离上有所损失，但是它的路由计算过程相对简化，综合考虑互连网络对速度的要求，这样的路由算法能够提供更好的性能。实际实现一个互连网络对于设备、资金和技术的要求都非常高，而分析网络性能又是应用网络的重要基础。因而对于网络性能的模拟成为互连网络研究的重要方面。本文通过应用杨愚鲁教授实验室自行设计的互连网络模拟软件对r d t ( 2 ，2 ，1 ) a 的实际构造进行了模拟，并且对不同规模下r d t ( 2 ，2 ，1 ) o 网络直径、平均距离等参数进行了详细的模拟分析，从结果看，这些参数都与理论分析能够很好的吻合。同时本文还对网络在不同发片概率下，不同规模网络的通信性能进行了模拟分析，取得的数据为网络的实用提供了支持。6 、第一章绪言本文第二章对互连网络的特征、性能和结构作了初步的介绍，并介绍了目前比较典型的静态互连网络。第三章中介绍了r d t 网络系列的定义、参数、基本概念以及典型网络结构。第四章按照r d t 的定义引入了新的网络结构r d t ( 2 ，2 ，1 ) q ，并且提出了新的路由算法和反死锁的算法，对该网络基于这样的算法下的性能作了理论分析。第五章引入了互连网络模拟软件并且利用该软件对r d t ( 2 ，2 ，1 ) o 进行了模拟。第六章是本文的总结。第二章互连网络2 1 互连网络概述第二章互连网络互连网络是一种由开关元件按照定的拓扑结构和控制方式构成的网络，用来实现计算机系统内部多个处理单元( p u ) 和或多个功能部件之间的相互连接。决定并行计算机性能很重要的一个因素是其互连网络的性能。在并行计算机中，互连网络的任务是将信息从源结点发送到目的结点，以支持实现并行计算模型的网络事务处理。原则上，完成这项任务的时间越小越好，同时应当允许大量这样的信息并发传递。互连网络的性能由它的拓扑结构、路由算法、控制方式、连接线路、开关元件等共同体现。并行计算机对响应时间的严格要求使得互连网络在网络结构、通信时延以及控制方式上都与普通的网络有着很大的差别。与常规网络相比，互连网络绝大多数在拓扑结构上是完全对称的，具有很整齐的数学特征，并与重要的并行算法所要使用的基本通信方式有密切联系，在结点闯物理链路以及解决系统中多个信息流争用通信资源的时候，也采用了适合于并行计算机要求的技术。图1通用的大规模并行计算机模型中互连网络的构造模型从网络结构上讲，互连网络是由连接、交换开关、网络接口构成的，图l 表示了一个m p c 系统。方框中是一个可扩展的互连网络结构，其中各个模块为带有交换开关的路由选择单元，其间的连线表示连接，而互连网络与处理单元的通信辅助模块之间的连接就是网络接口。雹第二章互连网络本章分析网络的特征因素、性能参数、网络组织结构，进而对网络进行分类，提出并行计算机系统对于互连网络总体的要求，最后对于目前一些具有代表性的网络进行简要的分析。2 2 互连网络的特征因素互连网络的特征因素决定它的性能，具体而言，一个互连网络具有下面特征因素：网络拓扑结构、路由算法、交换策略和流控制机制。互连网络的拓扑结构决定了各处理单元间的通信结构、处理单元和存储器以及i o 设备部分之间的数据通路，直接影响着整个系统的信息传输的速度、容错能力、路由控制算法的复杂性以及整个系统的工作效率，从而对整个并行计算机系统的性能有着重要的影响。路由算法、交换策略和流控制机制则是实现网络拓扑结构的这些效能的实际方法，所有网络拓扑结构的性能都需要通过这些策略来实现。以下对于各个特征因素分别阐述。2 2 1 网络拓扑结构网络拓扑结构是指网络图的连接结构。大多数并行计算机采用非常规则的网络拓扑结构。这种拓扑结构中还分成两类，直接网络和间接网络。在直接网络中，任何个处理结点连接到每一个交换单元上，而间接网络中，处理结点只连接到交换单元中的一个子集上。许多并行计算机采用了混合方式，因此这种界限就不明显了，于是需要加以区别的是处理单元和交换单元。处理单元产生或消除消息传递，而交换单元只对消息进行转发。2 2 2 路由算法路由算法决定了消息在网络上传递时按照何种路径走，是网络实际效能的实现方式。一般而言，路由算法将可能的路径集合限制到一个小的合法路径的集合。对于一个网络，各种不同的路由算法提供了不同的性能。通常，每个结点均有一张路由表，指明向其它结点发送消息可供选择的各条路径及其传输速度和消耗( 表中内容必要对可修改) 。实现路由算法的时候有以下三种常用的路由选择模式：第二章互连网络固定路f h ( f i x e dr o u t i n g ) ：预先指定自结点a 到结点b 的某条通讯路径，且该路径一经确定，在硬件不失效的情况下便不再改变。为了降低通讯费用，通常选择网络中a 至b 的最短路径。虚电路( v i r t u a lc i r c u i t ) ：自结点a 到结点b 的通讯路径只在某个时间段内固定，不同时间段可能经由不同路径。动态路e h ( d y n a m i cr o u t i n g ) ：自结点a 到结点b 的路径仅在消息传送过程中才。决定。这种动态确定路径的方法可能造成一批消息的各个分段可能选择不同的道路。结点a 可能决定把某消息发送给结点c ，c 又决定将它发送到d ，最终消息被送到结点b 。通常，一结点将从可行的通讯链路中选择当时使用最少的路径发送消息。上述三种模式各有利弊。固定路由既快速又简单，尤其是以维数为顺序的固定路由网络划分起来非常方便，预防死锁也非常容易。在大多数现有的多机系统的路由网络都采用了固定路由方式。但是，为了避免死锁的发生，尽管在源结点和目的结点之间有大量的路径可以选择，固定路由仅选择一条从源结点到目的结点的路径。这意味着由于不能灵活的使用物理通道，互连网络不能有效的使用其物理连接的密度。此外负载常常变动，也不宜采用固定路由模式，否则会导致路径忙闲不均。采用虚电路模式可以部分解决这一问题，而若采用动态模式，可以完全避免由于负载变动导致繁忙不均的现象。前两种模式能确保所发消息按发送次序到达目的地，而动态模式则不一定。采用动态路由模式时，消息到达顺序可能与发送顺序不一致。给每个消息附加上顺序号即可解决这一问题。2 2 3 交换策略交换策略决定了消息中的数据是如何通过路径的。有两种基本的交换策略：电路交换和包交换。电路交换：从源结点到目的结点的路径建立起来后，一直保持到消息完成在此路径上的传输。包交换：消息被分解成一系列更小的包，每个包包含了路由信息和次序信息以及数据。各个包是单独从源结点发送到目的结点，然后在目的结点按照序号重新组装。包交换的方式通常更好的利用了网络资源，因为只有当一个包在传输时，才占用网络连接和缓冲区。第二章互连嗣络2 2 4 流控制机制流控制机制决定了消息或消息的部分何时开始在它的路径上进行传送。当两条或两条以上的消息试图同时使用同一网络资源( 如一个通道) 时，尤其需要流控制。其中的一个消息应当被暂停，放在缓冲区里，或选择另一条路径，或简单的被丢弃。以上这几种选择都对交换单元的设计有特殊的要求，同时对通信子系统的其他方面有影响。所有的并行机都提供链路级的流控制策略，如图2 就是一个简单的链路级握手策略，当源结点有个片( f l i t ) 要传输，就发出它的请求，而目标点在准备好接收片的时候才响应它的请求，然后源点才可以传输片。图2 简单的链路级握手链路级的流控制策略并不能解决所有的问题，这是因为如果拥塞在某处持续的话，缓冲区将会被塞满，流控制会一直从远端回馈到发送端，给发端带来压力，这样的压力称作回压，比如“热点问题”的情况下 ”。这就要求网络能够提供端到端的流控制策略。在虚跨步( c u t - t h r o u g h ) 网络中，条简单的消息( 或者是些消息) 就会占用一整条源点到目的点的通道，如果目的点的网络接口n i ( n e t w o r ki n t e r f a c e ) 还没有准备好接收消息，那么把消息暂存在源结点会比阻塞在网络中要好一些。采用n i 到n i 间基于许可证的流控制机制就是这样的方式 8 1 。薰二章互连同缛2 3 互连网络的性能参数下面定义几个下面将要用到的估算互连网络计算复杂性、通信效率和网络价格的重要参数。互连网络中的结点数称为互连网络的规模，它表示该互连网络所能连接的功自部件的多少：与结点相连的边( 链路或通道) 数称为结点度，用d 表示。结点度反映了一个结点所需要的y o 端口数，也反映了结点的价格。为了降低价格，应尽可能使它小，而为了构造可扩展系统，使孝句件能够模块化，尽量要求结点度保持恒定：互连网终中两个结点根连的最少边数称为距离：互连网络中任意两个结点之间的距离的最大值称为网络的直径，它是说明互连网络通信性能的一个指标。从通信的观点来看，互连网络的直径应当尽可能小；假若从网络的任 可结点看其拓扑结构都是一样的话，我们就穆此网络为对称网络。对称甄终比较容易实现，编程也比较容易。网络的路由距离指的是在一对结点之间的路由所使用的连接数目。平均距离指的是所有结点对的路由距离的平均值；而平均距离也可以有随机的对结点之间的距离。在直接网络中，对于每一组交抉单元来说，都要提洪路由，两在阑接鼹络牛，只需要提供处理结点之间的路由。2 4 网络组织结构：互连网络作为并行计算机的连接网络，由三种基本的组件构成：连接( 1 i n k ) ，交换开关( s w t i c h ) 和网络接口( n e t w o r ki n t e r f a c e s ) 构成。选择合适的网络组件，可以构成适合于不同要求的网络，但是对于这三种组件，它们的性能与成本对于网络设计经常是无法兼顾的，需要二者选其。2 4 1 连接连接可以是两端带有连接装置的电缆或者是其它的电子线路或光纤，它的每一端连接到交换开关或两络接口端。它允许模拟信号觚一端传送到另一端，从中获得数字信息流。实际上，各种连接在电子和物理特性上有很大的差异，但它们的逻辑特性可以被描述成三个独立的方面：连接长度，带宽和时钟。2第二章互连唰络2 ，4 2 交换开关互连网络是由连接和交换开关( s w i t c h ) 组成，而这些连接应提供一种将消息从源结点发送到目的结点的路由方法。图3 交换开关交换开关是由一系列的输入端口和输出端口构成。一个内部的交换单元( c r o s s b a r ) 把所有的输入端口和输出端口连接起来，图3 为一个典型的交换开关。每个输出端l - 1 都有一个传输器用来驱动连接，每个接牧端口都有一个相应的接收器。大多数的设计中，输入端口都有个同步装置用以把输入的数据与交换开关的本地时钟同步。这在本质上讲是一个f i f o 的形式，所以很自然的需要在每个输入端口提供一定数量的缓存。控制逻辑的复杂性依赖于路由算法和调度算法( s c h e d u l i n g ) 的复杂性。2 4 3 网络接口网络接口( n e t w o r k i n t e r f a c e s ) 包含一个或者多个输入输出端口，它的功能是将数据打包，并且构建路由以及控制信息。它的运作与交换开关结点大不相同，并且可能是经过特殊的连接链路。与交换开关相比，它具有实质性的输入和输出缓存。它可以完成端到端的错误检测以及流控制功能。很明显，它的耗费主要受它的存储能力、处理的复杂性，以及端口的数目的影响。第二举互连髓络2 5 互连网络分类网络拓扑结构是互连网络的三大要素之一，而且是互连网络合理布局的关键因素。迄今为止，设计出的互连网络已经很多，也有各种分类方法，但从并行处理和分布式计算机系统的角度出发，以网络的开关元件和处理单元结点的连接方式来分更为合理，这样，可将互连网络分为静态和动态两大类。静态互连网络( s t a t i ci n t e r c o r m e c f i o n n e t w o r k ) 是指在各结点之间有专用的连接通路，而且在运行中不能改变的互连网络。在静态互连网络中，每一个开关元件固定地与一个结点相连，建立该结点与邻近结点之间的被动连接通路，直接实现两结点处理机之间的通信。这种网络的开关元件都分散设置在每个结点内部，从外面看是看不到开关元件的。因此，网络中结点问的连线是固定连接的，且是无源的，其连接通路出就被称为被动( p a s s i v e ) 连接通路。它能够直接实现两个结点之间的通信，而非相邻结点之间的通信必须经过某些中间结点的协助才能完成。静态互连网络经常用在一个集中式系统中子系统之间的固定连接或者分布式系统的多个计算结点。动态互连网络( d y n a m i ci n t e r c o n n e c t i o nn e t w o r k ) 则是指设置有源开关，可以根据需要借助控制信号对连接通路加以重新组合，实现所要求的通信模式，相邻各级之间具有固定的级间连接。利用动态设置开关的状态来实现输入与输出问的所需连接的建立。动态互连网络中，其输入输出两侧的开关元件与结点相连。在控制信号的作用下，通过网络所有开关的工作，建立结点间主动可控的连接通路，使系统具有重构能力，这种开关网络常以一个集中的独立部件出现，网络两侧结点间的连接可通过有源开关的状态来动态地改变。因此其连接通路被称为主动( a c t i v e ) 连接通路。在具体到设计并行计算机系统体系结构时，根据各个系统具有的不同的目的和规模来选择不同性质的互连网络。对于大规模的并行计算机系统，一般使用静态互连网络，简称为静态网络；而对于中小规模的，比如十几个到几十个处理单元的并行计算机系统，考虑到这时对内存访问的均性对系统具有高性能比较有利，往往会采用动态互连网络，简称为动态网络。2 6m p c s 对互连网络的要求m p c s 的互连网络于普通的网络有着很大的差异，总结m p c s 的应用需求，它对互连网络一塑三垦至整鬯丝有如下的要求：1 由于在这样的网络中，结点数量比较多，所以直径必须小，通常应该小于h y p e r c u b e的直径。2 度，考虑到芯片工艺的要求，通常度必须在8 以内。而且对于一个可扩展的系统而言，度在整个系统中应是一个常数。3 对于科学计算而言，现在大多数的软件是基于m e s h t o r u s 这样的结构的，所以，网络还应该能够包含m e s h t o r u s 结构。4 路由算法简单。5 具有一定的容错能力。6 能够实现广播多播的功能。7 尽量避免复杂的连线。2 7 现有互连网络简介并行机最理想的网络是全连接结构( c o m p l e t ec o n n e c t i o n ) ，但是网络规模的不断扩大，这样的结构结点度就会相应的线性增加，这对于大规模的应用网络是不现实的，因此，经过几十年的发展，产生过许多实用的和理论的互连网络模型如：d eb r u i j n 【9 】，f a tt r e e h y p e r c u b e ，m e s h t o r u s 等等。在讨论新的网络之前，先对过去典型的网络做一回顾。2 7 1 树图4m e s h t o r u s 和树( t r e e ) 型结构树( t r e e ) 的结构如上图4 右，通常一些专门为a i 应用设计的并行机器采用这样的第二章互连两绍结构。然而这样的结构同样存在以下的缺陷：1 通信流量集中在根结点处。2 除了叶子结点外的其它结点的失效会扩散到整个网络中。2 7 2 超立方体网络超立方体网络( h y p e r c u b e ) 是种多维网格型结构的网络。在n 维的网络中，用n位二进制数编码n = 2 “个结点，将地址码只差位的各对结点一一连接，构成超立方体网络。它的直径比较小1 0 9 2 n ，路由算法简单，可以根据源结点和目标结点的二进制地址异或所得结果进行路由，大多数第一代并行机多采用这样的网络构成。它的缺点在于结点度比较大。无法构成大规模的实用网络。其拓扑结构如图5 。2 7 3m e s h t o r u s图5 超立方体网络( h y p e r c u b e )在最近出现的并行机中，如曙光2 0 0 0 “，多采用2 一维网格型网络( m e s h ) 。虽然它的直径比较大，但是对于每个结点来说，它的结点度比较小，只有4 或者6 ，远小于超立方体结构的l o g 。n 。其结构如上图4 左。网格网络可p 4 带, i 造比较大规模的网络，同时，网格网络非常适合大多数的科学计算包括分布参数系统模拟，图象处理和结构分析等。第三章r d 7 网络介绍3 1r d t 说明第三章r d t 网络介绍r e c u r s i v ed i a g o n a lt o r u s “1 网( 下文简称r d t ) 是一种非常容易映射到网格的网络，它具有使用递归方法构造的网格( t o r u s ) 结构，对于结点数在1 0 0 0 到1 0 0 0 0 之间时，r d t 的网络直径和度都比超立方体小。在目本七所大学联合研制的j u m p 一1 机群中，已经采用了r d t 网络的其中一种构造r d t ( 2 ，4 ，1 ) o 。图6 卜阶和z 一阶带环网络的拓扑结构( n = 2 )3 2 基本带环网格网首先一个二维的正方环带网格结构定义为r d t 的基本结构，称做基本带环( b a s et o r u s )它可以表示成为如下的二维数组：( o ，o ) ( 1 ，0 ) ( 2 ，o ) ( n l ，0 ) 1 ) ( 1 ，1 ) ( 2 ，1 ) ( n i 。1 )( o ，n _ 1 ) ( 1 ，n - i ) ( 2 ，n 一1 ) ( 卜l ，n - i )第三章r d t 网络介绍其中n = ( n ，k 都是自然数) 。在结点( x ，y ) 与相邻的四个结点( m o d ( 爿l ，n ) ，y ) 和( 丑m o d ( 世1 ，n ) ) 之间形成了四个连接，构成个带环网格。基本带环网格网又称做o 一阶带环网格网( r a n k 一0t o r u s ) ，下文将简记为o 一阶网。其中0 称做阶数。3 3 上层带环网格网在基本带环网格网上增加对角线方向的旁路是一种减少网络直径的高效率方法。在结点( x ，y ) 和结点( x n ，y n ) 增加四个连接，这样新增加的连接形成一个新的带环网格网络。新的带环网格网络与原来的带环网格网络相差4 5 度角。这里，这个新的带环网格网络被称做卜阶带环网格网络。以此类推，可以在1 一阶带环网格网络上形成2 一阶带环网格网络。也就是说，在x 一阶上，按照上述连接方式可以形成x + 卜阶带环网格网络。r d t 就是按照这样的递归方式形成的。对于r d t 网络，可以在o 一阶网之上形成无穷阶的其它阶网络。这里将在o 一阶网之上形成的各种带环网格网络统称为“上层带环网格网络”，下文简记为上层网。图6 中即为当n = 2 时形成的卜阶和2 一阶带环网络的拓扑结构。3 4r d t 的参数构成一类r d t 网络，需要三个参数，它们是：n ，r ，m 。下面对三个因素分别说明。( 1 ) n ：步长。它决定了上层网的单位矢量的长度。( 2 ) r ：最大阶数( r a n k ) 。该参数受到o 一阶网的大小的影响，因为只有o 一阶网的尺寸足够大的时候，才能形成真正意义上的上层网。例如，在一个具有1 2 8 1 2 8 或者2 5 6 2 5 6个结点上才能形成一个不需要经过带环网格结构的4 一阶网。( 3 ) m ：指每个结点上形成m 层上层网。该参数决定于当今的微电子技术水平。按照r d t 的定义我们可以得到结点的度和m 的关系，即：d e g r e e = 4 ( m + 1 ) 就目前而言，当m = 1 时，d e g r e e = 4 ( m + 1 ) = 8 是可以实现的。由此可见，实现r d t ( n ，r ，m ) 网络，其中r n 这个参数实际上是基本不可以变化的，我们可以通过选择合适的n ，r 的数值，构成新的网络，来适应特定的需求。3 5 完全r d t每个结点上都有所有可能的上层网连接，这样的r d t 网络称做完全r d t ( n ，r ) ，下文第三章r d t 网络介绍简记为p r d t 。其中r 为最大阶数。这样的网络在实际的构造中是无法实现的，它的结点度相对于制造工艺而言太大( 如前文，d e g r e e = 4 x ( r + 1 ) ) 。但是p r d t 是建立m e s s a g er o u t i n g 算法和研究其他类型r d t 网络群的理论基础。3 6 阶的分配改变r d t 的参数( n 或者m ) 可以得到一系列针对不同应用的网络结构，它们的性质各不相同。为了易于继承队前的在2 叉树或者是c u b e 上的算法，参数n 一般设置为2 。而对于参数m ，如果r d t 的参数m 很大，那就意味着要有很多的硬件连接存在。因为每个上层的t o r u s都表示每个结点需要增加4 条连接。考虑一个有1 0 0 0 0 个结点左右这样规模的网络( 例如：1 2 8 x1 2 8 ，2 5 6 2 5 6 个结点) ，我们把m 设置为1 ( 这意味着度= 8 ) ，最大的上层t o r i 为4 ，从而得到r d t ( 2 ，4 ，1 )这样的结构。对于r d t ( 2 ，4 ，1 ) 网络，对于上层的阶r a n k 的不同排布可以的到不同的网络结构，为了表述清楚，需要定义上层阶的排布方式。3 7r d t ( 2 ，4 ，1 ) a 与r d t ( 2 ，4 ，1 ) 1 3对于r d t ( 2 ，4 ，1 ) ，按照r d t 阶的表示方式，具有如下带环排布方式的r d t ( 2 ，4 ，1 ) 称作r d t ( 2 ，4 ，1 ) a ：r a n k - 1 ：r a n k - 2 ：r a n k - 3 ：o1r a n k - 4 ：( ( 0 ，1 ) ( 4 ，+ ) ( 4 ，+ ) ( + ，+ ) ) ，( ( 2 ，0 ) ( + ，+ ) ( + ，+ ) ( + ，+ )其拓扑结构如图7 所示。哟似时，一 “j 的 托蚨曲 他第三章r d t 嘲络介绍图7r d t ( 2 ，4 ，1 ) a同样，具有如下带环排布方式的r d t ( 2 ，4 ，1 ) 网络称作r d t ( 2 ，4 ，1 ) 1 3r a n k - l ：( 1 ，o ) ，( 2 ，1 ) ，( o ，1 )r a n k - 2 ：( ( 0 ，o ) ( + ，+ ) ) ，( ( 3 ，1 ) ( + ，+ ) ) ，( ( 1 ，1 ) ( 4 ，+ ) )r a n k - 3 ：( 3 ，o ) ( + ，4 ) ( 4 ，4 ) ( + ，+ )r a n k - 4 ：( 2 ，o ) ( + ，+ ) ( + ，+ ) ( + ，+ )其拓扑结构如图8 所示。对于r d t ( 2 ，4 ，1 ) o 每个结点可以连接到任何一层的网格，这样就会比较容易的传输到网第三章r d t 网络介绍络中的任一个结点，在这样的网络中，至多需要一步额外的传输，就可以在任意阶上根据路由需要进行消息传输。因此，r d t ( 2 ，4 ，1 ) g 适合于消息传输在全网络均衡的应用中，也就是说，消息的传输在附近点发生的可能与在远处发生的可能是相近的。而对于r d t ( 2 ，4 ，1 ) b 来说，它更适合小范围或局域范围发生的信息传输远多于远程结点的信息传输的应用中。也就是说，对于一个结点，它最可能发生的信息交换是与和它相近的点之间进行的、，在这样的应用中，r d t ( 2 ，4 ，1 ) a 结构中平均连接的特征就会显得不太适合了。而r d t ( 2 ，4 ，1 ) b 增加了卜阶和2 一阶的连接数量，同时减少了3 一阶和4 一阶的连接数量，这就为局部的消息传递提供了更大的灵活性。第四章r d t 的新结构r d t ( 2 ，2 - 1 ) o第四章r d t 的新结构r d t ( 2 ，2 ，1 ) a在m p c ( m a s s i v e l yp a r a l l e lc o m p u t e r s ) 的应用中，r d t ( 2 ，4 ，1 ) o 和r d t ( 2 ，4 ，1 ) 0适合于规模在1 0 0 0 0 个结点左右的网络中。近来，在许多的应用场合，大约1 0 0 0 个结点的网络越来越受到重视，也处于广泛应用之中。对于这样的应用场合，两种r d t ( 2 ，4 ，1 ) 的构造都不太适合。在这样的条件下，提出一种适合于1 0 0 0 个结点左右的规模，同时又能非常好的埋入m e s h t o r u s 结构的网络就显得极为重要了。r d t ( 2 ，2 ，1 ) a 就是这样的网络。它只有r a n k - 1 连接和r a n k - 2 连接，这样就使得网络相对简化了许多，同时，r d t ( 2 ，2 ，1 ) a仍然可以使用r d t 的路由算法和漂移算法。与r d t ( 2 ，4 ，1 ) o 的两种形态相比，它的构造简单，适用于1 0 0 0 个结点的网络。4 1r d t ( 2 ，2 ，i ) a 的定义按照r d t ( n ，r ，m ) 定义方式，取m = 2 ，r = 2 ，n = i ，并且按照如下阶的分配的r d t 网络称作r d t ( 2 ，2 ，i ) 0 ；r a a k - 1 ：( o ，o ) ，( 1 ，1 ) ，( 2 ，o ) ，( 3 ，i )r a n k - 2 ：( 1 jo ) 代砷，( 0 ，i ) ( 鼍斗。，( 2 ，1 ) ( 屯岣，( 3 ，0 ) 的r d t ( 2 ，2 ，1 ) a ，r d t ( 2 ，4 ，1 ) a ，以及r d t ( 2 ，4 ，1 ) 1 3 的每个结点都有8 个连接，其中4个是用于r a n k 一0 的连接。r d t ( 2 ，4 ，1 ) o 和r d t ( 2 ，4 ，1 ) 1 3 有四个上层带环网，而r d t ( 2 ，2 ，1 ) o 只有2 个上层带环网。从r d t 的阶的分配方式来看，r d t ( 2 ，2 ，1 ) o 的构造相对于这两个网络要简单许多。这种构造上的简单，就会导致路由算法也会变简单。在特定的网第四章r d t 的新结构r u t ( 2 ，2 ，i ) o络尺寸规模上，r d t ( 2 ，2 ，1 ) o 的性能会非常优秀。4 2 向量路由算法r d t 上通用的路由算法是向量路由算法，任何的r d t 网络构造，都可以使用向量路由算法再加上合适的漂移算法就可以构成该网络构造下完整的路由算法。向量路由算法是将消息的路由用一组向量来表示。而这组向量将分别对应着不同阶的网。在带环网格结构上，一个从源结点指向目标结点的向量可以表示成：a = 口xo+byo其中x 。和y 。是o 一阶网上的单位向量。而路由算法的目的就是将各层网上的单位向量组合起来，来表示向量a ，如图1 0 ( a ) 。f 叠)；矿7瀛矿 s n k - 2 ：( r s n k - i xr _ a k - or m n “驴氏。忑f b )图1 0 ( a ) 向量a( b ) r d t 各阶网的单位向量的方向因此我们首先需要定义一下各阶网的单位向量( 方向+ 大小) 。根据前文所述r d t 的形成方法，可以看出随着阶数的递增，各阶网的单位向量方向按顺时针方向旋转4 5 度，如图1 0( b ) 。具体可由如下公式导出：设i 一阶网的单位向量为x ，y 。，那么( i + i ) 一阶网的单位向量为：第四章r d t 的新结构r d t ( z ，2 ，1 ) 。因此，向量a 还可以表示成j = 麻o + 够o = 职1 + 痧1 + 雳o + 锣。式1式2其中，a = n g n f 十b = n g 十n f 十膏按照递归的方法，我们还可以利用m 一阶网上的矢量来表示( m - i ) 一阶网和( m 1 ) 一阶网以下的矢量。于是我们得到如下公式：a = k + k y 。+ k 一，一l + ，。y 叫+ + _ + m + k 嘞+ y o 对?从此式看出，在p r d t 上的理论最佳路由就是当：+ k + 嚷+ ，+ 勺。+ + 忽。+ + 氏+ 为最小时所采用的路由方法。由于该式不易求解，因此在实际过程中，我们采用了下面的a l g o r i t h ma 算法，该算法采用的是“残余矢量”的思想。若想发挥r d t 的结构优势，就要在消息的路由过程中尽量更多的使用上层网的连接，因为每走一步上层网，往往等于n 步低层网的连接。对于卜阶网和0 一阶网，根据式2 ，可以得出g 和f 的最大整型值，如下：d + 扫g 。1 丁4 一df 。2 n式4结果4 舍5 入。也就是说，路由中，取g 和f 的最大值，将减少o 一阶网的使用，提高路由效率。按照同样的方法，可以将g x 。+ f y 用x 2 y ：，x ，和y i 来表示，其中x ：，y 。取最大值。最终，我们可以得到用各阶网的向量的组合来表示的r d t 路由结果。具体算法可以用c 语言来描述，如下所示：a l g o r i t h ma ：f o rc r a n k = o ；r a n k 5 ) l ( ( a = = 5 ) ( b = = 2 ) ) )ff = f 一1 ：a = a 一8 ：)d 在源点的西商都需要觌断翔龋其它类似的情况，g l = d i v 4r o u n d ( a + b ) ：f l = d i v 4 一r o u n d 卜峙b 、：腿i v 4r o u n d0 表示赊以4 并且四舍五入，a = a 一2 $ ( g l f 1 ) ：b = b 一2 十( g l + f 1 ) ：v e cvecvecveco r0 ro ro rx2g ：y = f ：x = g ly = f