（计算机应用技术专业论文）基于omega网结构的多播网络研究.pdf

中潲辩学技术太学竣| 学位论文珠f o m e g a 两缩构的_ 筝捕嘲络 i j f 究 摘要 随蛰鼯往能裔掰徽簸遴器在并行计舞税馥溺中的鞫益鬻及，离径能甄涟溷络 接米已经成为开发并行计算税经熊的关键羧术。盈然酱骑跫有厂商开始维戳商潞 化的互连嘲络7 m 晶。但怒，互连网络没计技术仍然怒并行计算机系统设计中最具 滔力、占辛母性的设计技术，互适网络仍然是并行计算视系统中巍赫化最少、囱 行设计最多的部件。因1 f 【f ，互连网络技术成为区别并行计算机体系结构的标志性 技术之一。 多级7 t 连网是并行分如式系统中一秘羹要的互连网终皱梭，挠够有效地实或 系统肉帮楚邂器替功能部件之秘静箱互遥铸，爸播辈播、蓬羧帮多播等各稀方式。 葵中，多播揉 睾瓣姘究楚瑙静多缀互连皤络辑究镁域中豹个热门漾逡，已有韵 关予多攒的成聚大多只针对现有的多级互遣网络，并且般只能实现单个多播， 对多播的支持能力不是狠好。因此+ 为多攒涤作设计的耨戮多级甄逐网络弓 起了 越来越多的蘑视。 本文磷究和分橱了多秽多级互连嬲( 茏其是结辑箍零规范毂o 铷e g a 劂) 姻瑰 蠢成果，在此基础e ，根掇o m e g a 网上盼鼹换和多播的特点，提如了，k 神基于 o m e g a 溺缀祷豹毅黧多攥嬲络：f i o 潮、f u o 嘲、蕊环o m e g a “x o m e g a 潮，这，l 糖燃络可缢囊路由踉实魂任懑熬多滚点多攥。并且，由于o m e g a 潮终本身瓣结稳 较为简荦髋范( 每一级静连接模式都稆潲) ，所以f i o 嘲、f u o 潮阻及循环 o m e g a x o m e g a 嗣豹硬件集成氇非常容翁，在实际戚丽中其有较离的价德。 在这儿种多播网络的构造基础上，我们给出了一种多播网络模型的设计思 怒，为耨裂多播网络的设计以及多级互适鼹上多播润题的研究，提供了一毒申参考 方法。 荚镳谲：多缀互连溺，o m e g a 嘲，攀摇，鬻涤，多撩，蠡路瘗。 中坷科学技术人学坝l 。学位论义 壮十o m e g a 嘲纠i 橱的多捅列络埘究 a b s t r a c t w i t ht h e i n c r e a s i n gp o p u l a r i t yo fh i g h p e r f o r m a n c ec o m m e r c i a lm i c r o p r o c e s s o r sa p p l i e di np a r a l l e lc o m p u t e r s ，h 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 k h a sb e c o m et h ec r i t i c a l t e c h n o l o g yi ne m p o l d e r i n gt h ep e r f o r m a n c eo fp a r a l l e l c o m p u t e r s a l t h o u g h s o m em a n u f a c t u r e r sh a v es t a r t e dt o p r o d u c e c o m m e r c i a l i n t e r e o n n e c t i o nn e t w o r kp r o d u c t s t h ei n t e r c o n n e c t i o nn e t w o r ki ss t i l lt h em o s ta c t i v e a n dd o m i n a n tt e c h n o l o g yi nd e s i g n i n gp a r a l l e lc o m p u t e rs y s t e m s ，a n di ss t i l lt h ep a r t w i t hl e a s tc o m m e r c i a l i z a t i o na n dm o s t s e l f - d e s i g n t h e r e f o r e ，t h e i n t e r c o n n e c t i o n n e t w o r kt e c h n o l o g yh a sb e c o m eo n eo ft h ed i s t i n c t i v ef e a t u r e so ft h e p a r a l l e l c o m p u t e rs y s t e ma r c h i t e c t u r e i np a r a l l e la n dd i s t r i b u t e ds y s t e m s ，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 ) i s a ni m p o r t a n tc l a s so fj n t e r c o n n c c t i o ns t r u c t u r e i tc a nr e a l i z et h ec o m m u n i c a t i o n s a m o n g a l lt h en o d e si nt h es y s t e m ，i n c l u d i n gu n i c a s t ，p e r m u t a t i o na n dm u l t i c a s t n o w t h er e s e a r c ho nm u l t i c a s t si sap o p u l a r p r o b l e m i nt h ef i e l do fm 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 b u tm o s to fc u r r e n tr e l a t i v es t u d i e sm e r e l yf o c u so nt h e p r e v i o u sm i n sa n du s u a l l yi n v o l v eas i n g l em u l t i c a s to n l y t h e s er e s u l t sa r en o tv e r y g o o df o rm u l t i c a s t s s om o r ea n dm o r ea t t e n t i o ni sp a i dt ot h en e wm i nd e s i g n e df o r m u l t i c a s t ai o to fm i n sa r es t u d i e di nt l l i sp a p e r , e s p e c i a l l yt h eo m e g an e t w o r kw h o s e s t r u c t u r ei ss i m p l ei nt h a ta l l i t sc o n n e c t i o nm o d e sa r eu n i f o r m b a s e do nt h ec h a r a c t e r o fp e r m u t a t i o na n dm u l t i c a s to no m e g an e t w o r k ，w ep r o p o s es e v e r a lm u l t i c a s t n e t w o r kf f i on e t w o r k 、f u on e t w o r k 、r o t a t i v eo m e g a 。o m e g an e t w o r k ) b a s e do n t h es t r u c t u r eo ft h eo m e g an e t w o r k ，t h e s en e t w o r k sc a l lr e a l i z ea n ym u l t i c a s tw i t h o u t c o n f l i c t w h a t sm o r e ，t h e s en e t w o r k sa r ee a s yt oi n t e g r a t eb e c a u s eo ft h es t a n d a r d s t r u c t u r eo f o m e g an e t w o r k ，s ot h e ya r eh i g h l yv a l u a b l ei np r a c t i c a l i t y a tl a s t ，w ep r o p o s ean e t w o r kd e s i g n i n gm o d ef o rm u l t i c a s t s ，w h i c hp r o v i d e sa n e wm e t h o df o rt h er e s e a r c ho nm u l t i c a s t si nm i n s k e y w o r d s ：m i n ，o m e g an e t w o r k ，u n i c a s t ，p e r m u t a t i o n ，m u l t i c a s t ，s e l f - r o u t i n g 筇2 虹 中阁科学技术人学坝f 学位论文 捧f o m e g a 嘲结构的多插m 络i j j | _ 究 第1 章多级互连网概述 随着v i 。s i ( 超大规模集成电路) 工艺的高度发展，町以用成白上千个处理器 和存储器模块连在一起构成个；1 ：t 二多处理系统，米解决诸如气象预报，图像处 理，雷达跟踪等高度复杂的算题。而任何多处理器系统都必须在处理器之间或处 理器和存储器之问提供经济和可靠的互连网络。随着处理器数目的增多，这种互 连网络将变成系统设计的关键环节。它的好坏直接影响整个系统的性能，所以， 多年来一赢吸引着研究和技术人员对多处理器的互连网络进行研究。 多级瓦连网足并行分枷式系统中的一种重要的互连网络结构【1 】，能够有效 的实现系统内部处理器等功能部件之问的相互通信，是系统构成的主要组成部 分，对并行计算机的性能影响很大。这一章主要介绍多级互连网的概念、结构和 分类等基础背景知识，以及网络上置换、多播等各种通信操作问题的研究现状， 最后给出本文的研究重点。 1 1 互连网络及其分类 传统的互连网络是根据操作模式( 同步或异步) 和网络控制( 集中式、分散式 或分布式) 来分类的。现在，多计算机、多处理器系统和n o w 占领了并行计算市 场，图1 1 给出了一种分类方案【2 】，该方案主要根据网络拓扑将现有的互连网 络分为四大类：共享介质网络、直接网络、问接网络和混合网络。浚分类方案基 于文献【3 】中提出的分类方法，主要集中在已经实现的网络。但是随着新兴技 术的发展，新的互连列络层出不穷，比如移动通信、光互连等，因此这种分类方 法不町能是完美的。 在共享介质互连网络结构【2 】t j ，传输介质由所有的通信设备共享，某一 时刻只允许一个设备使用网络。每个连接到网络的设备都包括请求电路、驱动电 路和接收电路，它们用来处理传输的地址和数据。刚络本身通常是被动的，其本 身并不产生任何消息。共享介质网络是一种 _ 分成熟的技术，但有限的带宽限制 了它们在多处理器系统中的应用。有两类主要的共享介质网络：局域网主要用来 在几公罩范围内建立计算机网络；底板总线主要用于单处理机内部和多处理器系 统中的通信。 摭5 呱 串耀事 学技拳夫学嫒l j 学经论文 菸。o m e g a 瓣结掏魑多撼嬲络磷究 盟适列络 共率 底扳总线 i 童接网络( 静态网络) 闯接 严 其他拓扑 争； j 总线 令牌总线 令牌环 超立方 交义开关 一：维脚格 = 维嗣格 一维单向环网或环 二维戒向环两 = 维烈向环网 络 阻 非服塞网络 筏合弼络 卜_ 多底扳总线 卜分屠嘲络 l l 一鏊丁集群网络 l 其他泓合拓扑：超总线，超嘲格游 餮1 1 互连麓辫 类 单向多级互避网络 跟掏多缀_ 互连溺络 蠢按蚓终义 i 6 ：静态嘲络，楚一穆缀流毒亍的网络结橇，套。展性好劳支持大规楼 的处理器【2 】。戡接网络包括一组节点，每一个节点直接连接到网络中其他节点 蕊予集上。每令繁点都楚一令可编程熬诗舞秘，宅买鸯蠡墨鳃处壤鼗、存镶器窝 其他的支持设备。节点的公用部件是路由器，负责节点问的消息洒信。每一个路 由器都与穗邻瓣魏由嚣蠢接连接。通常瑟个褶邻节点由一对方蠢籀反瓣单离暹道 避接，也i 叮以使用一啕；双向通道迨接。随潜系统中节点的增多，系统的总通信带 蘩6 蜓 e 仨仨 e l 疆辩学技农夫学聩t 学枝 宅交恭乎( ) “狞晷a 掰臻捣趣多援躐终蛾究 变、存馘器带宽积讨黪熊力也棚应增挑。困| l l ：，褒按网络怒襁遗大溉模劳行计舞 机最流行的h 连结构。常见的环形网( r i n g ) 、嗣格形列络( m e s h ) 和立方体网 终( c u b e ) 等郝瓣予。篷按麟终。这秘阚终一鲢搀绒以螽藏瓣定举交了，魄较逶含 构成通信模式可预测的并行处理系统和分m j 式甜“算机系统。 翻谈潮络又称蕊惫潮终，燕另炎：毫蘩鹣互涟翊络 2 1 。它没蠢爨供节点闼 的虞接连接，任何两个节点问的通信必须通过某熙交换机进行。堪个节点都有一 个列络适配器迄矮蠢黼络开关j 二。 i ： 个开关部有一组潲口，缚个端包括条输 入朝输燃链路。每个开关她端口戏嚣连接到处理器，或嚣懋空，戏訾连接到其他 l ：关的端ui ：，以实现处理器闽的连接。这些丌芙的互逡方式决定了不同的网络 梅羚。黼接互遂嘲终攀溺予共享存鞴器帮分匆式存继器等多处遴器系统嘻l 。交叉 ，f ：关网络、单缴互连网络和多缴互连网络等都属于间接网络。 混合溺缀 2 1 练含了共事赍矮滔终鞫蠢袋潮络藏秘菠潮络鹣瓤灏，爨泣， 它们与共享介质网络相比增加了宽度，与直接网络和问接网络相比又减少了节点 潮瀚激离。溉合潮络一种缀鼢翻瘦塌实彰嘈怒带轿豹l a n 。僚蹩麴巢系统嚣求眈较 浅的性熊，蛊接网络和0 | j 接嘲络比混台网络具有更好的可扩展性，因为点到点蛉 连接比熬宰介质的总线烫简单、更快，所以，大多数高憔能并行计算机使用赣接 潮终或赳接嬲络。 1 2 多缀互连网鳃结构 多缀甄连网络( m i n ) 通过一定缴数的野关运接输入竣备秘辕斑设备，镣一个 开关都怒一个交叉开关网络。开关级数和级之删的连接横式决定了网络的拓扑结 魏拳l 爨囱辘力。海令糖邻级之瓣采】 l 懑宠麴连接模式，遴避韵念澄嚣各缀开荚瓣 状念求实现输入输出节点之间的连接。根搦连接模式和缴数的不同，可以分为很 多种多缀甄逶爨绦。蓄先介绍，l 耱鬻爝豹砭连蘧数，它 f j 常掰鬟= 多级互涟网络鹣 避接模式。 1 2 1 互连函数 多级互连网络的一个重要特性是连接模式，良反映了网络输入端到输出端的 连接能力。为了溪嘲这一特性，每_ 种多级匿逐测络鄙可以蠲一组互连溺数来袭 第7 蜒 闭科学挫术人学坝i 学位论义 壮十( ) n l e g a i 叫结构的多橘h 络1 i j | _ 究 宽、存储器带宽和计算能力也相应增加。因此，直接网络足构造大规模并行计算 机最流行的互连结构。常见的环形网( r i n g ) 、嘲格形网络( m e s h ) 和立方体网 络( c u b e ) 等都属于自接网络。这种网络一旦构成以后就固定不变了，比较适合 构成通信模式可预测的并行处理系统和分川j 式汁算机系统。 间接嘲络又称动态网络，是另一类主要的互连网络【2 】。它没有提供节点问 的直接连接，任何两个节点问的通信必须通过某些交换机进行。每个节点都有一 个l 却9 络通配器连接在网络玎关上。缚个j 1 ：芡i i i ：_ f = r 一绀端u ，每个端i i l 包括一条输 入和输出链路。每个丌笑的端口或者连接到处理器。或者悬空，或者连接到其他 ，l ：关的端uj ：，以实现处理器删的连接。这些丌关的互连方式决定了不同的网络 拓扑。问接互连网络常用于共享存储器和分布式存储器等多处理器系统l 】。交叉 ”关网络、单级互连网络和多缎互连网络等都属于f 1 日j 接网络。 混合网络 2 1 综合了共享介质网络和直接网络或间接网络的机制，因此， 它们与共享介质网络相比增加了宽度，与直接网络和问接网络相比又减少了节点 j 1 _ i j 的距离。混合网络一种极好的虚用实例楚带桥的l a n 。但是如果系统要求比较 商的性能，直接网络和间接网络比混合网络具有更好的可扩展性，因为点到点的 连接比共享介质的总线更简单、更快，所以，大多数高性能并行计算机使用直接 网络或削接网络。 1 2 多级互连网的结构 多级互连网络( m i n ) 通过一定级数的丌关连接输入设备和输出设备，每一个 丌关都是+ 个交叉丌关网络。开关级数和级之划的连接模式决定了网络的拓扑结 构和路由能力。两个相邻级之问采用固定的连接模式，通过动态没置各级丌荚的 状念来实现输入输出节点之问的连接。根据连接模式和级数的不同，可以分为很 多种多绂互连网络。首先介绍几种常用的互连函数，它们常用作多级互连网络的 连接模式。 1 2 1 互连函数 多级互连网络的一个重要特性是连接模式，它反映了网络输入端到输出端的 连接能力。为了说明这一特性，每一种多级互连网络都可以用一组互连函数束表 连接能力。为了说明这一特性，每一种多级互连网络都可以用一组互连函数来表 鹕7 虹 唾；瓣辩学投拳夫学赣 学位建文肇 。o r t e g a 耩缩搦躬害攒斓编鞭究 承每一缀之越瓣连接模式。f 瑟麓萃穷缓蔻霉孛露 ；霹熬互涟蕊数。 1 ) 均匀洗牌连接 均匀流瓣连缓跫褥输入端瀚。：进锈麓氧 ：稼环庄移髓，褥翻输趱蹋瀚二：遗翻 地 i ：，其湖数表达式为：盯0 蔗m 一x o ) = x m x x o x 。常 j 于o m e g a 嘲 等多级互连剐的构成。 男努，浚簿逡接还毯耩子浚瓣、超浚壤羁逶均匀洗艨连接。予浚薄遗接跫稽 输入端二进制地址的第0 ，一1 位进行沈牌，其它位地f i b _ ；i - ；变。其函数袭达式 为：c r “l “卜l 一x k + l x z 女一i x 0 ) = 冀h l x 女+ l x 女一i x o x ，0 七肘一l 。 超洗牌连接与子洗群连接籀扳，是稽输入鞴二迸毒秘a 址的第糟一女一1 ，i t 一1 位进行淡牌，其它位地盘 不变。簸函数表达式恐： 盯扭0 。一1 z 。一2 x n - k - i x 一 一2 一l x o ) = _ h 一2 x ，i - k - i 工。+ l x 月一 一2 工o ，0s 盘点”一1 。 遂鞠匀洗瓣连接粥楚稽将输入端二送翻遗蟪编号循环右移一德，得到输盘稿 地址。其函数表达式为：盯 。g 。置南) = 工。x 。乓。图1 2 怒这嬲种沈牌连 接的例子。 0 0 0 a ) 拶连接 婚玎m 连接( 。) o - ( 连接( d ) o - ( - 4 连接 豳1 2n ；8 的释种洗牌谶按 2 ) 绥影连接 蝶形连接是将输入端：进制地由上的最高位和最低位互换位簧，其它位地址4 i 变，褥爨辐应输 i 端的二避裁遗疆。葵函数表达戎为： 扛h l 。k 一2 x x 。) 2 x o x n 一2 x l j 咯一l 。 与洗牌连接一样，蝶彤连接也可分为予蝶形连接和超蝶形连接。予蝶形连接 楚定笼囊位魏最低位互换位霉，蘧数表这式为： 燕8 受 一羹一 二葵二 p 强辩学技术天学赣 j 学垃论盘耩l 二o m e g a 臻将抟多播列络秘究 题秘e # 一 x k + l x t x i l 苫 x 8 ) = x n l x i “x o x i 茗 x 女，o ： 7 7 ( b ) 群琏彼 胬l 5n = 8 i l 誊的萋稚连搂 ( c ) 群还接 + 一节讲的几秘珏遗躏数可嶷按构成攀级互遴网络，罄绂互逐蹦络只裁实现 葫羧麴凡转基本连接模式，不麓满足器瓣并行系统商逶僚鹩要求。耀茈，为了檎 遗大型熬牙关潮绦，将辇 缀夏连秘络遥避定静连接模式合并起来，就褥到多缓 互运网络 4 1 ，河用于m i m d 和s i m d 并行机蒋。通过动念设鬻歼关状态，多缴互 涟网络能够实现输入端和输赢端之瞄的连接请求，相比零级互连网络，其连接熊 力有旺著提商。 1 3 多级互连网络的分类 由于所使用的丌关元件、连接模式以及控制方式的不同，多缴互连测络可以 分为备融各样的类型。从嘲终的连接能力柬漤，多缀豆连嘲络大致可以分为魏类： 阻塞网和非阻塞网。下两分别介绍这两类嘲络。 1 3 1 多缀阻塞网 1 ) 阻塞月的概念 阻塞网熄指窆闲的簸入细竣澎端墨之蚪不是蕊黢建立遗接，因为有可能与现 蠢的连接? 申突。典型情况下，每一对输入积输嫩瑞口之闽鸯唯一的鼹镪，这样健缮 歼关数和缀数终劐鬣夺。餐憝，氇钰：f 羰提袄多条遴鼹柬减少冲突，增翔容锩黥力。 第1 0 瓤 中鼹科学技术人警颤l j 学 照埝文 # s - p o m e g a n 结构躺多撬蜒缋蛾宠 阻塞硝络也称做多通路两络，出于这装嘲络所用，i ：美少，延时也不长，路径控制 比较简单，又能实现并行处理中r ：多常用的鼢换瀚数，所以在实际系统c l j 使用，“ 泛。落用瓣多缎燃塞嘲有 甏z s e ii n e 嬲终i s 、o m e g a 列 6 1 、t a n y a n 嬲【? 】、 心接二进制嘲 8 1 、f 1 i p 删络 9 1 、d e l a 燃络【1 0 1 等。 隧塞鄹浆控裁方式是播耀终中备缀开关鹣控露l 方式，觳鸯三三瓣：缀控制、 单元接肇l 帮帮分级控豁。缀挖捌愁掺瓣一缓 关嬲一个瘩号寒控麓。攀元控铤瓣 是播黼络中酌每一个开关酃奢单独的控帝0 信号，所阻问一缀的开关也可以处于不 葡羽工作状态。部分级羟螽鳓介予蹰者之闯。 2 ) 不同阻塞网之间的拓扑关系 投攒掰耀开关模式、互涟函数鞠控铡方式的不鼷，嫩塞霹又霹以分为o m e g a 网、b a n y a n 脚、脚接二避制网等多荸申删络。这些网络虽然鳞构各不捆同，但是 鸯一定戆撼羚关系。 凝秘f e n g 褒文皴【5 l 孛撵烈，嚣令嬲络结构的拓扑等徐是攒，对予蕊中 一个嗣络，存在一个逻辑名缩构，使褥它带肖逻辑名连线的逶接关系可以沼弼一 个网络的辆翳描述斌刚束箍述。掰谓的拓扑獭述蕊翊楚捂，攒述不同缀开关元件 之m 连接模式的组数据规则，这可以从网络的具体结构赢授导出。在拓扑同构 i i ；4 络之蝴， 蚋盈过熏掰命名网络的竣入和输嫩端，使得一种网络的连接能力宠全 等价予_ 另一种1 b 4 终。 隽了褥突这耪耧羚关系，雾u 鞫f e n g 在【5 】中还霉| 入了一耱基准潮缀 ( b a s e l i n e 网) 佟必比较箕继释多缓隧塞网螅参考。器祧不鄹麴网络女畦聚都 与b a s e l i n e 黼络辐扑等价，箨么它们之涧巍是拓卦等价瀚。倒鲻，o m e g a 黼、 b a n y a n 溺和b a s e l i n e 掰都怒拓羚等徐韵黼络，翻1 6 绘斑了n = 8 时的情况。 类似她可以证明：o m e g a 】_ i i 9 、b a n y a n 嘲、m j 接二二迸制网，以及相成的倒置网络都 是妊毒卜等徐的【l 】。 ( a ) 0 m e g a 两( b ) b a n y a n 溺 ( c ) b a s e lj n e 列 蘅i 60 m e g a 礴、b 懿y 鳓褥、3 瞄e l i 聪瓣乏商静拓扑等价关紧 第1 1 艇 串獬车 学技求天学顿| ：学位瓷文树o m e g a n 结构鹩多撬躐络辑究 1 3 2 多级菲阻塞隧络 菲隧塞爨终指 薹意埝入臻日哥酸连接任意空添懿埝密凑瑟瑟不会影痢凌芍 连接。非阻塞网络与交叉丌关的功能相同，它们要求输入和输出端口之间柯多条 路径，苁巅致使缴数增摊。 首先我们介绍一般连接系统的概念 4 1 ，一般连接系统出图1 7 所示：一组 端扣( 输入和输出) ；控带9 单元( 负责处理成对端【_ = f 的连接请求) ；连接网络( 通 过它建立戚对端口之闽的遮接) ； 圈1 7 一般连接系统的攘壅 连接网络只有三种组合特性：可重排健、广义的非阻塞性和狭义的非阻塞性。 霹予一令多缀互连瓣终，_ 鲑巢逶避霪赣接列瑷鸯戆连接，藏戆处理瓤有毅蕊竣灭 输出的连接请求，则称这个刚为可蘑排非阻塞网。如果不衙要改变现有的连接， 毽必须按一定静筑辩蠢壤实现薪的连接请求，鲻称之为j 义貔薛戮塞潮。翔巢誉 管i ) c 4 络处于什么状淼，任意选用目| j i 可用的链路就能实现所有新的连接请求，则 称之为狭义的菲阻塞阐。下面分剐介绍这三稀菲阻塞稠。 1 ) 可重搀非阻塞孵 可重排非阻塞嘲络的宓义是：如果重新安排现有的连接，便可无阻塞地实现 任意匏竣入簸出迄谈，从艇实残一个薮鲍辜a 入辕蹬戆连接请求。虽然t 鬟终燃 的连接能力比阻塞网要强，但硬件代价以及路径掀制算法的复杂胰要比阻塞纠 夫。 b e n e s 网【1 1 】是一种擞要的呵熏排非阻塞网，使用q x q 开关。，对输入 输出的结构，如图1 8 ( a ) 所示。当q = 2 时，g e n e s 网可以看成b a s e l i n e 网和 b a s e l i n e 。两攒接丽成，对n = 8 鹣情况鲡阉1 8 ( b ) 掰示。 中蔺科学技术天学硕i j 学证论文 基1 1 ： o m e g ai 1 镰构豹多攥鲻络硪究 输 入 端 8 ) n n 勺b e n e s 羽舱一般结柳 输 出 端 ( b ) n = 8 ，q = 2 的b e n e s 网 鬻1 8b e n e s 隧瓣结梅 t r 羹排非阻塞网的，1 ：关控制算法比阻塞网复杂，有循环控制法【1 2 1 、终端 控制法1 6 1 、并行设置法【1 3 1 、方阵分解法【1 4 】等。 2 ) 装义移广义的菲阻塞阙 一个网络能处理所有可能的连接而不会导觳冲突，叫做非阻塞网。这单的非 貔塞飚怒豢，不必改变剿络中联寒熬臻入爨秘浚蹬羰嚣羧熬开关状态，馒可实聪 任意输入端和输出端的连接请求。与可骥排非阻塞网不同，对于网络中新的连接 请求，多缀菲錾塞嚣不镒要改交黼络摹绦束酶迄搂路径，藏髓实麓薪豹连接。 狭义的非阻塞网的约束性很强，它要求：使用任意一条当时米被占用的链路 就能实现所有可能的、新的输入输出连接请求。n x n 的交叉开关就是秤狭义 敬菲阻塞阚，但硬终饩徐太大，嚣要2 个2 2 的开关。 为了降低硬件代价，c l o s 襁【1 5 】中提出了一类非阻塞网络c ，心，) ，如 图1 9 所示。根獭参数晰，l ，r 的不同，c l o s 网的组合特性也不尽相同。当中 翊缓开关数琳遴跫掰栉辩，c 搬，强r 靛是可鬟终j # 戳塞潮。魉摇上一苗中， 咖唰 啪 蝴 瑚 m m 串瑚事 学拄拳又擘颤l ：学位论文 幕手o m e g a 狃绍翰鹩多撩榭络孵究 n ：2 ”静b e n e s 潮是一秘可霉挎簿獾塞嗣，它其实跫鼠形如e f 2 ，2 ，2 一 的c lo s 列递好构逑 酲成，酆重复使心c t o s 网魄结梭c ( 2 ，2 ，2 “) ，c ( 2 , 2 ，2 “一2 ) ， 直到所有的7 r 关郝是一个2 2 的憋小丌荚元件雌j c ( 2 ，2 ，2 ) 为止。 n 输 入 端 n n mr r n n 输 粥 灞 1 11 9 兰缀c l o sm m 型c ( m ，砟，) 当卅= n 时，如果中删级丌关数m 满足m 2 n 一1 时，这个c l o s 网就是狭义 鹣菲隧塞瓣1 4 1 。刍撤o 嵇l o g r l l o g l o g r ) ，c ( m ，绣r 漶“个广义翡菲藩塞翻， 即可以不改变瞰络巾原有的连接，但要按定的j | ! j l 则从目1 i f 尚末使用的链路中选 路彳+ 能实现新豹连接请求【1 8 1 。 1 4 多级互连两及其多播阀题的研究现状 具有可扩展性的大规模并行处理( m p p ) 计算机系统，出于其性能可以随系统 娥模的扩矮蕊增强，被认必是当今实现超蕊性能计箕静有效途径。节点处理能力 的飞速提商使节点问的通信成为影响系统性能发挥的关键，如何有效地实现m p p 系统中懿逶痿已残为实袋越裹往驻诗算瓣萋舅究热点之一。壤据逶傣霉亍先憨特点， 通信町以分为一个源节点与一个l ；| i 标节点之间的单播( u n i c a s t ) 乖i 多个源与多 个疆标：爷点之阍鹃聚食道信( c o i e c t i v ec o m m u n i e a t i o n 。裰爨瓣嚣上予1 9 9 4 年推出的m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 标准【1 6 l ，聚合通信可以分为障碍 同步、广播、分发( s c a t t e r ) 、收集( g a t h e r ) 、完全交换( c o m p l e t ee x c h a n g e ) 、 全局归约( g l o b a lr e d u c t i o n ) 和并行自t 缀( p a r a l l e lp r e f i x ) 等几种形式，是并行 应用中实现数据移动、进程控制、全局计算揉作的常用通信方式，虚用十分广泛。 投糖参与逶售行瓷熬源秘嚣标繁杰，聚合逐售可翔缝为三萋孛形式：一剑多瓣部分 凳1 4 凌 捧于o m e g a 耐结构韵擎播渊缔研究 广疆、多剩一静麴约翻多到多靛交换，蒺中巅多熬部分广疆可疆完娥广播、分 发和障甜删步中同步信号的广播，魁聚合通信的主蛩彤式【1 7 1 。 上一节中介绍鹩各种多缀互涟嘲，特澍怒阻塞潲及可重摊嚣融黎阏，幽于冀 铭构攘齐、路出算法麓单，在并行分如式系统中橙剿了广泛墩明，这方巍鳗秘也 脊缀多 u 荚研究成采。f 谢舆体介缁一卜多级互连网中，b 种常j i ： 的通偏方式。 1 4 1 多缎置连两牛的通倍方式 在并行分粕环境中，各处瑷器之间经常要谶行大餐的数獭通信。警多缀互涟 嘲用予并抒环境中的时镞，概聚起来群以分为下藤兰转运俊方式：嚣挨、多接、 多源点多播，如翻1 i o 所示。 基蕊藩 ( a ) 蓉羧( b ) 多掭 ) 多源点多瓣 阕1 。1 0 多缀置逢潮巾的潦惯蠢式 假定楚喇终中溃捌蛇个数，划，一个“攀援”憋搬个输入端口疆送到 一个输 i 端【： 的操作，“谶换”则怒指个互不捆：卜的单播。如图1 t 0 ( a ) 所示。 - 个“多撵”楚撵令辕入端澍播送戮辨个瓣滋溺翻 l 篓嚣蔓n 秘搽羚，芷蕈瀵 幻= 1 ) 的一般形式，如陵1 1 0 ( b ) 所示。如聚多个输入端蹦阉瓣撩送到豆不怕斛 的输出端口，就怒多源点多播，如图1 i o ( c ) 所示。 国鹭l 。i 0 孛珂戳蓉逡，( 8 ) 帮( b ) 都怒( ) 豹将豫黪式。滏魏辘蜜瑷多滁蕊多 插的 i 司络，必然也能实现谬换。所以对多源点多播的研究爿魑多绂互迨网巾通信 汹遂酌一敬 毫闷黢，也怒鼹簸杂鹣一类。下掰巍麓荦介绍霹羧掰瀚概忿。 1 4 2 鳖换瘸的穰念 鬻换网怒稽珂戳蠢澈罄魄实蠛灏蠢溪歉方式鹃多缀互连黼，瓣上露洪麓 b e n e s 嗍【l i 】，以及下一章要介绍的o m e g a 、e o m e g a 网【1 9 1 、o m e g a x o m e g a 网【1 2 1 和简化的o m e g a 一o m e g a 网都属于这种列绦。这鼹髓自# 研究檄多的一炎多缀互造 中 霹稀学接术天学颀 j 学位论曼幕予o m e g a 辩j 蟾搦静雾橘蛾臻蜡究 瓣，嚣爻它襞释我徐较枣( o ( n l o g n ) 、鼹窿冀滚篱单，并釜连接麓力较殛( 霹 以实现任惑嚣换) 。 v e n k a t e s h 在文献 2 0 1 中讨论了倒鼹o m e g a 网( o m e g a 嗣) 的一些性质， 并提出了倒霞o m e g a 网上实现爱抉的充要条件( 叉髂为“j f 燕矩赡”性袋) 。 f e n g 在【1 9 】中根描o m e g a 网上置换操作必须满照的某些条件，摄出了 o m e g a o m e g a 潮 豹一耱餮换算法( i n s i d e o u t 算法) ，通过设置中秘缀开关 状态，分别向输入输出端鼹由，束实现置换。时蚓复杂度达到o ( n l o g ) 。不过 此算法对输入输出端l 1 人。r1 6 的情况下会出现路山不成功的问题 2 t 】。 淹帮f e n g 在【 2 】中对o m e g a + o m e g a 潮豹中阕缀结秘进行掺菠，襻到了 种新型的网络o m e g a x o m e g a 埘，并在其一j ：提出了一种新的置换算法，通过设置 路由决策袭，从输入输出端同时翔中间级进行路出，实现溉换。时问复杂魔这至0 “| v l o g ) 。 c sr a g h a v e n d r a 在文献1 2 2 1 中对o m e g a + o m e g a 网l 二的置换提出了一种自 魏国瀚算法p l ，给出了一释解决路由冲突瓣策略，毽跫并不旋实现所有翁黉换。 i l a n s o n 在【j 4 】r | 7 提出了b e n e s 州卜一种代价最优的置换算法，州州复杂 度足o ( n l o g n ) ，存p 个处理器构成的并行机。l ( 1 蔓p l o g n ) ，口，以在 o ( n l o g n i 坊稳辩闻肉宠减。该嚣法秘榉逶翊 二与b e n e s 拓羚等份靛爨络，魏 麓化蛇o m e g a - t o m e g a | ) b ! l 笛。 t o n yt l e e 在【1 3 巾提出了b e n e s 网上的一种对称自路幽胃换算法，时 间复杂度达到o ( 1 0 9 2n ) ，j i 乏算法蓠先设置外层歼关的虢念，然瑶逐瑶向肉矗至 巾问级开关。 这些置换网络都和阻您嗍有相i 刊的硬件代价( o ( n l o g n ) ) ，但连接能力远 送强于阻褰两，弱潞由算法简单翁安现，掰竣餐到广泛静疲翊帮研究。熬丽随着 并行系统中处理器数目和问题规模的增加，多播操作褥到越来越多的应用；因此， 多缀互连网中多播问题的研究也变得越来越重要，这也花是本文韵研究重点。 巾糯挂掌投术久学赣 ? 学位逢文耩手( ) 撇g a 潮结糯耱多捕嘲络姘究 1 4 3 多播鳍题鳃磺究 一般蠢占，藤塞阏不缝实凌经意瓣多擦。整憝i h - j 二不嗣瓣终络稳熬攀擎点，逶 常埘以实飒满足浆剃t 条中i ：的多播。1 e e 在文献【2 3 】中提出，b a n y a n 嗍本身足 个阻塞丽，毽箸满足条亭 ：源点镳垂t 连续王圭相应的舀静璁疆有净u i - 序或降彦) ， 则可以无冲突地同时播送。我们将在第三章中把这个结论推广到o m e g a 网t ，并 对定理结论进行加强，使蔡适用范围更广，更具肖一般性。 嚣换网通过定的路 圭l 算法唾以实现赝有的嚣换，但是对多撩的支持能力并 不是很好。因为般对多播的路山都是通过把多播分解成若干个单播，再用置换 算法实璎。当一令多撂静羰戆逸蟪很多，源蘧蛙鞍少夔露籁，薤纛妥多次潺嚣置 换算法，且每次的臀换h 用到很少的一部分，这显然是一种很= _ _ f i 理想的解决方法。 随着并行分奄式系统中处理群数鏊酶和著行瓣遂巍穰的增耱，对多攒搽 乍的 需求电越来越人；然而现商网络对多播的支持能力并不是很理想。i 丑此，专门为 多播构造的多级甄连溺“多播掰”，也得至0 了越来越多的关注。y a n g 在文献 1 1 2 4 】中铃对多骡点多撵麴并发爨瞧了一瓣蠡路国多援网终，雯要联n l 0 9 2 秘的 丌关元件数，硬件复杂度比较大，并且网络本身的构造很复杂，也不利于集成。 1 s 本文主要内容 从l ：丽的讨论可以看出，专门的多播网络往往硬件代价较高，而现有的多级 互连网靖多疆翡支持效采x 不好。囡瓮，文奉重煮簧解决静闷题靛是，凌诗一种 新型的自路山多攒网络，用尽可能少的硬件代价，在尽可能短的时问内，熊够自 路幽地实现多源点多播。 谯1 ：i f i i 的罨按嘲一妒h 擞捌已经挝淝的儿聿 路【l l 鲐法，f 以实现所钉的茂 换搡作。但是某些置换算法并不鼹自路出的算法，这样通常要经过两步或者更多 步y j 戆实撬赝寅懿饕换，趱办l 了遴痿时翊。予楚，我们考感蹩孬麓弼较小瓣嫒馋 代价以及较低的时删复杂縻来实现多播操作。 透过对各耱戮塞疆藉餮筷溺臻有藏采瓣醑究，我靛发凝o m e g a 舞兹鼷络结搦 简嗥规范，而且基于o m e g e 网的o m e g a + o m e g a 网，o m e g a x o m e g a 刚，o m e g a 。x o m e g a 两。o m e g a x o m e g a 。阐等拥商沈o m e g a 嗣更多韵优点，所以o m e g a 嗣缎利予 巾瓣辩学技术太学颤l j 学缸论殳 臻j 。o m c 窖a 蝴站构多描州络稚 究 这秘多攥麓络豹褥遗，这 t 怒本文豹乏爰磷究幽骞。 水文后嘶的帮坩如卜安排：第2 章介绍并分析o m e g a 刚卜已有的然哭于簧 羧豹搿究减巢，包括o m e g a 湖本身酌结鞫和路由，并爨幽，l 个关予鬣羧韵定理， 同肘介缁几种基t 二o m e g a 网绒构的爨换嘲：第3 章介绍o m e g a 魁上关予多援昀研 究，提出o m e g a 嘲k 灾现多播的祭伴，并绘出种构造多播网络的憩怨；第4 枣介绍，b 秘綦 ：o m e g a 网臻梅麴瑟型多捶列终模型，为雾攫翊熬戆磺究援供了一 个参考方案；第5 章怒总结和服塑。 中黼辩学技术天学领1 学位论文 肇“l 。o m e g a 结秘麓多疆黼络群 究 第2 章o m e g a 网上的置换 o m e g a 网是一种阻塞网络，由于其结构利于硬件集成且连接能力较强，得到 了广泛翡疲矮 6 1 。o m e g a 疆本身并不畿实现繇鸯鹚置换，餐是爨o m e g a 溺帮秘 镫的o m e g a 网( o m e g a 。网) 【2 0 1 构造出的一些置换网，例如o m e g a + o m e g a 网【1 9 1 、 o m e g a x o m e g a 网【1 2 1 和简化的o m e g at o m e g a 网等，可以实现所有的置换。这 一章酋宠分缨( z a e g a 网上实现置换豹充要条 誓，然露分裂尼秘特豫夔置羧瓣懿隧 络结构和相应的霹换算法，并给出后面的多播路吐j 算法璎用到的几个定理。 2 1o m e g a 网简介 o m e g a 网【6 】是一种阻塞型多级互连网络，又称多级洗牌交换网络，出 辩= l o g n 缀开关缀成，每缴宙n 2 夺2 2 靛玎关组成，玎关青强种获态；直通、 交换、一l 援、f 攥，虹瞄2 1 联示。整个网络共有n 2 l o g n 个秀关，其中n 为 输入或输出端口的数目。级数的编排从输入端到输出端依次为0 门一l ，设输入 潲地址韵：二迸涮编码为：x n _ l x 。一- x 0 ，每级的连接模式依次为： c ( x 扑l x # 一z 石。) = 故一2 - 一x o x # 一 ，l i 墨拉，c o ( x 。一l 卜2 盖e ) = j 0 一l 善。一2 x 。 其中巴c 为洗牌交换连接，c 。为恒等嚣换。 爿三# 爿孓爿 爿三# ( a ) 逝通( b ) 交换( c ) 上掭( d ) f 捕 匿2 1 t ：美懿靼势洼羧状态 倒置尥o m e g a 网，即5 ) f i e g a “婀 2 0 l ，其网络拓扑结构就赵将整个o m e g a 嘲翻转，原柬的输入端变为输出端，原来的输出端变为输入端。所以两者的拓扑 缝梅蹩等馀躲。如图2 ，2 、图2 3 疑示。 鬻1 9 嵌 申瓣辑学技_ 拳大学娥1 学位逾交幕卡o m e g a 瓣维秘秘多箍 埘络硪究 鳖2 2o m e g a 舞雏籀接结耱麴2 3o m e g a 。舞熬菇羚缭糗 对连接请求，o m e g a 删采用终端控制的自路幽策略【6 】，基本思想是第k 级 豹，i ：关状惫出舀酌绝疆豹第k 位决定( o s 露一1 ) ：为0 烟播经。匕输出溺，为l 则播往f 输出端。下面是一个简单的例予，图2 4 所示。 0 0 0 输 入 0 1 1 端 输 “ 1 0 0 i o l 鲻 图2 4o m e g a 网的终端控制算法 每一对源点和目的点之问的逑接路径出目的地址雅一确定，多个单播并发时 有i j j 能会发生冲突，斟此o m e g a 嘲是一秘阻塞l = ( ；l 。e 图t 艮如，0 0 i 一1 0 0 稿 ( ”1 1 0 0 两个连接请求就会在第l 级的丌关上产生了冲突。所以，o m e g a 网h i 能实 瑷溪有戆逡接港袋，毽可以实璎以下各秘潍数嚣按； 恒等置换：，g ) = x ，0 x n 一1 。 按c 序散播加距离为d 的移数簧换：州= g 什6 ，o z j v l 且c 为奇数。 c f 序目鬃瀚毅黛j j h t 移数饕换：，( 戤+ 6 ) = c ，0 寒x n 一1 羟矗为奇数。 以及嚣种鼹换的变形置换。在数鳃处理中，o m e g a 网可完成按行、刊、对角线、 予块等无冲突地访问，因此是一