（管理科学与工程专业论文）光互连网络通信模式及通信协议研究.pdf

摘要 并行计算机是高性能计算机领域的重要研究方向，大规模并行机的关键是需要高效、 快速、大容量的互连网络，所以改善并行计算机性能的关键问题是设计高性能的互连网络。 电互连网络不仅存在着“瓶颈效应”、运算速度有限、时钟歪斜、互连带宽受限等问题，而 且从工艺上也是无法解决的。由于光信号具有并行、高速和可在空间交叉互连等特点，所 以光互连网络可以克服电互连网络的以上种种限制并且无电磁干扰问题，能大大提高运算 的准确性和稳定性。因此研究光互连网络具有重大的现实意义。 本文首先分析了光互连网络的研究现状及各种通信模式。然后，重点讨论了在光多级 互连网络中无串扰的实现通信模式的调度问题，给出了基于时域法的无串扰的实现置换路 由的三种调度算法，讨论了算法的时间复杂度以及所需要的调度次数的上界。其次，解决 了在b u t t e r f l y 中如何无串扰的实现置换路由的问题，然后，又将该结果推广到任意通信 模式，讨论了它们的无串扰通信问题。再次，分析和比较了现有的光网络中的分布式波长 预留协议，提出改进的策略。最后，对提出的协议用网络模拟软件n s 2 进行了模拟，证明 改进的波长预留协议可以降低阻塞率。 本文的主要研究工作及创新点如下： l 、分析光互连网络的研究现状，包括光互连网络的拓扑结构、参考模型、分类和研究热点 等。对网络中存在的诸如单播、组播、广播、选播和置换路由等通信模式进行深入的理 - 4 论探讨。 ， 2 、给出了b a n y a n 网络的一些性质及实现置换路由的冲突次数及发生冲突的充要条件，并 且给出了基于时域法的无串扰的实现置换路由的三种调度算法，讨论了算法的时间复杂 度以及所需要的调度次数的上界。 3 、解决了在b u t t e r f l y 中如何无串扰的实现置换路由的问题，然后，又将该结果推广到任 意通信模式，讨论了它们的无串扰通信问题。 4 、分析和比较了现有的分布式波长预留协议s i r 和d i r 协议，指出了其中存在的问题，并 在此基础上提出改进的策略s d i r 协议。试验结果表明，改进的波长预留协议可以降低 阻塞率。 5 、介绍了著名的网络模拟软件n s 2 在不同操作系统下的安装过程，然后介绍了n s 2 的模拟 原理、步骤，并举例说明了模拟的过程。j 关键词：光互连网络、通信模式、光多级互连网络、置换路由、串扰、分布式波长预留协 议、n s 2 中图分类号：t p 3 9 3 山东师范大学硕士学位论文 2 a b s t r a c t p a r a l l e lc o m p u t e ri sa ni m p o r t a n ta r e ao ft h er e s e a r c ho fh i g h p e r f o r m a n c e c o m p u t e r ，a n dt h ee f f i c i e n t ，r a p i d ，l a r g e c a p a c i t yi n t e r c o n n e c t i o nn e t w o r ki s t h eb a s eo fl a r g e s c a l ep a r a l l e lc o m p u t e r t h e r e f o r e ，t h ed e s i g no fh i g h p e r f o r m a n c ei n t e r c o n n e c t i o nn e t w o r ki si m p o r t a n tt o t h ei m p r o v e m e n to fh i g h p e r f o r m a n c ep a r a l l e lc o m p u t e r t h e ”e f f e c to ft h eb o t t l e n e c k ”o fe l e c t r o n i c i n t e r c o n n e c t i o nn e t w o r kl i m i t so p e r a t i o ns p e e d c l o c ks k e wa n di n t e r c o n n e c t i o n b a n d w i d t hc o n s t r a i n t s ，w h i c hc a nn o tb ed e a l e dw i t ht h r o u g ht e c h n o l o g y f i b e r o p t i cc o m m u n i c a t i o n so f f e rac o m b i n a t i o no fh i g hb a n d w i t h ，l o we r r o rp r o b a b i l i t y ， a n dg i g a b i tt r a n s m i s s i o nc a p a c i t y t h e r e f o r e ，o p t i c a li n t e r c o n n e c t i o nn e t w o r k c a dn o to n l yo v e r c o m et h ea b o v ec o n s t r a i n t si ne l e c t r o n i cn e t w o r k ，b u ta l s oa v o i d e l e c t r o m a g n e t i ci n t e r f e r e n c e ，a n dg r e a t l yi n c r e a s et h ea c c u r a c ya n ds t a b i l i t y o p e r a t i o n s t h e r e f o r et h es t u d yo fo p t i c a li n t e r c o n n e c t i o nn e t w o r ki so fg r e a t p r a c t i c a ls i g n i f i c a n c e f i r s t l y ，t h e t h e s i sa n a l y s e st h er e l a t i r er e s e a r c hi nt h eo p t i c a l i n t e r c o o n e c t i o nn e t w o r k s ，a n ds t u d i e sc o m m u n i c a t i o nm o d e si nt h en e t w o r k sd e e p l y s e c o n d l y ，i td i s c u s s e sh o wt oa v o i dt h ec r o s s t a l ki no p t i c a ls w i t c h e sa n ds e v e r a l a l g o r i t h m sa r ep r o p o s e d t h i r d l y ，d i f f e r e n td i s t r i b u t e dw a v e l e n g t hr e s e r v a t i o n p r o t o c o l sa r ed i s c u s s e da n dc o m p a r e d s o m ep r o b l e m sa r ep r e s e n t e da n di m p r o v e m e n t s c h e m e sa r ep r o v i d e d f i n a l l y ，n s 2a r ed i s c u s s e da n ds i m u l a t i o nr e s u l t ss h o wt h a t t h ei m p r o v e m e n ts c h e m e sc a nr e d u c et h eb l o c k i n gp r o b a b i l i t y t h em a j o rr e s e a r c hw o r k sa n di n i t i a t i v ep o i n t si nt h i sa r t i c l ea r ea sf o l l o w s ： 1 t h et h e s i sa n a l y z e st h e r e l a t i v er e s e a r c hi nt h eo p t i c a li n t e r c o n n e c t i o n f i e t w o r k sa n ds t u d i sc o m m u n i c a t i o nm o d e si nt h en e t w o r k sd e e p l y ，s u c ha su n i c a s t ， m u l t i c a s t ，b r o a d c a s t ，a n y c a s ta n dp e r m u t a t i o nr o u t i n g 2 p r e s e n t i n gb a n y a nn e t w o r k sp r o p e r t ，c o n f l i c ta n d t h en e c c e s a r ya n d s u f f i c e n tc o n d i o n so fc o n f l i c t t h e n ，t h r e er o u t i n ga l g o r i t h m sa r ep r e s e n t e do n r e a l i z i n gp e r m u t a t i o nr o u t i n gb a s e do nt i m ed o m a i na p p r o a c hu n d e rt h ec o n s t r a i n t o fa v o i d i n gc r o s s t a l k ，a n dt h ec o m p l e x i t yo ft h ea l g o t i t h m sa r ea n a l y s e d 3 d i s c u s s i n gh o wt or e a l i z ep e r m u t a t i o nr o u t i n gu n d e rt h e c o n s t r a i n to f a v o i d i n gc r o s s t a l ki nb u t t e r f l yn e t w o r k ，a n dt h e n ，t h er e s u l t sa r ee x t e n d e dt o a r b i t r a r yc o m m u n i c a t i o nm o d e 4 d i f f e r e n td i s t r i b u t e dw a v e l e n g t hr e s e r v a t i o np r o t o c o l sa r ed i s c u s s e da n d c o m p a r e d s o m ep r o b l e m sa r ep r e s e n t e da n di m p r o v e m e n ts c h e m e s a r ep r o v i d e d s i m u l a t i o nr e s u l t ss h o w t h a tt h ei m p r o v e m e n ts c h e m e sc a nr e d u c et h eb l o c k i n g 山东师范大学硕士学位论文 p r o b a b i l i t v 5 i n t r o d u c i n gt h ef a m o u s n e t w o r ks i m u l a t i o ns o f t w a r en s 2 si n s t a l l a t i o ni n d i f f e r e n to p e r a t i n gs y s t e m s ，a n dt h e ni n t r o d u c e dn s 2s i m u l a t i o np r i n c i p l e s ，s t e p s ， a n di l l u s t r a t e ds i m u l a t i o np r o c e s s k e y w o r d s - - o p t i c a li n t e r o o n n e c t i o nn e t w o r k s ，c o m m u n i c a t i o nm o d e ，o p t i c a lm u l t i s t a g e i n t e r c o n n e c t i o nn e t w o r k s ，p e r m u t a t i o nr o u t i n g ，c r o s s t a l k ，d i s t r i b u t e dw a v e l e n g t h r e s e r v a t i o np r o t o c o l ，n e t w o r ks i m u l a t o r2 c l a s s i f i c a t i o n t p 3 9 3 3 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得( 注：如没有其他需要特别声明的，本 栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：撼、 导师签字：务l 才嚎 学位论文版权使用授权书 本学位论文作者完全了解有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权 可以将学位论文的全部或部分内奄编入有关数据庠进行检索，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 一躲獭、一字：封才曙 签字日期：跏晶年5 月o b签字日期：2 州锌f 月饵 山东师范大学硕士学位论文 第一章光互连网络概述 1 1 互连网络的提出及意义 到目前为止，人们对更高计算能力的需求还是越来越迫切。尽管从1 9 8 6 年到1 9 9 6 年， 处理器的性能大约每3 年翻一番，但软件复杂度、应用的规模和解决方案的质量仍不断推 动着处理器向更快的速度发展。在国防、太空、汽车制造业和科学领域已经出现了大量具 有巨大挑战性的应用问题，它们要求计算机具有每秒钟万亿次级浮点运算( t e r a f o p s ) ，甚 至更高级别的计算能力。 高性能计算机技术是现代科学研究、工程技术开发和大规模数据处理的关键支撑技术， 没有高性能计算机，大量复杂问题的计算和事务处理就无法在合理的时间内完成。利用高 性能计算机还可以解决一些仅靠理论及实验的方法无法解决的问题，例如核爆炸模拟、宇 宙的形成及演变过程研究、中长期天气预报、石油地质勘探、数字地球和大规模事务处理 等。 并行计算是在并行计算机或分布式计算机等高性能计算系统上所作的超级计算，是为 了解决大规模、大数据量的大型科学计算而发展起来的一门学科。由于种种因素的制约及 使用计算机方式的改变，单台计算机系统的性能与功能难以满足应用需求的情况下，由多 个计算机节点经专门设计的互连网络紧密耦合而构成的大规模并行处理系统，以及由多个 自主的高性能节点经计算机网络连接组成的分布处理环境，将成为高性能计算机领域的重 要研究方向。目前，大规模并行机从连接性质来看有两种：一种就是分布式内存计算机。 另一种是共享内存计算机。无论哪一种，这其中的关键是需要高效、快速、大容量的互连 网络，以实现处理器和处理器或处理器和内存之间的信息交换或者通信。所以改善并行计 算机性能的关键问题是设计高性能的互连网络。因此互连网络的设计就变得尤为重要了。 目前较为常见的高性能网络，如m y r i n e t r ，n c u b e 一2 1 3 ，i n t e lp a r a g o n m j ，c r a yt 3 d 5 1 ， t h i n k i n gm a c h i n e sc o r p c m 一5 t 。1 ，n e cc e n j u 一3l ，j ，i b ms p 2 t 8 1 等。 输 入 端 图1 1 互连网络的模型 输 出 端 那么，究竟什么是互连网络呢? 并行机的互连网络是一种由开关元件按一定的拓扑结 构和控制形式构成的网络。其任务是实现从任何源节点向任何目的节点传输信息，支持用 以实现编程模型的网络事务处理唧。它必须以尽可能小的延迟完成这个任务，并允许大量这 l 坐查堕蔓奎兰望主兰垡丝塞 样的传输并发的发生。 互连网络的模型可以表示为一个三元组( n ，m ，c ) ，如图1 1 所示，n 表示输入端数：m 表 示输出端数：c 表示连接能力，即网络能同时实现连接的最大数目。 我们可以将并行机互连网络形式化的描述成一个图，这里顶点v 是由通信通道c _ g v x v 连接的处理主机或交换机单元。通道是主机或交换机单元之间的条物理链路，包括保存 传送数据的缓冲器。典型情况下，主机与单个交换机相连，但也可以与多个独立的通道连 接。消息沿网络中的一条路径从源主机传输到目的主机，该路径由一系列通道和交换机组 成。 互连网络应用十分广泛，小到超大规模集成电路( v l s i ) 内部总线，大到计算机广域网【i l 。 互连网络的应用主要包括底板总线和系统域网络、电话交换机、异步传输模式( a t m ) 和网际 协议( i p ) 交换机内部网络。同时还包括向量超级计算机处理器存储器互连、多计算机和分 布共享主存多处理器系统互联网络、工作站和个人计算机集群、局域网、城域网、广域计 算机网以及工业应用网络等。互连网络的应用还在不断增长，例如：汽车集中控制系统就 需要一个网络把多个微处理器和外设连接起来。正因为多计算机互连网络可以应用于绝大 多数分布共享主存多处理器系统、局域网和系统域网，所以对互连网络进行研究具有重要 的理论和现实意义。 1 2 互连网络的特性 互连网络的特征由其拓扑结构、路由算法、交换策略和流控机制所刻画。， 1 、扑结构是网络图的物理互连结构，它可以是规则的，如二维的网格，也可以是非规 则的。大多数并行机采用高度规则的网络。通常我们区别直接或间接网络：直接网络使主 机与每一个交换机连接，而间接网络中主机仅与特定的交换机子集相连，这子集形成了 网络的边沿。许多机器使用混合的策略，所以更重要的是要区别两类节点：主机可以产生 和吸收流量，而交换机仅仅传递经过的流量。 2 、路由算法决定了消息在网络中沿哪一条路径传输。路由算法把可能的路径集合限制 为较小的合法路径集。存在许多不同的路由算法，提供不同的保证和各异的性能折中。在 并行机中我们仅关心主机到主机的路径。 3 、交换策略略决定了消息中的数据如何穿越它的路径。有两种基本的交换策略：电路 交换策略和数据包交换策略。电路交换策略中，在源主机和目的主机之间建立一条路径并 一直保持到消息通过电路为止。数据包交换将消息分割成一系列数据包。数据包包含路由、 序列信息和数据。数据包被逐个从原主机传递到目的主机。数据包交换允许我们更好的利 用网络资源，因为链路和缓冲器只有在数据包通过时才被占用。 4 、流控机制决定消息或消息的一部分何时在它的路径上运动。当两个或更多的消息试 图同时使用同一网络资源( 如一个通道) 时特别需要流控。可以让其中某个数据流原地暂停， 或令其分流进入缓冲器，或迂回到另一条路径，或简单地丢弃它。每一种选择都对交换机 山东师范大学硕士学位论文 的设计提出特殊的要求，并影响到通信子系统的其它方面。 1 3 互连网络拓扑结构 研究通信网络和通信算法是设计高性能并行和分布式计算机系统的关键【lo 。在过去的 几十年中，大量工作集中于发现有效的拓扑为潜在的通信网络结构服务。导致诸如环、 m e s h 1 ”、超立方【1 2 】、星形图【1 3 】等拓扑的设计和分析。对于一个好的网络设计的重要要求是， 对不同通信任务所提出的有效算法应具有可用性。 可见，对于并行处理或分布式系统来说，互连网络的设计是极为重要的【1 4 】。分布式系 统的通信性能很大程度上是由所选择的网络拓扑结构决定的。 网络的拓扑结构是抛开网络物理连接来讨论网络系统的连接形式，网络中各站点相互 连接的方法和形式称为网络拓扑( n e t w o r kt o p o l o g y ) 。拓扑图给出网络服务器、工作站的 网络配置和相互间的连接，它的结构主要有总线结构、环形结构、星型结构、树型结构、 m e s h 结构、超立方结构等。什么是最好的拓扑取决于设备的类型和用户的需求。一种在某 环境中表现很好的拓扑结构照搬到另一环境中，也许其表现就变差了。 为讨论方便，介绍以下定义： 定义1 1 射入或射出一个节点的边数称为节点度( n o d ed e g r e e ) 。在单向网络中，入射和出 射边之和称为节点度。 定义1 2 网络中任何两个节点之间的最长距离，即最大路径数，称为网嚣直径( n e t w o r k 一 d i a m e t e r n 。 + 定义1 3 将网络对分各半所必须移去的最少边数称为对剖宽度( b i s e c t i o nw i d t h ) 。 互连网络可分为静态网络与动态网络两类，本部分将分别予以介绍： 1 3 1 静态网络 ( 1 ) 一维线性阵列( 卜dl i n e a ra r r a y ) 一维线性阵列是并行机中最简单、最基本的互连方式，其中每个节点只与其左、右近邻 相连，故也叫二近邻连接。如图1 2 所示，用n - 1 条边将n 个节点串接，网络规模n ，内节 点度为2 ，直径为n - 1 ，去掉一条链路就分割了网络，因此它的对剖宽度为1 。任何连续的 节点段都是具有与整个网络相同拓扑结构的子网。此网络中的路由是简单的，因为在任何 一对节点之间只有一条路径。也正是由于在一对节点之间存在惟一的路径，该网络显然不 提供容错能力：一维线性阵列可扩展性好但可靠性差，只要网络上一个节点发生故障，就 会导致整个网络瘫痪。 o o ) ) _ ( ) 一。 图1 2 一维线性阵列 ( 2 ) 环形拓扑结构( r i n gt o p o l o g y ) 环形结构由网络中若干节点通过点到点的链路首尾相连形成一个闭合的环，即将_ 维线 生查塑蔓查兰堡主兰垡丝塞 性阵列的两端简单连接就形成了环( 如图1 3 所示) ，这种结构使每一个节点只能和它的一 个或两个相邻节点直接通信。要与其它节点通信，信息必须依次经过两者之间的每一个节 点。环形网络可以是单向的，也可以是双向的。其节点度恒为2 ，对剖宽度为2 ，网络规模 为n 。 环形结构具有如下特点：对于单向环，信息流在网中是沿固定方向流动的，两节点间 仅有一条路径，故简化了路径选择的控制；硬件复杂度低：当环中节点过多时，信息传输 速率低；节点更多的时间被用于替其它节点转发数据；环路是封闭的，不便于扩充：可靠 性差；维护难，对分支节点故障定位较难。尽管环形结构有上述诸多缺点，但因其简单易 行国内外许多多处理机系统采用环形拓扑结构，如f d d i ，s c i 等。 图i 3 环形结构 ( 3 ) m e s h 拓扑结构 m e s h ll i 网络是研究的较早，并且现在仍然是最为重要和最有吸引力的网络模型之一。 因其结构简单、规则及良好的可扩展性且易于v l s i 的实现，m e s h 网络不仅成为许多理论研 究的基础模型，也是许多大型多处理器并行计算机系统所采用的拓扑结构。在众多的m e s h 网络模型中，较为有用且最为流行的是二维m e s h ( 2 - dm e s h ) 网络，因此国内外许多多处理 机系统采用该拓扑结构，如i n t e lp a r a g o n 4 1 、s t a n f o r dd a s h 1 卦、t o u c h s t o n ed e l t a 16 1 、 s y m u l t2 0 1 0 1 7 】年口国内的曙光系列。 ： j 2 一dm e s h 在一个的二维网络中，每个节点只与其上、下、左、右的近邻相 案； 连( 边界点除外) ，故也称四近邻连接，如图1 4 ( a ) 所示。在m e s h 结构中，用二维坐标( x ，y ) 来标识其节点，若两个节点相邻，则它们的坐标值只有一位不同且差值为l ，称这样的两个 节点为邻接点。不难得到，该网络的节点度为4 ，网络直径为2 ( - 1 ) ，对剖宽度为。 如果在垂直方向上带环绕，而水平方向呈蛇状，则2 - dm e s h 就变成1 1 l i a cm e s h ，如 图1 4 ( h ) 所示，此时节点度恒为4 ，网络直径为一1 ，对剖宽度为2 。如果2 一dm e s h 的垂直和水平方向均带环绕，则它就变成2 - d 环绕( 2 一d t o r u s ) ，如图1 4 ( e ) 所示，其节点 度恒为4 ，网络直径为2 i 2j ，对剖宽度为2 。 辫 占。吣 u- 6巷 u每 弋 乙 ( a )( b ) 吣 。_ 电 f 吣电 呷【 。- 图1 4 四近邻连接 ( a ) 2 - d 网孔；( b ) i l l i a c 网孔；( c ) 2 - d 环绕 ( c ) 山东师范大学硕士学位论文 ( 4 ) 星形拓扑结构( s t a rt o p o l o g y ) 星形结构“”是指每一个远程节点都通过一条单独的通信线路，直接与中心节点连接。即 中心节点与每一个远程节点之间都是采用点一点连接方式，中心节点是其它节点唯一的中 继节点，如图1 5 ( b ) 所示，这种结构使用中心节点与网络中其它节点通信，采用集中控制 的方式，因此又称为集中式网络。一个需要通信的设备把数据传输给中心节点，然后中心 节点再把数据送往目标节点。 星形结构具有如下特点：a ) 功能高度集中。整个网络的处理和控制功能，都高度地集 中在中心节点，这样的系统容易构造、便于管理，但存在着潜在的不可靠性。中心节点易 成为系统的“瓶颈”，且一旦中心节点出现故障将直接导致整个系统的崩溃；b ) 网络延迟小， 传输误差低：c ) 单信息流通路径。每个终端通常只有一条信息通路到达中心节点，反之亦 然。因而，不存在路径选择问题，但无疑也是影响网络可靠性的一个因素：d ) 线路利用率 低。每条线路只连接一台终端，使该线路利用不充分；e ) 可扩充性差。星形网络受硬件和 软件功能的限制，致使其可扩充性差、成本高、资源共享能力也较差。目前，有许多应用 采用该拓扑结构，如l a n ，a t m 。 ( 5 ) 树形拓扑结构( t r e et o p o l o g y ) 在实际构造一个较大型的网络时，往往采用多级星形网络，将多级星形网络按层次方 式排列，即可形成树形网络。网络的最高层是中央处理机，最低层是终端，而其它层次可 以是多路转换器、集中器或计算机。树形结构是分级的集中控制式网络，与星形结构相比， 它的通信线路总长度短，成本较低，树可划分为子树，节点易于扩充，寻找路径比较方便， 多个终端共享一条通信线路，线路利用率较高。但在任何一对节点间存在惟一的路径，因 此，不存在容错能力，即除了叶节点及其相连的线路外，任意节点或其相连的线路故障都 会使系统受到影响。树的一个优点在于它能很容易地支持一个节点对多个节点的广播和组 播通信。 ( a ) 1 ( c ) 图1 5 树形连接 ( a ) - - x 树；( b ) 星形连接；( c ) 二叉胖树 树形结构中最常见的是二叉树，它除了根节点和叶节点之外每个内节点只与其父节点 5 坐查堑堇查堂堡主堂些堡苎 和两个子节点相连，故也称为三近邻连接。如图1 5 ( a ) 所示，显然节点度为3 ，对剖宽度 为1 ，直径为2 ( l o g nl 1 ) ( n 为树的总节点数) 。为了减小直径，可使用x 一树，将同级的 兄弟彼此相连。如果尽量增大节点度为n 一1 ，则直径缩小为2 ，此时就变成了如图1 5 ( b ) 所示的星形网络，其对剖宽度为l 2l 。 ( 6 ) 超立方拓扑结构( h y p e r c u b e ) 一个n 维超立方网络包含2 “个节点，并且每个节点与n 条边相连。每一节点用唯一的n 位二进制地址来标识，两个节点是互连的当且仅当它们的二进制地址中仅有一位不同。超 立方是一种高度并行、容错能力极强、具有递归结构的网络拓扑。它具有优良的拓扑特性 如，对称性、高连通性、容错性等。同时，许多其它类型的拓扑，如环、m e s h 、树等在多 数应用中都能有效的嵌入到超立方网络中【2 。 由于超立方拓扑的这些优势，在并行计算领域，它被广泛用于构建多处理机系统( m p s ) 组成的高性能计算平台 2 ”，是并行计算理论研究的基础网络结构。因而对基于超立方互连 网络的路由研究一直都没有f a n 2 0 , 2 2 , 2 3 。超立方网络已成为并行计算机通信系统中最受青睐 的互连网络之一。 同时超立方拓扑结构还常用来设计不同的商用多处理机系统。许多商用系统如 c o n n e c t i o nm a c h i n e ，n c u b e ，a n di p s c 2 4 , 2 5 , 2 6 】都采用超立方作为其根本的网络拓扑。如图 1 6 所示是一个4 维超立方网络。 图1 64 维超立方网络 ( 7 ) 全连接拓扑结构 在全连接拓扑结构中，每一对设备间都有直接的连接，如图l7 所示。 图1 7 全连接 这是一种极端的方案。由于不再需要竞争公用线路，通信变得非常简单。任意两台设备 可以直接通信，通信速度快。然而，每一对设备直接连接必然使费用增加、灵活性较差， 如n 个节点的全互连网络，若增加2 个节点，则必须增加n 条线路? 而且，肯定有很多连 6 坐堡堕蔓查兰堡主兰垡堕苎 接得不到充分利用。如果两台设各间很少通信，那么它们之间的物理线路的利用率就相当 低。一个更经济的解决方案就是不让这两台设备直接连接，去掉这些低效率的通信线路。 只有每个站点都要频繁发送信息时才使用这种方法。它的安装也复杂，但系统可靠性高， 容错能力强。 1 3 2 动态网络 ( 1 ) 总线( b u s ) 总线结构是指各工作站和服务器均挂在一条总线上，各工作站地位平等，无中心节点 控制，公用总线上的信息多以基带形式串行传递，其传递方向总是从发送信息的节点开始 向两端扩散，如同广播电台发射的信息一样，因此又称广播式网络，如图i 8 所示。各节 点在接收信息时都进行地址检查，看是否与自己的工作站地址相符，相符则接收该信息。 总线型结构的特点是，结构简单，可扩充性好：当需要增加节点时，只需要在总线上 增加一个分支接口便可与分支节点相连，当总线负载不允许时还可以扩充总线；使用的电 缆少，且安装容易；使用的设备相对简单，可靠性高：维护难，分支节点故障查找难。 ；一开关点 图1 9 交叉开关网络， 对于具有分布式控制的交叉开关，每个开关点可以包含4 种状态，如图i 1 0 所示。在 图i 1 0 ( a ) 中通过开关点的行输入允许访问相应的输出，而从上面发出的、访问同一输出的 输入请求被阻塞。在图1 1 0 ( b ) 中，上面发出的输入请求允许访问输出，通过开关点的行输 入不请求同一输出并可以传向其他的开关。在图1 1 0 ( c ) 中，从上面发出的输入请求允许访 7 些查堕蔓奎兰堡主兰堡望苎 问相应的输出，但是通过开关点的行输入也请求同一输出，所以被阻塞。图1 1 0 ( d ) 所示的 状态只用于要求交叉开关支持组播的情形。 v l s i 的发展允许几千个开关集成到一个芯片里。但由于v l s i 芯片引脚数目的限制， 较大的交叉开关很难集成到单个芯片里。因此，大的交叉开关可以分成多个小的交叉开关， 每个小的交叉开关使用个芯片。这样，一个n x n 的交叉开关可以用( n n ) ( n n ) 个n n 的交叉开关来实现。 ( a ) 图1 1 0 开关点的4 种状态 ( 3 ) 多级互连网络( m u l t i s t a g ei n t e r c o n n e c t i o nn e t w o r k ，m i n ) 多级互连网络通过一定级数的开关连接输入设备和输出设备，每一个开关都是一个交 叉开关网络。开关级数和级之间的连接模式决定了网络的路由能力。 多级互连网络最初是为电话网提出的，后来用于阵列处理机。在这些情况下，由中央控 制器建立从输入到输出的路径。当输入和输出的数目相等时，每个输入向一个输出同步传 输消息，每个输出恰好从一个输入接收消息。这种单播通信模式可以用输入地址的排列来 表示。阵列存储通常被曲解为允许无冲突访问，网络被用于访问期间对阵列的还原。这些 网络也瓢以使用输入多于输出的配置( 集中器) ，反之亦然( 扩展器) 。另一方面，在异步多 处理器系统中，集中控制和排列路由是不可行的。在这种情况下，需要路由算法建立m i n 跨级路径。 凸 笑日 师 【a 舳b a 轴b i s c l 【a 舳b 开关级0 a 灿b a 舳b i s c 2 a 灿b 开关级1开关级n 一1 图1 1 l 多级互连网络 输 出 端 根据两个相邻级之间所采用的互连机制和级的数目的不同，提出了很多种m i n 。m i n 有 利于构造有几百个处理器的并行计算机并已用于某些商用计算机。 争 孛争审 嚣：b 山东师范大学硕士学位论文 1 4 光互连网络 1 4 1 光互连的兴起及研究意义 当今，正是科技和经济飞速发展的信息时代，计算机在信息的获取、传输、处理和存 储中起了重大作用，而随着现代科技发展和社会需要的扩大，对计算机的要求越来越高。 随着计算机运算速度的进一步提高，芯片集成度的提高，使用导线进行芯片一芯片、处理 器一处理器、系统一系统之间的连接，不仅存在着“瓶颈”效应、运算速度有限、时钟歪 斜、互连带宽受限及串音等问题，而且从工艺上也是无法解决的。 、 光由于其并行、高速和可在空间交叉互连等特点，在信息处理中与计算机图像处理互 为补充，具有独特的优越性，受到人们的极大重视。在光计算系统中，由于它以光波作为 信息载体的信息处理技术，可以克服电子计算机串行处理中的以上种种限制。可采用自由 空间体互连实现对数据和信息的并行传输和处理，克服电子计算机中的“瓶颈”效应。光 在介质或自由空间中传输的高速性使得光计算系统中不同光路的信号传输时间差减小，从 而使光计算系统无时钟歪斜问题，也无r c 滞后效应问题。光波的空间域及时间域带宽都很 高，从而可达到巨大的信息和很高的信号重复频率。因此，无论运算和处理的信息量还是 系统运算速度都可以大大提高，使计算及处理技术进一步适应目前高科技信息社会发展的 需要。由于光子信号没有电荷，光子流不感生磁场，因此无电磁干扰问题，从而提高了计 算系统的抗干扰能力，提高了运算的准确性和稳定性。光计算的研究不仅是为新一代全光 计算机的实现作技术准各，探索各种可能的体系结构，并对光学逻辑元件质量改进提出指 导性意见。光计算的研究包括适合光学并行性的算法、原理及实现途径，光逻辑开关、光 互连结构汲光学系统等方而，其中光互连结构是光计算的重要组成部分。 。“ 前面所述的光计算的优越性，都是通过其互连结构的特点体现出来的，是由于光互连 取代电互连的结果。在大规模的数字并行计算及处理系统中，互连既是传输和交换信号的 途径，又是完成数学关系计算和处理数据的基础。在光计算中。核心内容不是逻辑运算， 而是互连网络的构成。因此，在光计算的研究中，光互连占有极其重要的地位。随着光计 算的研究和发展，光互连的研究也越来越深入。一方面，以直接取代电子计算机中某些电 子互连为主要日标的光互连结构和技术得到了发展，并且得到了应用，如超大规模集成电 路( v l s i ) 中的全息光互连等 2 7 - 3 3 】；另一方面，随着新型的光计算处理单元及系统结构的研 究和发展，与之相适应的光互连网络及结构也将随之产生。随着对光互连研究的不断深入， 人们对研究光互连的意义和前景及山它决定的光计算发展前景有了更进一步的认识。尤其 在近十几年的发展中，光互连作为光计算领域的一部分，己经基本上形成从理论、结构到 技术的系统学科。 光互连网络( o p t i c a li n t e r c o n n e c t i o nt i e t w o r k ) ，又称为i p 优化网互连网络或i po v e r o p t i c a l 网络，是数据网络，它的低层使用光传送网作为物理传输网纠3 4 】。在数据网络中， 它的组成设备主要是a t m 交换机、路由器等；在光传送网络中，它的组成设各主要是w d m 终端、光放大器以及光纤等；而在光互连网络中，高性能的数据互连设备( 如交换机和路由 器等) i 爵过光网络技术互连，这些设各既可能直接连接在光纤上，也可能连接在向各种客户 q 山东师范大学硕士学位论文 提供光波长路由的光网络层上。这里的客户包括数据互连设备和s d h s o n e t 网络单元。在 这两种情况下，交换机或路由器可以充分使用光纤或光波长的容量，对数据分组或信元进 行复用。 光互连网络的协议模型如图1 1 2 所示，光互连网络不致力于研究数据网络或光网络内 部的问题，而是致力于数据网络与光网络之间的互操作或兼容性问题的研究。 三 互 三 三 巨叵巨回 至 三 w d m 光网络 物理光纤网络 1 4 2 光互连网络的参考模型 图1 1 2 光互连网络的协议模犁 光互连网络的分层模型如图1 1 3 所示，它包括数据网络层、光网络层和层间适配和 管理功能。数据网络层提供数据的处理和传送，光网络层负责提供传送通道，层间适配和 管理功能用于适配数据网络和光网络，使数据网络和光网络相互独立。 幸嚣申 光网络 图1 1 3 光互连网络的分层模型 i p i p 适配 光通路 w d m 光复用段 w d m 光传输段 图1 1 4i po v e rw d m 的协议堆栈 坐查堑蔓查兰堡主堂垡丝奎 光互连网络的协议模型如图1 1 4 所示，包括客户层( i p 层) 协议、i p 适配层协议、光通 路协议以及w d m 光复用段、w d m 光传输段等。客户层协议使用i p v 4 ，i p v 6 等协议，i p 适 配层协议用于i p 多协议封装、分组定界、差错检测以及q o s 控制等功能。光通路协议包括 数字客户适配和带宽管理( 比特率和数字格式透明) 、连接性证实等功能。光复用段功能包 括带宽复用、线路故障分段和保护切换以及其它传送网维护功能。光传输段功能包括高速 传输( 色散补偿) 、光放大器故障分段等功能。 1 4 3 光互连网络的分类 从结构来看，可分为：芯片内的互连、芯片之间的互连、电路板之间的互连和计算机 之间的互连。从互连所采用的信道来看，可分为：光纤互连、波导互连、自由空间互连等。 各种结构有各自的信息处理功能p ”。 ( 1 ) 自由空间光互连技术口6 j 通过在自由空间中中传播的光束进行数据传输。适用于芯片之间或电路板之间这个层 次上的连接，可以使互连密度接近光的衍射极限，不存在信道对带宽的限制，易于实现重 构互连。该项技术是光互连技术中最具吸引力的。 早期的研究主要集中在如何利用技术构成m i n ( 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 ) 、c r o s s b a r 和m e s h 等互连网络，如何在传统二维平面结构电子插件的三维空间上 实现光通信，而目前的研究已经深入到v l s i 器件的内部。由于器件尚不能达到实用化，所 以仍处乇研究阶段。薯攀 目前发展最快的多级光互连交换系统是自由空间光互连交换网络。这主要有两个方而 的原因：_ 是自由空间光互连交换网络除了具有一般的光互连所共有的优点外，还具有易于 实现三维网络、互连数大、互连密度高、无接触互连等优点：二是由于实现自由空间光互 连交换网络系统所需要的开关节点从阵列器件和二元微光学器件的发展很快，均己接近实 用化。 ( 2 ) 波导光互连技术【 ” 通过沿光波导传播的光束进行数据传输。该技术的研究进展十分迅速，己经进入市场， 部分商用计算机己采用了简单的波导光互连技术，如c r a y t 9 0 己采用集成光波导h 树进行 时钟信号分布。 波导互连可以提供高密度互连通道，适用于芯片内或芯片之间这个层次上的互连，采 用集成光源和探测器，由集成光路来完成连接，这一种互连目前还不很成熟。 最成熟的光波导是光纤，点一点的光纤互连技术己有商品出售。光纤互连适用于电路 板之间或计算机之间这个层次上的连接，借助于光通中的有关先进技术，己进行了好几种 互连方案的实验工作。光纤互连具有频带宽、无电磁干扰、可高密度并行行连接、多信号 和多扇出、传输速度快、不需接地等优点。光纤的波分光交换技术在m p p 系统的互连网络 中有自动寻径功能，具有诱人的前景。 美国光纤通道协会( f c a ：f i b e rc h a n n e la s s o e i a t i o n ) 针对当前光互连技术和光通信 技术的发展，制定了一系列的光纤通信标准，对光纤在光纤通信和计算机互连中的使用制 定了全面的规范。这些标准的制定，全面推进了光纤光互连技术在计算机中的使用。 l l 些垄堕鎏查堂堡主兰垡笙奎 1 4 4 光互连网络的研究热点 ( 1 ) 光源：在光互连中，光源主要用于携带数据的光信号的产生。早期的光源研究主要 基于外部光源，研究光源分束技