（计算机软件与理论专业论文）一种新的并行计算机网络——gpn网络.pdf

山东师范大学硕士学位论文 摘要 互连网络的性质对髓个网络的性能起着决定性作用。然而。由于互连网络设计是一个 多目标最优化问题所以很难找到种互连网络适合所有并行系统。因此已经有许多的 互连网络被提出和应用。 p e t e r s e n 图作为一个节点度为3 、直径为2 的强正则图，正好满足了互连网络对小节 点度和短网络直径的苛刻要求。因此p e t e r s e n 图在构造瓦连网络模型附被广泛应用和借 鉴。但是p c t e r s e n 图仅有1 0 个节点，在构造并行机系统时网络规模受到很大限制，因此 不能直接应用设计互连网络。 本文基于p e t e r s e n 图提汜种新的互连网络一g p n ( g e n e r a l i z e dp e t e r s e ng r a p h n e t w o r k ) ，并深入地分析了这种互连网络的性质，简记为g p ( n ，目，其中n 3 1 k sl ( ”j 。与其他所有在p e t e r s e n 图的基础上构造的并行计算机互连网络模型相比， g p ( n ，七) 具有简单的拓扑结构。 所作的主要工作是： ( 1 ) 通过分析g p ( n ，句的拓扑性质知道了该网络中每个节点的度均为3 对任意不 小于6 的币整数疗，g p ( n ，女) 网络直径的上限是【形2 t j + l k 2 j + 3 。并给出了几类g p ( n 的网络的精确网络直径：对任意不小予3 的正整数d i a m ( g p ( i ：, 啪= i + i 。在极限意 义下，当总节点个数相同时，g p ( i2 , i 1 的网络直径仅根当于2 一dm e s h 的三分之一，相当 于2 一dt o r u s 网络直径的三分之二。对任意不小于2 的正整数m 。 d i a m ( g p ( 2 “，2 ”) ) = 2 + h 实质上，g p ( 2 “，2 “) 是g p ( i2 ，f ) 的一个特倒对任意正整数 m ，d i a m ( g p ( 22 ”1 ，2 ”) ) = 昙2 ”+ 1 。在极限意义下。当总节点个数相同时g p ( 22 ”1 ，2 “) 的 z 网络直径仅相当于2 一dm e s h 的八分之三，相当于2 一dt o m s 网络直径的四分之三。通 过和最流行的2 dm e s h 、2 - d t o r u s 比较得出结论，这几类a t ( n ，女) 有更短的网络直径。 ( 2 ) 路由算法作为互连网络最基本的操作也是影响并行计算机通信效率的重要因素。 因此本文设计了互连网络g p ( i 2 , j ) 上的路由算法，主要有o n e t o o n e 、o l l e t oa l l 、a l l t oa l l 等，并对这几种路由算法作了性能分析。这些算法实现简单，有比较小的通信次数，分 别是： o n et oo n e 路由算法在最坏的情况下，所需要的时间步是：i + 1 。而且按这种方式 的单播路由算法是最优的。o n e t oa l l 路由算法，当始发节点在c 上时所需要的时间步 是：2 l f 2 j + 3 。始发节点在c i 上时所需要的时间步是：2 l i 2 j + 2 。a l l t oa l l 通信 山东师范大学硕士学位论文 所需要总的时间步是：4 i 一2 。 ( 3 ) 全光环网络是最重要的全光网络之一。许多流行的互连网络都可以嵌入全光环网 中实现。因此在全光环网络上实现了g p ( n ，妨网络的波长分配方法。最后给出任意的 g p ( n ，女) 网络嵌入到全光环网络中需要总的波k 数仅为：k + 2 + ( n m o d k ) 。 关键词：并行计算；互连网络：直径：路由算法；网络嵌入；波长分配 分类号：1 p 3 9 3 些查堕里查兰堕主兰篁堡茎 一 a b s t r a c t i n t e r c o n n e c t i o nn e t w o r k sa l ef u n d a m e n t a lp a r t so fp a r a l l e lp r o c e s s i n gs y s t e m s h o w e v e r , i ti sv e r yd i f f i c u l tt of i n ds o m ek i n d so fi n t e r c o n n e c t i n gn e t w o r k st os u i tw i t he v e r yp a r a l l e l p r o c e s s i n gs y s t e m ，b e c a u s e i ti sa m u l t i t a r g e to p t i m i z a t i o np r o b l e m f o r d e s i g n i n g i n t e r c o n n e c t i o nn e t w o r ks y s t e m st h e r ea r em a n yk i n d so fi n t e r c o n n e c t i o nn e t w o r k sh a v eb e e n p o s e da n dd e s i g n e d p c t e r s e ng r a p h ，3 - r e g u l a ra n d2 - d i a m e t e r , i ss u i t a b l et ot h ei n t e r c o n n e c t i n gn e t w o r k s s t r u c t u r e ，s oi ti sw i d e l ya p p l i e da n dm o d e l e di nd e s i g n i n gi n t e r c o r m e c t i o nn e t w o r k s b u t p e t e r s e ng r a p hc a nn o tb ea p p l i e dt od e s i g ni n t e r c o n n e c t i o nn e t w o r k sd i r e c t l y , b e c a u s eo ft h e l i m i t e ds i z eo f n o d e s ，10 b a s e do np e t e r s e ng r a p h an e wi n t e r c o r m e c t i o nn e t w o r k s ，g p ( n ，袖 f o rn 3a n d i k 蔓卜刎i sp r e s e n t ，a n dt h ep r o p e r t i e so fg p ( n ，七) a r ed i s c u s s e d c o m p a r e dw i t ht h e o t h e ri n t e r c o n n e c t i o nn e t w o r k sw h i c ha r eb a s e do np e t e r s e ng r a p h ，g p ni ss i m p l ei nt o p o l o g y t h es c a l eo fg p ( n ，幻i sd e c i d e db yt h ep a r a m e t e r ，a n dt h ec o n n e c t i o ns t y l ei sd e c i d e db y p a r a m e t e rk i nt h i sp a p e r , a l lt h ew o r k sa r ef o l l o w i n g ： ( i ) b a s e do nt h ep e t e r s e ng r a p h ，an e w i n t e r c o n n e c t i o nn e t w o r k s ，g p ( n ，t ) ，i sp r o p o s e d t h en o d ed g r e ei ng p ( n ，i s3 ，a n dt h ed i a m e t e ri sn o tg r e a t e rt h a n1 2 k j + k 2 j + 3 f o r n 6 i na d d i t i o n , s o m ec o n c l u s i o n sa b o u td i a m e t e ro f s e v e r a lk i n d so f g p ( n ，a r eo b t a i n e d t h ed i a m e t e ro fg p ( i 2 ，i ) i si + 1f o ra l lf 3 i fe a c hk i n do f n e t w o r kh a ss a m en u m b e r o f n o d e s ，g p ( i2 ，f ) sd i a m e t e ri s1 1 3o f 2 一dm e s h sa n d2 3o f 2 一d t o r u s sw h e nt h en u m b e r o f n o d e s i s l a r g ee n o u g h t h ed i a m e t e r o fg p ( 2 2 m , 2 “) i s2 ”+ l f o ra l l m 2 t h e d i a m e t e ro fg p ( 2 2 “，2 ”) i s - 2 ”+ 1 i fe a c hk i n do fn e t w o r k sh a ss a m en u m b e ro fn o d e s ， g p ( 2 2 “，2 8 ) sd i a m e t e ri s 3 8o f2 一dm e s h sa n d3 4 o f2 一dt o r u s si ft h en u m b e ro f n o d e si sl a r g ee n o u g h b ya n a l y z i n gg p ( n ，t ) st o p o l o g ya n dc o m p a r e dw i t ht h ed i a m e t e r so f 2 - dm e s ha n d2 - dt o r u s ，i ti sk n o w nt h a tg p ( n ，k ) h a ss i m p l et o p o l o g ya n ds m a l ld i a m e t e r s ( 2 ) a sab a s i co p e r a t i o no fi n t e r e o n n e c t i o nn e t w o r k s ，t h er o u t i n ga l g o r i t h mi sa l s o a l l i m p o r t a n ta s p e c to na f f e c t i n gt h ee f f i c i e n c yo fp a r a l l e lp r o c e s s i n gc o m m u n i c a t i o n i n t h i sp a p e r , s o m ek i n d so fr o u t i n ga l g o r i t h m so ng p ( i2 , f ) a r ed e s i g n e d ，啊h i c hi n c l u d ep o i n t - t o - p o i n t l i l 山东师范大学硕士学位论文 r o u t i n g ，o n e t o a l lr o u t i n ga n da l l t o a l lr o u t i n g t h e s ea l g o r i t h m sa r ee f f i c i e n c y ：i nt h e p o i n t - t o - p o i n tm u t i n ga l g o r i t h m ：i ti sn e e di + ls t e p s ，e v e ni n t h ew o r s ts i t u a t i o n s i nt h e o n e t o a l lr o u t i n ga l g o r i t h m ：i ti sn e e d2l f 2 j + 3s t e p sw h e ns o u r c ep o i n to nc n o t h e r w i s e ，i ti s n e e d2 l i 2 j + 2s t e p s a l l t o - a l lr o u t i n ga l g o r i t h m ：i ti sn e e d4 i 一2s t e p s ( 3 ) t h ea l lo p t i c a lr i n gn e t w o r k si so n eo ft h em o s ti m p o r t a n to p t i c a ln e t w o r k s m a n y p o p u l a ri n t e r c o n n e c t i o n n e t w o r k sc a l lb ee m b e d d e di na l l o p t i c a lr i n gn e t w o r k s t h e w a v e l e n g t ha s s i g n m e n ta l g o r i t h m sa r ep r o p o s e dw h e ng p ( n ，k ) a r ee m b e d d e di nt h ea l lo p t i c a l r i n gn e t w o r k s a tl a s t ，t h ew a v e l e n g t ha s s i g n m e n tn u m b e r si sk + 2 + ( n m o d k ) f o r e a c hg p ( n ， k 1w h e ni ti se m b e d d e di na 1 1o p t i c a lr i n g k e yw o r d s ：p a r a l l e lc o m p u t i n g ；i n t e r c o n n e c t i o nn e t w o r k s ；d i a m e t e r ；r o u t i n ga l g o r i t h m n e t w o r ke m b e d d i n g ；w a v e l e n g t ha s s i g n m e n t c l a s s i n c a t i o n ：t p 3 9 3 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得 ( 注：如没有其他篱要特别声明的，本栏 可空) 或其他教育机构的学位或证书使用过的材料。与我一一同1 作的同志对本研究所做的 任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名： 位彩瑾 导师签字：孑发彳z 学位论文版权使用授权书 本学位论文作者完全了解芏撞有关保留、使用学位论文的规定，有权保整弗向因家有 关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权兰燕可以将学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 导师嫁3 像彳z 一 签字日期：2 0 0f 年j ，月7f j 签字目期：2 0 0 乞年月7 9 曰 山东师范大学硕士学位论文 第一章引言 随着计算机在社会各个行业及各个层面应用的广泛与深入，需处理的数据量越来越 大。计算机早己由处理简单的数值计算发展到文字、图形、图像、声音的综合处理。而且 要求数据处理更加及时、准确。尽管处理器的性能平均每3 年就翻一番，但仍然赶不上应 用的脚步。仅靠单机处理大量数据实践证明是不现实的。单机技术发展的限制和与日俱增 的需求之间的矛盾决定了采用多台计算机并行处理数据是未米高性能计算机发展的趋势。 在高性能并行计算机系统中，用丁实现处理机( 或功能部件) 之间相互连接的是：按一 定拓扑结构和控制方式构成的互连网络。互连网络决定了并行系统连接的模式、算法，直 接影响系统的同步和通信速度，是并行处理系统的核心组成部分，直接决定整个系统性能， 对整机系统的效率起着举足轻重的作用。 本章首先介绍了并行计算机系统、互连网络，其次介绍了现在流行的互连网络拓扑结 构，最后引出本文的研究对象，种新的互连网络拓扑结构g j p ( ”，d ，并且针对g p ( n ， 女) 结构以及性质简要介绍了本文的主要内容和所做工作。 1 1 并行计算机系统 当今，采用由多台处理机互连构成的高性能并行计算机处理大规模数据是各行各业解 决科技、工程以及科学研究等课题的重要工具。比如在石油地质勘探、气象分析、药物研 究、分子原子结构分析、宇宙演变模拟等领域都有广泛应用。因此并行处理系统以及相关 问题是当今计算机科学研究的前沿问题。 并行计算机的发展基本上可以分为四个阶段：阵列机的研制与发展、向量多处理机系 统的研制与发展、基于共享存储的多处理机系统、基于分布存储的大规模并行处理系统 f m p p ) 。一般的并行机结构包括：处理器一存储器节点、网络接1 2 1 f n e t w o r ki n t e r f a c e ) 、互 连网络( i n t e r c o r m e c t i o nn e t w o r k ) 。这三部分分别负责：本地任务处理，协作请求，启动 终止数据传输等；将处理器一存储器节点连接到互连网络，组织数据包的格式，构造路由 和控制信息；路由选择、交换策略和流控制的数据传输。 而在使用和实验中研究者认识到，在针对海量数据的计算过程中，并行机的性能和成 本更多地依赖于通讯而非节点的计算能力。因为并行计算机在采用通信系统来连接处理 器、存储器、磁盘和各种外围设备时，传统的计算机网络互连方式并不适用于并行节点之 间频繁的数据传递。因此通信系统成为并行计算机提高性能的关键。提高通讯效率的重要 技术是网络如何互连，即各个处理器之间如何连接才能发挥最大效能，降低构建网络成本。 因此互连网络是并行机的最关键组件之一，它经常能够决定整个系统的性能。 山东师范大学硕士学位论文 1 2 互连网络 互连网络主要是指各种组件集合和通信链路的集合。组件是指处理机以及各种外围设 备。组件与通信链路之间是通过路由 发备连接的。互连网络主要由四个参数表征：拓扑结 构，路由算法，交换策略和流撮控制机制。 拓扑结构：拓扑结构就足指互连网络组件与组件之间的相互连接。它可能是规则的， 如二维的网格：也可能是不规则的。比如基于开关的不规则拓扑网络。决大多数并行机采 用高度规则的网络。网络的拓扑结构决定了每个节点的通信链路数，消息或数据包的传输 路径以及到达目的节点的远近。拓扑结构是互连网络，乃至整个并行计算机设计的第一步。 对整个系统的性能起重要的作用，而且也是实现各种通信协议的基础。 路由算法：路由算法决定了数据包在网络中的通过路径，是互连网络最主要的功能之 。它的优劣直接影响网络整体的性能和效率。因为到达目的节点的路径往往不止一条， 好的路由算法可以寻找到通信距离相对较短、不拥挤的路由策略，减少在中间节点的排队 等待时l s j ，减少通信所需的时间。 交换策略：决定了一个消息中的数据如何通过它的路径进行传输。交换策略有两种， 一种足电路交换，在这种交换过程中，保留由源节点到目标节点的路径直至消息传输完毕。 还有一种是包交换，是指消息被拆分为系列包，每个包中都包含序列信息和路由信息， 它们按照各自的由源节点目的节点的路径传输。 流量控制机制：可以通过链路进行传输的最小单元称为流篮控制单元。当对某一单元 进行传递时，如果两个或更多的单元同时使用同一网络资源，其中一个应该被放入缓冲区 或改变它的路由，甚至直接丢弃。具体如何处理决定于交换元件和通信系统的具体设计。 从理论上看互连网络最理想的拓扑结构是全互连结构，也就是网络中每个节点都与其 他任何节点相连。这样任意节点之间发生消息传递时不需要经过中间节点就可以直接通 信，最大限度的缩短了通信延迟。但是在实践中这种互连模式是不可取的。假设采用全连 接的互连网络中总共有n 个节点，那么这个全连接的拓扑结构就要求每个路由器有n 条 通路，将大大增加网络连线的复杂度，增加构建互连网络的成本。另外，由于物理引脚数 目和可能的连线面积等都是有限的，并且难以扩充，所以全连接互连网络还受限于许多其 它硬件条件。 互连网络作为并行处理系统的主于网，其性质如何直接决定着整个网络性能的优劣， 互连网络可以决定最终并行计算机的许多重要特性。一个好的互连网络可以简化软件开发 难度，增加系统的可靠性，提高并行网络的可扩展性，降低物理布局的复杂度和构建系统 的成本。然而互连网络是并行计算机中唯一不可能用商品化部件来高效实现的子系统【l 】， 因此它的设计对并行计算机的性能提高和成本降低都起着至关重要的作用。 2 山东师范大学硕士学位论文 1 3 常见的互连网络 进一步提高并行计算机的性能价格比依赖于对新型互连网络的设计及其内在性质的 研究。由于最初设计网络的驱动因素不同，互连网络的设计也就成了一个多目标最优化问 题。根据不同使用者的不同要求，结合图论的知识以及网络技术的限制，各式各样的互连 网络结构陆续被提出。提出的这些网络各有各的优缺点，适用于不同情况，但真正付诸实 施的只是极少数。因为互连网络拓扑的选择不但要考虑系统的性能，更要考虑构建的成本。 只有那些高性能低成本的互连网络才会被人们使用和认i t r 。下丽这些都是比较流行的互连 网络。丰日对于其它的互连网络，这些网络拓扑结构简单，而且性质基本上已为人们所熟知。 吁连网络一般以有规律的模式连接，而且这些网络拓扑往往有比较好的数学性质。为 了便于描述，互连网络常用一个图g = ( n ，e ) 来表示，图中顶点n 表示处理机节点的集 合，边e 表示通信链路的集合。双向通道_ 口，以用一条双向边或无向边来表示，单向通道 可以用带方向的弧来表示。这样，研究网络的拓扑结构也就归结为研究图的拓扑性质。虽 然图中不能表示出物理实现的细节问题，但是它有助于研究网络的属性。比如：节点度、 寅径、规整性、对称性等重要的属性从图中直观的就可以知道。 1 3 1 线性阵列、环 最简单的网络就是线性阵列。线性阵列足由连续编号的n 个节点用双向链路连接构 成的。其直径为n - 1 。这种嘲络路由简单，任何节点之间只存在唯一条路径，凶此这 种网络没有容错能力。对分带宽为1 。在n 个节点的线性阵列中有n 一1 条链路所以很 容易在0 ( n ) 的空间内用短导线布线。 卜1 卜_ _ 卜l 图1 1 线性阵列、环 将线性阵列的两端简单连接就形成了环，网络性能得到优化，直径是ln 2i 对分带 宽2 。而且在有一条链路出故障的情况下，可以降低性能工作。由于其简单的环形拓扑结 构，低廉的网络成本和简单的路由策略，环网被应用到许多早期的局域网络中。例如f d d i ， 光通道仲裁环( f i b e rc h a n n e la r b i t r a t e dl o o p ) 和可扩展的一致接口( s c a l a b ec o h e r e n t i n t e r f a c e ( s c i ) ) 等【2 】。 虽然环和线性阵列从实际意义上讲都是不可扩展的一维网络，但他们的概念十分重 要。而且环因为其简单的路由方式和硬件复杂度低，使得它在局域互连网络中十分流行， 还经常用作构造模块。在构建现代的互连网络时，这两种网络很少再被使用是因为它们的 致命弱点：在节点规模比较大时，网络直径太大，使得通信延迟难以接受。随着全光网络 1 山东师范大学硕士学位论文 的出现，波分复用技术( w d m ) 的发展，光环网络又重新引起人们的重视。【8 】 1 3 2 多维网格、多维花环 将线性阵列和环推广到更高的维数二维、三维、甚至更高的维数，自然就得到了 多维网格( n dm e s h ) 、多维花环( n d t o r u s ) ，这里的n 表示维数。这两种结构可以说 是最流行的网络拓扑。它们在网络直径和对分带宽以及容错性上较线性阵列和环都有很大 的提高。它们都是严格正交的，可以用节点在n 维空间中的坐标作为节点的编号。因此路 由简单，可以使用硬件商效地实现路由算法。 在实践【 i 最常采用的还是低维网格和花环。目前许多基于消息传递的并行体系结构都 采用类t o m s 的体系结构，像2 一dm e s h ，3 - dc u b e 等等。例如，i n t e lp a r a g o n ，d a w n i n 9 3 0 0 0 采用2 一dm e s h 网络拓扑，c r a y t 3 d 采用3 一d l o t u s 结构，m i t 的j - m a c h i n e 等采用3 d m e s h 结构。 图卜2 二维网格、二维花环 相对于现在设计的其他互连网络多维刚格、多维花环的直径还是比较大，所以在不增 加节点度的基础上减小刚络直径仍然是设计者的追求目标。 1 3 3 树 多维网格的直径与总的节点个数n 之间存在这样的关系：q - d ，其中m 表示网格的 维数。比如二维网格的直径是万。而树作为非常简单的种拓扑结构，它的直径却很小， 是按对数上升。常用的是二叉树。叶子节点度是1 ，根节点度为2 ，其他节点度是3 。当 只把处理器节点安排在叶子上时，直径为2 1 0 9 2 n 。这种拓扑结构中除了根节点，每个 节点都只有一个父节点，所以在树中不存在圈。如果所有的叶节点到根节点的距离都相等 这棵树就可称为平衡树。 4 山东师范大学硕士学位论文 a公 昔通二义树 平衡二义树 图1 3 扛f 形拓扑 在通信上，树的优点十分明显，虽规模扩大直径上升幅度很小。树的缺点也很突出： 因为节点的通信都要靠上层节点完成，所以越靠近根通信越繁忙。在根附近容易形成网络 瓶颈。仅靠增加带宽也很难解决拥挤问题。树还有一个潜在问题就是：越靠近根的链路需 要越长的导线。靠近根方向的链路长度通常随层数按指数增长。导线越长，决定网络周期 的线延迟也就越大。自然也就降低了通信效率。 1 3 4b u t t e r f iy 网络 树中存在的长导线问题在b u t t e r f l y 中可以得到部分缓解。因为在b u t t e r y 网络中存 在许多上层节点，不需要靠长导线把节点连到同一个根上。b u t t e r f l y 是另外一类交换网络。 这类网络是建立在2 * 2 交换开关的基础之上，由多个交换开关连接成不同的互连网络。在 b u t t e r f l y 网络中，任意的输入和输出都可以经过设置交换丌关建立连接。m o n s o o n 计算机 是采用b u t t e r f l y 互连嘲络构建的 3 】。 蛾嘲基本模块 1 3 5h y p e r c u b e 网络 图1 - 4 螺网基本模块、3 维蝶网 超立方体( h y p e r c u b e ) 互连网络是一个规整对称的网络拓扑。一个n 维超立方体含 有2 n 个节点，每一个节点的地址用i 位二进制数表示。对于任意的两个节点a 、b ，当 且仅当它们的海明距离是1 时( 即二进制编码地址中只有一位不同) ，两个节点之间才有链 路。因此，n 维超立方体中的每一个节点和n 个节点直接相连。它是具有2 n 个节点和f 1 2 n 1 条边的n 一正则图。对照多维花环仔细分析超立方体的结构会发现，超立方体本身就是一 山东师范大学硕士学位论文 个n 维2 元花环。 虽然超立方体实质上只是一个n 维2 元花环。但自从该网络被提出以后，就受到了 十分，。泛的关注。这是因为与其它互连网络相比，超立方体具有许多优越的性质如它具有 对数级的直径和最高连通度，有很好的容错性【4 】。因而在早期研制出了许多超立方体并 行机，比如c a lt c c h 的研究原型( s c i t z1 9 8 5 ) 、i n t e l 的前三代i p s c 机、三代n - c u b e 和 c m 一2 等等。但在较晚期的大规模并行机并没有采用超立方体网络，而是使用了低维的网 格。发生这种转变的主要原因是在实践中，要采用引脚度数尽可能大的的交换机来适配超 立方体，交换机度数的增加将会大大增加系统成本，也将造成引脚资源的浪费。 他1 ) 1 ，1 )( i ，1 )( 1 ，i ) 图1 _ 5 两个= 维超立方体可 句成个三立方俸 但从理论上说，超立方体仍然是种十分重要的互连网络，它给其它的网络设计提供 了许多新思路，也给评价网络优劣提供了好的参照。当节点度不再是构建网络的限制时， 超立方体很可能成为构建互连网络的首要选择。 除了上面所提到的这些基本互连网络，研究者还通过研究某些图的性质和对现有的互 连网络进行改进提出了多种互连网络。比如d e b r u i j n 网【5 1 ，星图( s t a r g r a p h ) 6 1 ，d c c 线 性同余图 7 】等。另外还有人提出以群论为工具设计互连网拓扑结构，这为互连网络的研 究提供了一种系统的代数方法。a k e r s 和k r i s h n a m u r t h y 利用一般的有限群构造出c a y l a y 图模型作为互连网拓扑结构，并得到了c a y l a y 图的一些性质。随后又根据对称群建立了 互连网络的对称群模型，其中具有代表性的是星图( s t a rg r a p h ) 。 p c t e r s c n 图作为一个节点度为3 、直径为2 的强正则图，j 下好满足了互连网络对小节 点度和短网络直径的苛刻要求。因此p e t e r s c n 图在构造并行计算机网络互连模型时被广泛 应用和借鉴。比如文献【l o 1 3 】提出了多种完全不同的基于p e t c r s e n 图的互连网络。 1 4 本文内容安排 本文基于p e t e r s e n 图提出一种新的互连网络g p n ( g e n e r a l i z e dp e t e r s e ng r a p h n e t w o r k ) 。g p n 的规模和连接方式主要是有两个参数n ，k 决定。1 1 决定了网络总的处理 6 山东师范大学硕士学位论文 机个数，k 决定了网络的连接方式。为了更精确简洁的表示出网络的大小和连接，在以后 的各个章节把g p n 表示为：g p ( n ，t ) 网络。本文对g p ( n ，作了深入细致的讨论。与其 他所有在p e t e r s e n 图的基础上构造的并行计算机互连网络模型相比，g p ( n ，七) 网络具有简 单的拓扑结构同时具有许多良好的性质。本文章节安排如下： 第一章绪论主要介绍了并行计算机以及互连网络的研究背景和意义，然后介绍了几 类主流的互连网络线性阵列、环、多维网格、多维花环、树、b u t t e r f l y 网络、超立方体， 并分析了他们的优缺点。 第二章本章给出了将爿j 到的术语和基础知识。首先介绍了图论和互连网络相关的术 语和概念，其次定义了本文的研究对象g p ( n ，女) 网络。 第三章主要讨论g p ( n ，n 应用到互连喇络时所具有的性质和直径。g p ( n ，七) 足3 正则图总的链路数是3 ”。虽然g p ( n ，女) 本身不是对称的。但是g p ( n ，女) 外圈上的节点 之间是对称的，内圈卜的节点之问也是对称的。对于大多数的g p ( n ， ) 都是哈密顿图， 当且仅当k = 2a n dn ；5 ( r o o d6 ) 时，不是哈密顿图。因为网络赢径是衡最一个网络好坏 的重要指标，因此本章用大量篇幅证明了g p ( n ，) 的直径与n ，k 之间的关系。得出了几 个重要结论：( i ) 对任意不小于6 的正整数n g t ( n ，七，网络直径【叫2 七j + l k 2 d + 3 。( 2 ) 对 任意不小于3 的正整数i ，g p ( t7 ，f ) 网络直径d i a m ( g p ( i 2 , f ) ) = i + i 。( 3 ) 当总节点个数相同时， g j d ( f ：j ) 的网络直径仅相当于2 一d m e s h 的大约三分之一，相当于2 一d t o m s 网络直径的 三分之二。( 4 )对任意不小于2 的正整数m ，g p ( 2 “，2 ) 网络直径 d i a m ( g p ( 22 2 ”) ) = 2 ”+ 1 。实质上，g p ( 2 2 m 2 “) 是g p ( i 2 , f ) 的一个特例。( 5 ) 对任意正整 数m ，o p ( 2 2 ”，2 ”) 网络直径d i a m ( g e ( 22 ”，2 ”) ) = 晏2 ”+ l 。( 6 ) 当总节点个数相同时， z g p ( 2 ：一，2 ”1 的网络直径仪相当于2 一dm e s h 的大约八分之三，相当于2 一dt o m s 网络直 径的四分之三。 第四章除了网络直径影响并行计算机的通信效率，路由算法作为互连网络最基本的 操作也是影响并行计算机通信效率的重要因素。合理的路由算法可以高效地完成节点之间 频繁的数据迁移、消息传递。另外，一个系统如果提供一些好的路由算法，也可以简化编 程。好的路由算法也是体现该拓扑结构良好性质的主要手段。本章主要对g p ( ia 。i ) 网络上 的一些基本路由算法进行讨论。有单播( o n et oo n e ) 、广播( o n et oa 1 1 ) 、多对多( a l lt oa 1 1 ) 等路由，并对这几种路由算法作了性能分析。 第五章因为全光网具有高带宽、信号透明、兼容性好、可靠性高等优点。从而可以 有效避免了由电子器件产生的“电子瓶颈”现象所以全光互连网络也成为并行计算机的 7 山东师范大学硕士学位论文 重要发展方向。全光环网络是最重要l i q 全光网络之一。许多流行的互连网络都可以嵌入全 光环网中实现。因此本章重点给出了在全光环网络上实现g p ( n ，) 网络的波长分配方法。 本章首先介绍了光网络的些基本知识。其次简要介绍了全光环网络。随后经过分析得出 g p ( i 2 f ) 嵌入到全光环网络中需要的波长数仅为i + 2 。g p ( i m ，i ) 嵌入光环网需要的波长数 仅为m + 2 。最后给出任意的g p ( n ，t ) 网络嵌入到全光环网络中需要总的波长数仅为： k + 2 + ( n m o d k ) 。 8 山宋师范大学硕士学位论文 第二章预备知识 建立高性能的并行计算机，不但滞要高性能的节点计算机，而且需要高性能互连网络 支簿。为了霞予互连鞲络懿磷究，遥鬻把互连秘终籀象为图来讨论。鲶瑾瓤番作图串豹顶 点，处理机之间的链路看作图的边。单向链路用带方向的弧来表示，被向链路用一条双向 孤或无自透来袭示。围踅对互逶鲻络馁矮豹研究也裁转纯为霹簋连黼终掰对应图豹菜魏数 学性质的研究。因为现在大部分的互涟网络部是使用双向链路( 比如全双 ：的通信模式) ， 所跌本文主要楚对筐臻双囱镶路静互遥耀络溅行讨淦，在浚裔特殊说溺瓣溏墩下，本文中 提到的瓦连网络均是双向链路，并且双向链路都用无向边来表示。 零章首先余绍了豳论和蠢连网络糖关豹术浯稻概念，其次定义了本文斡骈究对象 g p ( n ，女) ，并介绍了相关知识。 戳下考虑的图均为筒荜露壤图。文中来加浇臻的定义毒术语觅文献f 1 4 】。 2 。1 瀚论相关术语 一令嚣g 透露被定义麓g = v ( g ) ，e f g 羚。v ( g ) 和( g ) 分鼷淡示寅戳赣空璎轰集合及毒 限边集合。其中e ( g ) 的每个元索是v ( o ) 中顶点的无序对，称为g 的边。简记为e = ( “，v ) ， ”，。表示v ( g ) 巾不相同的任意慝接相连的两个顶点。l v ( g ) i 和i e ( g ) f 寝示图g 的节点个 数裒逡翡条数。连接条迭戆魏个矮点髂为关联豹或秘邻静。嚣苓辐邻瓣璎意攀l 蔓逶避路 径桐遵路径由边的序列组成。用符号可以记为：p ( 一，v 。) = ( v ，_ ) ，( v ，h ) ，( v ，v 。) ，( v 。 ) ， 路径的长度怒指该路径中边的条数，可以简诚为f p f 。比如在阁l 表示的p e t e r s e n 图中。顶 点封。剿琢之闻靛一条黪径是：( 1 , 1 0 ，鼯；) ，) ，该路径懿长瘦怒2 。 王意两个琰点之闻露在 的历羁路径中长度最小的路径，称为濒顶点阀的最短黪径。馁意顶点“到其它所有顶点最 短路径的最大值，称为顶点“的顶点直径。图中所有顶点的顶点直径中的最大值称为该豳的 直径。 程个图g 中，顶点x 的胰简记为d 。j ( x ) ，谯不会引起混淆的情况下，也可简记为d ( x ) 。 若鹜中每个节点豹度都等予k ，我靛称该图是靠芷羽鹜。对予强意懿一个妻- 委潮酶餐攀踅 g ，糟存在两个正整数五和a ，使得g 中的任意两个相邻的节点有五个获同的邻点，并鼠任 意两个不相邻的节点肖u 个欺同的邻点，那么该图g 称为是强正则图。 9 山东师范大学硕士学位论文 在个图中，如果存在一条路径包括所有的顶点，则该路径称为哈密顿路( h a m i l t o n 路) ，如果存在一个圈包括所有顶点，则该圈称为哈密顿圈( h a m i l t o n l 善1 ) 圈是指所经过各 顶点相异的一条简单刚路。如果一个图g 中存在至少一个h a m i l t o n 圈，图g 就是哈密顿图 ( h a m i l t o n 图) 。 2 2 互连网络中的基本概念 在设计互连网络的拓扑结构时，有一些用来估计网络复杂度、通信效率和构建成本的 性能参数起管十分重要的作用，这黾列出了评价网络好坏的几个主要参数和基本定义： 节点数( n o d e s ) 节点数用来表示网络中处理机节点的个数，主要反映网络的规模。 节点度( n o d ed e g r e e ) 网络中某一节点与其他节点相关联的边的条数称为该节点的度。 节点度表示节点所需要的i o 端口数。由于每个节点引脚的最大数目是有限制的，设计时 尽量减少节点的度数是降低成本的重要方法。另外，为了使系统构件模块化，网络可扩展， 节点度最好采用固定值。因此研究一个网络拓扑结构的正则性是十分必要的。 比如2 dt o r u s 中每个节点的节点度都是4 。2 dm e s h t p 内部节点的度也是4 ，处在拓 扑结构图四个角上的节点的度是2 ，除角上四个节点，最外层四条边上其他节点的度均为3 。 网络总的节点度( n e t w o r kd e g r e e ) 互连网络中所有节点的节点度之和。网络总的节点 度可以在一定层面上反映建构网络成本的高低以及网络布线的复杂度。 链路( 1 i n k ) 一条链路是由一条或多条电线或光纤组成的缆线。两端各有一个与交换 机或网络接口处端口相连的连接器。它允许模拟信号从一端开始传送，在另一端接受，通 过采样获得原本的数字信号流。链路主要从长度、宽度以及定时等三个方面来刻画。当把 互连网络抽象为图时，链路就相当于图中的边。 节点直径( n o d ed i a m e t e r ) 网络中任意节点u n 其它所有节点最短距离的最大值，称为 该节点的节点直径，记为d i a m ( u ) 。节点直径是评价具体某一个节点在网络中通信延迟的重 要参数。 网络直径( n e t w o r kd i a m e t e r ) 指网络中任意两个节点之间最短路径中的最大值，也 可以说是网络中所有节点直径中的最大值。网络直径可以表示为d i a m ( g ) 。显 然，d i a m ( ”) d i a m ( g ) 。网络中的路径长度是用路由时所经过的链路数度量的。网络的路径 长度越大，两节点间的通信延迟也就越大，通信效率也就越低。为了减少通信时延，应尽 可能的缩小网络直径。 对分带宽是指把网络分为完全相同的两个部分时所需要切断的最少连线数目。对分 带宽又叫等分带宽，它是网络性能评测的一种方式。如果去掉这些通道，就会将网络分成 两个相同的非连通的节点集。当通讯模式完全均匀时，两个方向都有一半的消息跨越对分 1 0 山东师范大学硕士学位论文 链路。 可扩展性( e x t e n s i o n ) 是指把网络模块化以后的可扩展能力，而且要保证扩展后，性能 要随着规模的增大按比例的提高。这一点是比较难做到的，因为除了模块化本身的限制， 现在封装技术、软件实现、拓扑性质也都没有达到随意扩展的水平。所以可扩展性是现代 互连网络设计所追求的重要目标。 嵌入能力( e m b e d d i n g ) 网络嵌入属于并行系统模拟仿真的一个重要方面。一个网络如 果有良好的网络嵌入能力，就说明其他的某些高效算法可以方便的被移植到该网络中。另 外，某些相关联的问题集也可以被分配在该刚络中高效的执行或模拟。最好是人们已经比 较熟悉的简单网络拓扑结构可以直接作为所设计网络的予图，比如路、环、二部图等。 连线长度网络的周期是d 1 最大线延迟决定的，而且大部分电源用于驱动这些互连线。 因此最好互连网络所有的物理连线都采用短连线，这样既节省能源，也缩小了延迟时间。 物理布图实际也就是指一个网络拓扑的可平面性。如果拓扑本身是平面的，在物理 布图时只需要找到该图平丽化的实现方法。如果不是平面图，则要求出该拓扑结构的交叉 树。实际