（计算机软件与理论专业论文）新型动态互连网络的研究.pdf

r e s e a r c h o n n o v e l mu l t i s t a g e i n t e r c o n n e c t i o n ne t wo r k s g u o f e n g h o u d e p a rt m e n t o f c o m p u t e r s c ie n c e a n d t e c h n o lo g y n a n k a i u n iv e r s it y , t ia n j in 3 0 0 0 7 1 , p . r . c h i n a ab s t r a c t t h e d e v e l o p m e n t o f v l s i t e c h n i q u e a n d t h e d e m a n d f r o m m a n y a p p l i c a t i o n f i e l d s n e c e s s i t a t e t h e n e w b r e a k t h r o u g h i n mu l t i s t a g e i n t e r c o n n e c t i o n n e t w o r k s ( m i n s ) u s e d i n p a r a l l e l c o m p u t e r s . i n o r d e r t o d o r e s e a r c h o n t h e n e w t y p e s o f mi n s , t h i s p a p e r h a s a n a l y z e d t h e f e a t u r e s o f t h e m o d e r n a n d c o m m o n l y u s e d m i n s fr o m t h e a s p e c t o f a p p l i c a t i o n o f p a r a l l e l c o m p u t e r s , d e s c r i b e d t h e i r i d e as, s t r u c t u r e s , r o u t i n g c o n t r o l a n d c o n fl i c t s o lv i n g m e t h o d s , e x p l a i n e d t h e d i v i s i o n m e t h o d o f m i n s a n d e x p o u n d e d t h e r e l e v a n t n e w r e s e a r c h r e s u l t s . a c c o r d i n g t o t h e g r a p h t h e o r y , i t h a s i n t r o d u c e d t h e d e s i g n m e t h o d s o f mi n s . t h i s p a p e r p u t s f o r w a r d t h e i d e a o f a n e w f a m i l y o f mi n s u s i n g 8 x 8 s w it c h e s w h i c h i s c a l l e d s u p e r r e c u r s i v e b as e l i n e i n t e r c o n n e c t i o n n e t w o r k ( s r b ) , e x p o u n d s i t s n e t w o r k t o p o l o g i c a l p r o p e rt i e s a n d r o u t i n g t e c h n i q u e s , m a k e s p e r f o r m a n c e a n a l y s i s a n d c o m p a r i s o n s i n t h i s n e t w o r k , a n d p r o v e s t h a t i t h a s s u p e r i o r q u a l i t i e s i n n e t w o r k p a s s r a t e s , b a n d w i d t h s a n d p e r f o r m a n c e / c o s t r a t i o s , e t c . t h i s p a p e r s t a t e s t h a t s r b i s a f a m i l y o f m i n s s i m p l e in r o u t i n g , s u p e r i o r i n p e r f o r m a n c e / c o s t r a t i o , a n d e a s y i n e x p a n d in g . t h i s p a p e r a l s o d e s c r i b e s t h e f a u l t - t o l e r a n c e m e t h o d s u s e d i n s r b n e t w o r k a n d p r e s e n t s t h e e x t r a s t a g e s u p e r r e c u r s i v e b a s e l i n e i n t e r c o n n e c t i o n n e t w o r k ( e s s r b ) , a f a u l t - t o l e r a n t n e t wo r k d e r i v e d f r o m t h e s r b n e t wo r k . t h e e s s r b n e t wo r k c o n s i s t s o f a s r b n e t w o r k w it h o n e a d d i t i o n a l s t a g e a t t h e i n p u t a n d h a r d w a r e t o a l l o w t h e b y p a s s , w h e n d e s i r e d , o f t h e e x t r a s t a g e o r t h e o u t p u t s t a g e . i t h a s a r e l a t i v e l y l o w i n c r e m e n t a l c o s t o v e r t h e s r b n e t w o r k . t h e e s s r b n e t w o r k i s s i n g l e - f a u l t t o l e r a n t a n d r o b u s t i n t h e p r e s e n c e o f m u l t i p l e f a u l t s . t h e r e f o r e , t h e e s s r b n e t w o r k i s a n a n s w e r t o t h e n e e d f o r r e l i a b l e c o m m u n i c a t i o n s i n p a r a l l e l / d i s t r i b u t e d s y s t e m s k e y w o r d s : i n t e r c o n n e c t i o n n e t w o r k , t o p o lo g y , r o u t i n g , p e r f o r m a n c e / c o s t r a t i o , f a u l t - t o l e r a n c e 第一章引言 v - 音己i省 二 刁 占宇 二j .刁 科学计算与大型数据处理广泛应用于重要的研究、设计和生产，如气象预 报、石油勘探、核电站设计、卫星遥感信息处理、飞机船舶设计、航空航天飞 行控制等。特别是大型实时处理系统，对高性能计算的要求更为突出。 计算机技术发展过程中两个决定性因素是制造工艺和体系结构。随着现代 科技的发展和集成技术日益提高的集成电路的出现，计算机的速度和性能不断 提高，但由于电子信号的最大传输速度的限制，仅靠提高电子部件的速度来改 善计算机性能已很难满足应用要求; 从体系结构方面来看， 由于沿用的传统冯 诺 依曼式结构的自身局限性，存储器读/ 写的瓶颈始终无法根除，人们认识到使用 单一c p u的办法不能根本解决问题，希望能摆脱冯氏结构的束缚。发展以高速 处理为主要目的的并行计算机系统成为提高计算机性能最现实的道路川 。 并行处理是一种有效的强调开发计算过程中并行事件的信息处理方式。而 提高计算机结构并行性的两种主要方法是空间重复和时间重复 ( 流水线技术)， 但它们都存在缺点，空间重复技术的处理机间 和处理机与内 存之间的通信成为 瓶颈;虽然流水线没有空间重复技术的通信问 题，但其并行性是很有限的。 五十年代以来，人们先后采用了先行控制技术、流水线技术、增加功能部 件甚至多机技术、存储寻址和管理能力的扩充、各种互连网络的拓扑结构等一 系列并行处理技术，来提高计算机处理速度，增强系统功能。多处理机体系结 构是计算机体系结构发展中的一个重要领域，已成为并行计算机发展中人们最 关注的部分。 在 对 多 处 理 机 体 系 结 构的 研 究中 ， 有 关m p p ( m a s s iv e ly p a r a ll e l p r o c e s s o r s ) 或m p c s ( m a s s iv e ly p a r a l le l c o m p u t e r s ) 的 研究 正 是 热点 z 1 m p p 或m p c s 是一种由 成百 上千乃至上万个微处理器所组成的大规模并行 处理系统13 1 。其体系结构发展特点是: 1结点机型选用通用高 性能r i s c微处理器芯片， 它具有v l s i 硅片、坤 化稼技术、高密度组装和光技术。 2 . 一般均在结点上设计一个功能较强的通信处理机构，尽量减轻处理器的 通信开销，有的甚至在结点上增设一个处理器作为通信处理机。 3 . 采用分布式存储方式， 使系统容易扩充。 而对于分布式存储系统的访问， m p c系统上广泛使用的是虚拟共享存储技术。即将物理分散的各个处理机使用 的局部存储器，在逻辑上加以统一编址，形成一个统一的虚拟地址空间来实现 存储器的共享。每个处理机可以访问全局存储器的任一位置，用户可以把它当 成全局共享存储系统。 第一章引言 4 连接处理结点和存储系统的部件称为互连网络 ( i n t e r c o n n e c t i o n n e t w o r k )， 其传输性能直接影响到整个系统的性能。 对互连网络的研究和实现， 需要有关对计算处理结点的硬件和互连网络的硬件的技术支持。 多处理机体系结构中最关键的部分之一就是互连网络4 1 。互连网络是一种 由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统 内部多个处理单元 ( p u)和/ 或多个功能部件之间的相互连接，其三大要素是结 点间的互连拓扑 ( 包括连接通路)、开关元件和控制方式。互连网络的拓扑结 构决定了各处理单元间的通信结构、处理单元和存储器以及 i / o设备部分之间 的数据通路，直接影响着整个系统的信息传输的速度、容错能力、寻径控制算 法的复杂性以及整个系统的工作效率，从而对整个并行计算机系统的性能有着 重要的影响，在一定程度上决定着整个系统的性能价格比。 互连网络是多处理机系统一个很重要的组成部分，互连网络在形式描述理 论、拓扑结构、分析方法、性能模拟、设计和实现技术以及实际应用等各个方 面都取得了许多研究成果，为并行计算机提供了坚实的结构基础，现在己发展 成为计算机组织和系统结构学的一个独立方向5 ,6 1 动态互连网络 ( d y n a m i c i n t e r c o n n e c t i o n n e t w o r k ) 是并行计算机体系结构 中常用的一种互连网络 1.8 。在设计中小规模的并行计算机系统 ( 比如十几个到 几十个处理单元)的体系结构时，考虑这时对内 存访问的均一性对系统具有高 j胜能的影响比较大，多采用动态互连网络，指设置有源开关，可根据需要借助 控制信号对连接通路加以重新组合，实现所要求的通信模式，相邻各级之间具 有固定的级间连接，利用动态设置开关的状态来实现输入与输出间所需连接的 建立。 互连网络已经成为现代并行处理系统的核心组成部分，伴随着 v l s i技术 的飞速发展，许多动态互连网络已经被提案，同时也有许多与之相应的寻径控 制算法被发表;而且， v l s i 技术发展到今天的水平，使得提出集成度更高、性 能更好的动态互连网络成为可能。集成技术的发展使得将上千个处理单元互连 在一起成为可能，这样就可以从理论、分析、设计、控制以及实现等角度去研 究动态互连网络。 动态互连网络研究的出发点和目 标是设计拓扑结构简单，满足可扩展性， 具有较好耐故障性，寻径控制不太复杂的动态互连网络。目前主要的动态互连 网 络有: o m e g a 网 络18 1 , 9 r 网络 i , g e n e r a l i z e d c u b e 网 络 0 i , b a s e l i n e 网 络1 ， 、 d e l t a 网 络1 1 2 1和b a n y a n 网 络 1 3 ,14 ,1 5 等。 现有的 主 要研究工作主要集中 在动态互 连 网络的拓扑结构、寻径控制和耐故障性方面。随着 v l s i技术的发展，有待进 一步提出性能更好的动态互连网络，改进解决方案，以推动动态互连网络研究 与 应用的发展。 第 一章引言 v l s i 技术的发展和各应用领域的需求使得并行计算机应用的动态互连网 络需要有新的突破。为了进行新型动态互连网络的研究，本论文在第二章和第 三章从并行计算机应用角度分析了 现代常用的动态互连网络的特征， 对其思想、 结构、寻径控制和冲突解决方法进行了描述，说明了动态互连网络的划分方法， 并综述了相关的最新研究成果。根据图模型理论，介绍了动态互连网络的设计 方法。 在本论文第四章，在当前 v l s i 技术发展水平的基础上，提出了一种新型 的使用 8 x8交叉开关的超级递归基准互连网络( s u p e r r e c u r s i v e b a s e l i n e i n t e r c o n n e c t i o n n e t w o r k , s r b ) i , . s r b具有简单的寻径控制方法，能够实现多 种置换并具有优良的网络规模可扩展性。更进一步对它进行子性能分析和比 较， 证明s r b具有较高的频带和网络通过率，比现有的d e l t a网络、基准网络和交 叉开关网络等具有更优良的性能价格比;并且 s r b适应于当前 v l s i 技术的发 展水平，具有良 好的应用前景。s r b在网络通过率、频带和性能价格比等方面 具有优良 性质，是一种寻径简单、性能价格比优良 且易于升级的动态互连网络。 本论文第五章研究了 s r b网络中应用的耐故障方法，提出了一种具有耐 故障 特性的附 加级超级递归 基准互 连网 络 ( e x t r a s t a g e s u p e r r e c u r s i v e b a s e l i n e i n t e r c o n n e c t i o n n e t w o r k , e s s r b ) ( 1 . e s s r b网络由 一个s r b网络上增加了 一个 附加级构成，在输入端增加了一个开关级，当需要时，可以控制硬件使得附加 级或输出级被旁路。可以证明，使用这种方法，当网络中任意一处发生故障时， 连接请求仍然可以成功地通过网络到达输出端。e s s r b只在 s r b 网络上增加 了相对较少的硬件代价，附加级使得在每对源与目的结点间存在多条路径。在 e s s r b网络中可以使用寻径标记的分布控制。e s s r b网络对单一故障具有耐 故障性，并且对多个故障具有良 好特性。e s s r b网络是在并行分布式系统中进 行可靠通信的一个很好的解决方案。 第二章互连网 络的基本问 题 第二章互连网络的基本问题 2 . ，互连网络概要 通常一个并行计算机包括 3个基本组成部分:处理一 存储结点，结点一 互连 网络的接口，以及将他们连成一体的互连网络。近些年，能够提供 1 0 0 0 个计算 结点以上的商用计算机己经面市，同时对 1 0 0 0 0个结点规模的并行计算机的研 究也正在开展。在这些系统中，系统的互连网络问题往往是影响系统性能的主 要因素。 互连网络与我们平常所说的局域网 ( l a n)、广域网 ( wa n)有一些共 同的基本概念和术语，但是有关互连网络的设计与 l a n. wa n却有着很大的 区别，主要是在时间单位上相差很多数量级。 并行计算机互连网络通常是按照某种规则互相连接到一起，而这些网络的 拓扑构造往往具有很整齐的数学特征，并与重要的并行算法所要使用的基本通 信方式有密切联系。也有相当数量的研究侧重于对互连网络拓扑构造的数学研 究，而假设其上的并行算法在通信方式上具有平均的性能。在两个独立的异步 设备之间通过电子或光学连接来传递信息也有一系列物理设计问题。另外，由 于存在着在多个信息流争用通信资源的情况，而这种争用将对网络性能造成一 定的影响，因此对于网络的性能模型的理论和实现技术的研究也是一个热点问 题 ，19 1 在并行机中，互连网络的任务是将信息从源结点发送到目的结点，以支持 实现并行计算模型的网络事务处理。原则上，完成这项任务的时间延迟越小越 好，同时应当允许大量的这样的信息传递并发。另外， 对于并行机其余部分的 成本来说，这部分的成本应当比较便宜。 互连网络是由 连接或交换开关( s w it c h ) 组成， 而这些连接应提供一种将消息 从源结点发送到目的结点的寻径方法。一个 “ 连接”实质上是一束载有模拟信 号的电线或光纤。而该连接两端都应具有将进行模拟信号和数字信号进行转换 的装置。 “ 物理层协议”是用来将数字信号和模拟信号进行转换的。消息发送 端、接收端和连接共同组成了一个 “ 通道”。 “ 连接层协议”将需要通过通道 的信息流划分成大的逻辑单元，称做 “ 消息包” 或 “ 消息”。而交换单元需要 决定从输入通道来的消息应当从哪个输出通道送出。计算结点就是通过一组这 样的连接或交换单元进行通信的。 “ 结点级协议”嵌入了辅助进行远程通信的 命令，使得消息包或消息在结点之间能够进行交换以完成网络事务处理。 第二章互连网络的基本i7 题 我们可以把一个并行计算机互连网络从形式上看成一个图，图中处理结点 和交换单元通过通信通道连接在一起。这里的 “ 通道”是指一个物理的连接处 理结点和交换单元的连接，并包含一个数据缓冲区以存储传输的数据。如果通 道的宽度为w， 信号发送频率为f - 1 / ( z 为时钟周期) ， 那么通道的带宽b = w f . 交 换单元将连接固定数目的输入通道和固定数目的输出通道，这个数目 称为度。 消息在源结点和目的结点之间的传递是通过一条路径，包括一系列的通道和交 换单元，并称之为寻径。 可扩展的互 连网络 口 口目 口 网 络 接 口 通信辅 助模块 通信辅 助模块 主存 卜 二 日处理器主存 尸州处理器 图1 一个通用的大规模并行计算机模型中互连网络的构造模型4 1 2 . 2互连网络的 特征因素 一个互连网络具有下面特征因素:网络拓扑结构、寻径算法、交换策略和 流控制机制。 2 . 2 . 1网络拓扑结构 它是指网络图的物理连接结构。该结构可能是规则的 ( 例如 2 一 维网格型网 络)，也可能是不规则的。大多数并行计算机采用非常规则的网络拓扑结构。 这种拓扑结构中还分成两类，直接网络和间接网络:在直接网络中，任何一个 处理结点连接到每一个交换单元上，而间接网络中，处理结点只连接到交换单 元中的一个子集上。许多并行计算机采用了混合方式，因此这种界限就不明显 了，于是需要加以区别的是处理单元和交换单元。处理单元产生或消除消息传 递，而交换单元只对消息进行转发。 第二章互连网络的基本问题 2 . 2 . 2寻径算法 寻径算法决定了消息在网络上传递时按照何种路径走。它将可能的路径集 合限制到一个小的合法路径的集合。各种不同的寻径算法提供了不同的性能。 通常，每个结点均有一张寻径表，指明向其它结点发送消息可供选择的各条路 径及其传输速度和费用 ( 表中内容必要时可修改)。常用的三种寻径选择模式 有三种z 0 , . 固定寻径( f i x e d r o u t i n g ) : 预先指定自 结点a到结点b的 某条通讯路径， 且该路径一经确定，在硬件不失效的情况下便不再改变。为了降低通讯费用， 通常选择网络中a至 b的最短路径。 虚电 路( v i r t u a l c i r c u i t ) : 自 结点a到结点b的 通讯路径只在某个时间段 内固定，不同时间段可能经由不同路径; 动态寻径( d y n a m i c r o u t i n g ) : 自 结点a到结点b的 路径仅在消息传送过程 中才决定。这种动态确定路径的方法可能造成一批消息的各个分段可能选择不 同的道路。结点 a可能决定把某消息发送给结点 c , c又决定将它发送到 d,。最终消息被送到结点 b 。通常，. 一结点将从可行的通讯链路中选择 当时使用最少的路径发送消息。 上述三种模式各有利弊。固定寻径既快速又简单，尤其是以维数为顺序的 固定寻径网络划分起来非常方便，对预防死锁也非常容易。在大多数现有的多 机系统的寻径网络都采用了固定寻径方式。但是，为了避免死锁的发生，尽管 在源结点和目的结点之间有大量的路径可以选择，固定寻径仅选择一条从源结 点到目的结点的路径。这意味着由于不能灵活的使用物理通道，互连网络不能 有效的使用其物理连接的密度。又如负载常常变动，也便不宜采用固定寻径模 式，否则会导致路径忙闲不均。采用虚电路模式可以部分的解决这一问题，而 若采用动态模式，则完全避免由 于负载变动导致繁忙不均的现象。前两种模式 能确保所发消息按发送次序到达目的地，而动态模式则不一定。采用动态寻径 模式时，消息到达顺序可能与发送顺序不一致。给每个消息附加上顺序号即可 解决这一问题2 2 1 2 . 2 . 3交换策略 它决定了消息中的数据是如何通过路径的。有两种基本的交换策略:电路 交换和包交换。在电路交换中，从源结点到目的结点的路径建立起来后，一直 保持到消息己经完成在此路径上的传输。而包交换中，消息被分解成一系列更 小的包。每个包包含了寻径信息和次序信息以及数据。各个包是单独从源结点 第二章互连网络的基本问题 发送到目的结点的。包交换的方式通常更好的利用了网络资源，因为只有当一 个包在传输时，才占用网络连接和缓冲区。 2 . 2 .4流控制机制 它决定了消息或消息的一部分何时开始在它的路径上进行传送。当两条或 两条以上的消息试图同时使用同一网络资源 ( 如一个通道)时，尤其需要流控 制。其中的一个消息应当被暂停，放在缓冲区里，或选择另一条路径，或简单 的被丢弃。以上这几种选择都对交换单元的设计有特殊的要求，同时对通信子 系统的其他方面有影响。通常提到的流控制机制有存储转发、虚跨步( c u t - t h r o u g h ) ， 虫 蚀寻径 技术， 以 及多 通道流控制技术。 其中 虫 蚀寻径 ( w o r m h o l e r o u t i n g ) 技术是目 前最引人注目的寻径技术.它具有低网络延迟、通道共享性好、易于 实 现对多点的组播和广播等优良 的特性。它已 成功的应用于一些先进的多计算 机系统。 在虫蚀寻径技术中，把一个消息分成一个个流控制片。其中第一个片是消 息的头微片 ( h e a d fl i t )， 它包含了 这个消息的 所有寻址信息。 最后一个片是尾 微片 ( t a i l o r fl it )，包含了消息结束符的数据微片。中间的微片都是数据微片。 一个流控制微片是通信队列和通道所能接受或拒绝的最小信息单位。对一个消 息来讲，在每个结点上只需能缓冲一个微片就能满足要求，而不象存储转发那 样，把一个消息的全部都存储到一个结点上后，再把它向下一个结点传送。虫 蚀寻径的操作方法实质就是通过用一个消息的头部直接开辟一条从输入链路到 输出链路的路径。每个消息中的微片以流水的方式在网络中向前 “ 蠕动”，每 个微片相当于虫的一个关节， “ 蠕动”是以关节为单位顺序地向前爬行。当消 息的头微片到达一个结点 a的寻径器后，寻径器根据头微片的寻径信息立即做 出寻径选择: 如果所选择的通道空闲且所选择的结点b的通信缓冲可用，那么这个头微 片就不必等待，直接通过结点 a传向下一个结点 b ;随后的其他微片跟着向前 “ 蠕动”一个结点。当消息的尾微片向前 “ 蠕动”一个结点之后，它刚才所占 用的结点就被放弃了。 如果所选择的通道不空闲或者所选择的结点的通信缓冲区不可用时，那么 这个头微片就必须在此结点的通信缓冲区中等待，直到上两者均为可用时为止; 其他微片也在原来各自的结点上等待。此时，被阻塞的消息不从网络中移去， 微片不放弃它所占用的结点和通道。由于除头微片外，其他的微片都不含寻径 信息，所以微片序列必须保持网络中连续的通道，不能被其他的消息的微片所 打断。 第二章互连网络的基本问题 2 . 3互连网络的性能参数 下面定义几个用于估算互连网络计算复杂性、通信效率和网络价格的重要 参数。 互连网络中的结点数称为互连网络的规模，它表示该互连网络所能连接的 功能部件的多少;与结点相连的边 ( 链路或通道)数称为结点度，用 d表示。 在单向连通的情况下，进入结点的边数称为入度，而从结点出来的边数称为出 度，结点度即为两者之和。结点度反映了一个结点所需要的 v 0端口数，也即 反映了结点的价格。为了降低价格，应尽可能使它小，而为了构造可扩展系统， 使构件能够模块化，尽量要求结点度保持恒定:互连网络中两个结点相连的最 少边数称为距离;互连网络中任意两个结点之间的距离的最大值称为网络的直 径，它是说明互连网络的通信性能的一个指标。因而从通信的观点来看，互连 网络的直径应当尽可能小;当一个互连网络被切成相等的两半时，沿切口的最 小通道数称为通道等分宽度，用b 表示。所以，线等分宽度就是b=b x w , w 为通道宽度，用位表示。因此，等分宽度是说明沿等分网络最大通信带宽的一 个参数，网络的所有其它横截面都应限制在等分宽度之内;结点间的线长是两 个结点间的线的长度，它会影响信号时延、时钟扭斜和对功率的需要;假若从 网络的任何结点看其拓扑结构都是一样的话，我们就称此网络为对称网络，对 称网络比较容易实现，编程也比较容易。网络的寻径距离指的是在一对结点之 间的寻径所使用的连接数目 。平均距离指的是所有结点对的寻径距离的平均值; 而平均距离也可以有随机的一对结点之间的距离。在直接网络中，对于每一组 交换单元来说，都要提供寻径，而在间接网络中，只需要提供处理结点之间的 寻径。网络分割是指如果一些连接或交换单元被去除掉后，系统就会被分割成 无法通讯的几个子系统。 2 . 4互连网络的结构分类 网络拓扑结构是互连网络的三大要素之一，而且是互连网络合理布局的关 键因素。迄今为止，设计出的互连网络已经很多，也有各种分类方法，但从并 行处理和分布式计算机系统的角度出发，以网络的开关元件和处理单元结点的 连接方式来分更为合理， 这样，可将互连网 络分为静态和动态两大类。 静态互连网络 ( s t a t i c i n t e r c o n n e c t i o n n e t w o r k )是指在各结点之间有专用 的连接通路，而且在运行中不能改变的互连网络。在静态互连网络中，每一个 开关元件固定地与一个结点相连，建立该结点与邻近结点之间的被动连接通路， 直接实现两结点处理机之间的通信。这种网络的开关元件都分散设置在每个结 第二章互连网络的基本问题 点内部，从外面看是看不到开关元件的。因此，网络中结点间的连线是固定连 接的，且是无源的， 其连接通路也就被称为被动 ( p a s s iv e ) 连接通路。 它能够 直接实现两个结点之间的通信，而非相邻结点之间的通信必须经过某些中间结 点的协助才能完成。静态互连网络经常用在一个集中式系统中子系统之间的固 定连接或者分布式系统的多个计算结点。 动态互连网络 ( d y n a m i c i n t e r c o n n e c t i o n n e t w o r k ) 则是指设置有源开关， 可以根据需要借助控制信号对连接通路加以重新组合，实现所要求的通信模式， 相邻各级之间具有固定的级间连接，利用动态设置开关的状态来实现输入与输 出间的所需连接的建立。动态互连网络中，其输入输出两侧的开关元件与结点 相连。在控制信号的作用下，通过网络所有开关的工作，建立结点间主动可控 的连接通路，使系统具有重构能力，这种开关网络常以一个集中的独立部件出 现，网络两侧结点间的连接可通过有源开关的状态来动态地改变。因此其连接 通路被称为主动( a c t i v e ) 连接通路。 在具体到设计并行计算机系统体系结构时，根据各个系统具有的不同的目 的和规模来选择不同性质的互连网络。对于大规模的并行计算机系统，一般使 用静态互连网络，简称为静态网络;而对于中小规模的，比如十几个到几十个 处理单元的并行计算机系统，考虑到这时对内存访问的均一性对系统具有高性 能比较有利，往往会采用动态互连网络，简称为动态网络。 第三章动杰互连网络 第三章动态互连网络 3 . 1对动态互连网络的分类 动态互连网络中，其输入输出两侧的开关元件与结点相连。在控制信号的 作用下，通过网络所有开关的工作，建立结点间主动可控的连接通路，使系统 具有重构能力，这种开关网络常以一个集中的独立部件出现，网络两侧结点间 的 连 接 可 通过 有 源开 关的 状 态 来动 态 地改 变。 因 此 其 连接 通 路被 称 为 主 动 ( a c t iv e ) 连接通路，可以从不同的角度对动态互连网络进行分类15 1 3 . 1 . ，按输入端和输出端的布置分类 按照动态互连网络输入端和输出端的布置情况，可将其来分为单边和双边 两类。单边网络的输入端与输出端都安排在网络的同一边，任一端口可与任一 其他端口相连，并工作在双向状态，这类网络适合于实现同一组部件之间的互 连。双边网络的输入端与输出端分别安排在网络的两边，这类网络在实际的系 统中多用于实现两类不同部件，例如处理机和存储模块之间的互连。 3 . 1 . 2按连接能力分类 按照连接能力可以将动态互连网络分为非阻塞、可重排和阻塞网络三类。 非阻塞网络可以实现输出端和输入端之间的任意连接，无需因增加新的连接而 改变原有的连接路径，如 c l o s 网络、 c a n t o : 网络和 g c n一般化互连网络等都 属于这一类。它们可以无阻塞地实现输入端到输出端的一对一连接，也可以实 现一到多的连接。可重排网络是指在已经实现输入端与输出端之间互连的网络 中，如果增加新的输入输出对的互连，或要改变原来端对中几对的互连，则都 有可能会引起路径冲突。但这种冲突可以 通过对已有的连接重新安排来加以避 免，以 达到无阻塞的实现输入输出 端对任意连接的目 的， 如 b e n e s f2 3 ,2 a i 网 络。 阻 塞网 络是指一对以 上输入端和输出端同时实现互连可能会出现路径冲突，但由 于这类网络所用的开关量少，延时也不长，寻径控制较简单，而且用二次通过 或采用屏蔽的手段可以实现许多常用的置换函数，因此， 这类网络已 被广泛应 用于实际的系统中。 s t a r a n网 络2 5 ,2 6 1 、 间 接二 进制n 立方体网 络( i n d i r e c t b i n a ry 第三章动态互连网络 n c u b e n e t w o r k ) l j , o m e g a 网 络、 数据变换网 络 ( d a t a m a n i p u l a t o r ) , b a n y a n 网 络和d e l t a 网络都属于这一类。 3 . 1 . 3按网络拓扑分类 按照网络拓扑分为单级或多级的结构。单级网络是由一级开关元件与构成 一 种连接模式的线路连接而成的， 如交叉开关网 络( c r o s s b a r n e t w o r k ) 。 这种网 络 如果循环使用多次，输入端的数据有可能到达预期的输出端。大多数的动态网 络常由 好几级开关构成多级网 络， 称为多级动态互连网 络 ( m u l t i s t a g e i n t e r c o n - n e c t i o n n e t w o r k , m i n )。 这种网 络的 控制比 单级复杂， 延时更长，与级数成正 比，但它一次通过就能实现某种置换函数，如s t a r a n网络。 3 . 1 .4按开关元件的类型分类 这种按开关元件类型的分法也能较好地反映出网络的结构特征。目前，已 提出的开关元件有三类:交叉开关、交换开关和细胞开关。这三种开关实际上 都是基于开关原理的互连开关，交换开关也是2 x 2 的交叉开关。用它们构成互 连网络的结构方式不同，因而赋予相应的名称。由交换开关构成的有单级和多 级互连网络;由细胞开关构成的是细胞互连阵列。 3 . 2动态互连网络的结构描述 从上面对动态网络的分类可以看出，动态互连网络， 特别是多级动态互连 网络的结构可以 用开关元件、结点间的互连拓扑 ( 包括连接通路)和控制方式 等三个参量来加以描述15 1 3 . 2 . ，开关元件 开关元件是多级网络中最基本的模块，它在不同控制信号的作用下，工作 在不同的状态，以实现输入输出之间的不同互连。它可以实现一对一和一对多 的连接，但不能实现多对一的连接，因为这样将在输出端发生冲突。 最普通的开关元件是具有两个输入端和两个输出端的交换开关，一般来 说，一个 nx n的交换开关有 n 种合法状态，但只可以实现 n! 种排列置换。 如图2 所示，每个交换开关都有四种基本工作状态: a ) 直连( s t r a i g h t ) . 上输 入端与 上输出 端相连， 下输入 端与 下输出 端相连。 b ) 交换( e x c h a n g e ) . 上输入端与下输出 端相连， 下输入端与上输出 端相连。 第三章动态互连网络 c ) 上播( u p p e r b r o a d c a s t ) . 上输入端与上、 下输出 端同时相连， 下 输入端不用. d ) 下播( l o w e r b r o a d c a s t ) . 下输入端与上、 下输出 端同时相连， 上输入端不用. 图2 2 x 2 交换开关的连接状态 只有上述a , b两种功能的称为2 x 2二功能交换开关，像间接二进制n方 体网络所用的就是这种开关。具有上述四种功能的称为2 x 2四功能交换开关， 在o m e g a 网 络中就采用这种开关。 此外，开关的两个输入端同时与一个输出 端 相连的情况是不允许的，这是冲突状态。 3 . 2 . 2互连拓扑 互连拓扑是指多级网络级间链路互连的模式与规则。用不同的连接模式可 以构成多种不同的互连网络。如 s t a r a n网络与间接二进制 n方体网络，它们级 间的互连模式是随级号的递增按子碟式置换设计的，在输出级开关至网络的输 出 端之间 还实 现了 逆均 匀洗牌置换 模式 连接. 又如o m e g a 网 络， 其级间的 连接 模式都是均匀洗牌排列。数据变换网络其级间的连接模式除实现直送的恒等置 换外，还有向上和向下的各种移数置换。其他的各种多级网络也按照一定的级 间连接模式组成。由此可见，连接模式是描述多级互连网络结构或称为拓扑 ( t o p o l o g y ) 的 十分重要的 参量。 动态互连网络的互连拓扑决定了各处理单元间的通信结构、处理单元和存 储器以及 i / o设备部分之间的数据通路，直接影响着整个系统的信息传输的速 度、容错能力、寻径控制算法的复杂性以及整个系统的工作效率，从而对整个 并行计算机系统的性能有着重要的影响，在一定程度上决定着整个系统的性能 价格比。 第三章动态互连网络 3 . 2 . 3控制方式 控制方式是指对网络中的各交换开关的控制方法，一般来说有三种控制方 式。 ( 1 ) 级控制 同一级中的所有开关用同一个信号来控制，它们都处于同一种工作状态， 一共需要 n个控制信号。其优点是控制简单，比较实现容易;但是网络能实现 的互连函数少。 ( 2 ) 单元控制 网络中的每一个开关都有单独的控制信号。因而它们即使在同一级中也可 以处在不同的工作状态， 一共需要n x n / 2 个控制信号。 这种方式控制下的网络， 它们能实现的互连函数显然比级控制的多得多，但控制比较复杂，实现起来也 麻烦一些。 ( 3 ) 部分级控制 这是界于上述两种之间的一种控制方式。 用i + l 个控制信号来控制第i 级， 这里， o - i -n - 1 , n 为级数， 要用( n + 1 ) x n / 2 个控制信号。 3 . 3动态互连网络的评价标准 衡量一个多级互连网络的优劣通常从下列几方面考虑17 .2 9 1 . ( 1 ) 连接特性要好，即能实现的互连函数要多; ( 2 ) 网络延时，即通过网络传输一个信息单元在最坏情况下的时间延迟要 求要短; ( 3 ) 网 络的 带宽即 最大的 数据传 输 速率 ( 其单位是m b / s ) 尽可能高; ( 4 ) 开关设备量要少，即 其造价要低; ( 5 ) 控制简单， 且希望获得控制信号的系统开销也要小; ( 6 ) 便于制成集成电 路，并且一个网络具有能够按机器资源的 性能增长进 行模块化扩展的能力。 3 .4单级动态互连网络 目 前主要的单级动态互连网 络有交叉开关网 络( c r o s s b a r ) 1 0 1 . 交叉开关网 络是最基本、最直截了当、连接功能最强、也是最早使用的开关连接网络，它 是各种多级动态互连网络的基础，它的基本参数、交叉点数和延迟时间，都将 是各种多级动态互连网络的比较尺度。交叉开关要求可以并行的进行信息传输， 并且解决在一个存储器周期内多个请求同时访问同一个存储器模块的访问冲突 第三章动态互连网 络 问题，比如使用预先指派优先权的办法等。交叉开关网络为处理器和存储器之 间提供了多重独占线路，即每一个处理器和每一个存储器之间都存在一个开关 可以使其直接连接。其结构的简单、控制的方便以及均匀的单位延迟，都是其 他互连网络所不能与其相比的，而且一般不会发生线路争用的冲突，因而目前 在计算机系统中被广泛采用。但所有这些都是以很高的硬件耗费为代价的，甚 至有时技术上是做不出来的，而且它还有一个缺点是一旦建成一个完整的交叉 开关网络之后，就不容易对它进行扩展p 1 。如图3 所示n x m的交叉开关网络示 意图。 1 2 3 m 图3 交叉开关网络结构图 3 . 5多级动态互连网络 在多级动态互连网络中，各结点通过 n x m 的交换开关 ( 即交叉开关箱) 实现互连，结点之间可以通过开关直接进行通信。当系统规模上升时，传输延 时也随着上升。为改善这些网络的性能，提出了许多级与级之间的连接方式， 多级网络的混洗方式和寻径控制是非常关键的技术。目 前主要的典型多级动态 互 连网 络有: o m e g a 网 络 8 1 、 二 网 络19 1 . g e n e r a l i z e d c u b e 网 络 0 1 . b a s e l i n 。 网 络叫、 d e lt a 网 络 n 2 1和b a n y a n 网 络 【15 1等。 本 节 简 要 介 绍 一 些 有 代表 性的 例 子。 混洗连接就是将全部源结点分成数目 相等的两部分，然后一个隔一个依次 隔开，则原来相邻的源结点经过一次混洗之后，它们之间的距离变为 2 ，如果 第三章动态互连网络 有n个源结点，经过 1 次全混洗之后，它们之间的距离变为2 ，也就是每一次 混洗都使它们之间的距离增大一倍3 1 ) 。能够跟踪这种混洗过程中的每个数据传 送轨迹的方法是使用移位寄存器。对任一列移位寄存器，其输入数据自顶向下 的编号为0 到n - 1 ( n=2 , i =1 , 2 , 3 , )，经过若干次混洗，可以预知此数据 到达哪个寄存器。假设原数据在第i 个寄存器，经过k 次全混洗，也就是将i 的 二进制放入循环移位寄存器， 执行k 次循环左移， 所得到的二进制数为j ，即原 数据到达第j个寄存器。 可知全混洗的功能就是将处理单元的二进制地址循环 左移一位。只使用混洗是不充分的，所以实际应用中常附之以交换连接，其功 能是将相邻的奇数和偶数地址中的数据相互交换一下。 3 .5 . 1 o m e g a网络 1 . o m e g a 网 络的 结 构 l a w r i e ( 1 9 7 5 ) 提出了 应用这 种混 洗交换 连接构 成的o m e g a 网 络， 这个网 络已 经用于伊利诺依大学的c e d a r 多处理机、 i b m的r p 3 和纽约大学的u l t r a - c o m p u t e r . 通常， 具有n个输入端的 使 用2 x 2 的 交换开 关的o m e g a 网 络有i o g 2 n 级，每一级都由混洗的内部连接链路和n / 2个交换开关来组成。虽然n个输入 端的o m e g a 网 络总共有n ! 种排列置 换， 但因为o m e g a 网 络是一 种阻 塞非全连 接网络，所以