（计算机软件与理论专业论文）光网中的波长分配问题及基于光通信的并行计算.pdf

摘要 f f 近年来，光通信技术在很多领域都得到了研究和应用。其中，在广域电信i 网络和计算机 网络方面，最近提出了一种称为全光网的互连网技术。由于这种网络具有高带宽、低延迟等 优点，被认为是下一代网络的关键技术，所以它得到了广泛的研究。随之提出了很多极具挑 战性的理论问题，波长分配就是其中重要的一类，这类问题的目的是为了提高光网中波长的 利用率和改善整个网络的性能，所以研究它具有很重要的应用价值。另外一方面，光通信技 术也被用来构造紧耦合并行机系统中的高速通信互连网络。目前已提出了几种基于光通信技 术的并行计算模型，它们具有以往模型没有的很多优点，使得在它们上面可以设计出一些非 常快速又更易于实现的并行算法，所以在这些模型上研究并行算法具有重要的理论意义和实 用价值：吖 本文就上述的波长分配和并行计算两个方面展开了研究。其中，在全光网的波长分配方 面，主要包括：( 1 ) 对于环形光网中固定波长转换器的情况，采用置换群来刻画转换器的能 力，在此基础上提出了一个对于一般情况能够给出较好波长分配方案的算法。( 2 ) 对于环形 光网中有限波长转换器的情况，设计了一种最优的度数为4 的转换器及相应的波长分配算 法。( 3 ) 对于任意拓扑结构光网上的广播和多播情况，提出了以优化波长利用率为目标的最 少波长广播和最少波长多播问题，在理论上证明了它们是n p 完全的，并分析了它们的可近 似难度，提出了相应的近似算法。同时还将这两个问题推广到更一般的波长带权的情况，分 别分析了问题的难度，并提出了近似算法。 在基于光通信的并行计算方面，研究了r m e s h ( r e c o n f i g u m b l em e s h ) 和a r o b ( a r r a y s w i t hr e c o n f i g u r a b l e o p t i c a lb u s e s ) 两种模型上图论和计算几何中最小生成树构造、最小生成 树维护和多边形的三角剖分等三个基本问题，分别提出了相应的并行算法，它们的时间复杂 度是目前最优的。 一( 本文的主要贡献和创新为： ( 1 ) 研究了光网和并行计算中的一些基本算法问题，改进了已有的结果，包括：在 环形光网中有限波长转换器的波长分配方面，所设计的度数为4 的转换器改进了以前度数为 5 的结果；在i 瑚e s h 和a r o b 模型上的最小生成树及三角剖分问题方面，提出的算法在时 间复杂度和代价方面均改进了已有的结果，其中有几个常数时间的算法是首次提出的，具有 一定的理论意义。 ( 2 ) 首次研究或提出了光网中的几类波长分配问题，包括：首次研究了环网上任意 固定波长转换器情况下的波长分配，并提出了一种一般性的算法；首次提出并研究了任 意拓扑结构网络中的最少波长广播和多播问题，证明了它们的难度，提出了性能优良的近似 算法，并将问题推广到了一般情况。 ( 3 ) 在研究方法上，首次提出了几种新的方法，包括：提出用置换群来刻画波长转 换器的转换能力的方法，它能够很好地用于研究固定转换器的情况，可能也能够用于其它拓 扑结构和其它转换器的情况；提出按照图的邻接矩阵设置开关将图嵌入网孔中的 已经用其来研究了图的最小生成树问题，同时也可以应用于图论中的其它相关问题。 a b s t r a c t r e c e n t l y , o p t i c a lc o m m u n i c a t i o nt e c h n o l o g y h a sb e e na p p l i e da n ds t u d i e di nm a n ya r e a e s - i n t h et e l e c o m m u n i c a t i o nn e t w o r ka n dc o m p u t e rn e t w o r k ，an e wi n t e r c o n n e c tt e c h n o l o g y , c a l l e da s a l l - o p t i c a ln e t w o r k ，h a sb e e np r o p o s e d b e c a u s eo f i t sa d v a n t a g e ss u c h a sh i g hb a n d w i d t ha n dl o w d e l a y , i t h a sb e e ns e l e c t e da st h e k e yt e c h n o l o g y f o rt h en e x tg e n e r a t i o n n e t w o r k m a n y r e s e a r c h e s a r ef o c u s e do ni ta n dm a n y c h a l l e n g i n gp r o b l e m sa r er i s e n a m o n gw h i c hw a v e l e n g t ha s s i g n m e n t i sa ni m p o r t a n tp r o b l e m t h e p u r p o s eo fw a v e l e n g t ha s s i g t m m a ti st oi n c r e a s et h eu t i l i z a t i o no f w a v e l e n g t ha n di m p r o v et h en e t w o r kp e r f o r m a n c e o nt h eo t h e rh a n d ，o p t i c a lt e c h n o l o g yh a sa l s o b e e nu s e dt oc o n s t r u c tt h ei z 鼬s p e e di u t e m e t w o r ki nt h et i g h - c o u p l e dp a r a l l e lc o m p u t e r s y s t e m s o m e p a r a l l e lc o m p u t a t i o nm o d e l sb a s e do no p t i c a lt e c h n o l o g yh a v eb e e np r e s e n t e d t h e yh a v e m a n ya d v a n t a g e s ，w h i c hm a k ei t i s p o s s i b l et od e s i g ns o m eu l t r a - f a s ta n dp r a c t i c a lp a r a l l e l a l g o r i t h m s0 1 1t h e s em o d e l s s oi ti sv e r yv a l u a b l ei nt h e o r e t i c a la n d p r a c t i c a la s p e c tt od e s i g n p a r a l l e la l g o r i t h m s o i lt h e s em o d e l s i nt h ed i s s e r t a t i o n ，w es t u d yt h et w o p r o b l e m s w a v e l e n g t ha s s i g n m e n ta n d p a r a l l e la l g o r i t h m s o no p t i c a lm o d e l s f o rt h ew a v e l e n g t h a s s i g n m e n ti na l l - o p t i c a ln e t w o r k ，o u rr e s e a r c hi n c l u d e ：( 1 ) f o rt h ew a v e l e n g t ha s s i g n m e n to n r i n go p t i c a ln e t w o r k sw i t hf i x e dw a v e l e n g t hc o n v e r t e r s ，w eu s e p e r m u t a t i o ng r o u pt os t u d yt h ea b i l i t yo fw a v a l e n s t hc o n v e r t e r s ，a n dd e s i g na na s s i g n m e n t a l g o r i t h m ，w h i c hc a ng i v eag o o da s s i g n m e n ts c h e m ei na n yg e n e r a lc a s e ( 2 ) f o rt h ew a v e l e n g t h a s s i g n m e n to nr i n go p t i c a ln e t w o r k sw i t hl i m i t e dw a v e l e n g t hc o n v e r t e r s w ed e s i g na no p t i m a l c o n v e r t e rw i t hd e g r e e4 ，a n dp r o p o s ea r ta s s i g n m e n ta l g o r i t h mf o ri t ( 3 ) f o rt h eb r o a d c a s ta n d m u l t i c a s to na n yt o p o l o g y o p t i c a ln e t w o r k ，w ep r o p o s et w op r o b l e m ，c a l l e da sm i n i m u m w a v e l e n g t hb r o a d c a s tp r o b l e ma n dm u l t i c a s tp r o b l e m , w h o s eo b j e c ta r et oo p t i m i z et h eu t i l i z a t i o n o fw a v e l e n g t h t h et w op r o b l e m sa r ep r o v e nt ob en p c o m p l e t e t h ea p p r o x i m a t i o nh a r d n e s s r e s u l t so ft h e ma r ea l s oa n a l y s e d t w oa p p r o x i m a t i o na l g o r i t h m sa r ed e s i g n e d m o r e o v e rw e g e n e r a l i z et h e mt ot h ec s s ew i t hw a v e l e n g t hw e i g h t a l s od o n ea r et h ea n a l y s i so ft h eh a r d n e s s a n dt h ed e s i g no f a l g o r i t h m sf o rt h e m f o rt h e p a r a l l e lc o m p u t i n gb a s e d e l l o p t i c a lc o m m u n i c a t i o n w ec o n s i d e rt w or n o d e l ： r m e s h ( r e c o n f i g u r a b l em e s h ) a n da r o b ( a r r a y sw i t hr e c o n f i g n r a b l eo p t i c a lb u s e s ) t h r e e f u n d a m e n t a lp r o b l e m si ng r a p ht h e o r ya n d c o m p u t a t i o n a lg e o m e t r y , i n c l u d i n gt h ec o n s t r u c ta n d i h m a i n t e n a n c eo fm i n i m u ms p a n n i n gt r e ea n dt h et r i a n g u l a t i o no fs i m p l ep o l y g o n s ，a r es t u d i e do i l t h e s et w om o d e l s p a r a l l e la l g o r i t h m sh a v eb e e np r o p o s e d ，w h o s e t i m ec o m p l e x i t ya r et h eb e s ta s w e k n o w 1 1 1 em a i nc o n t r i b u t i o n so ft h ed i s s e r t a t i o ni n c l u d e ：( 1 ) s t u d y i n gs o m e f u n d a m e n t a la l g o r i t h m p r o b l e m s i no p t i c a ln e t w o r k sa n d p a r a l l e lc o m p u t i n gb a s e d o n o p t i c a lc o m m u n i c a t i o n t h e r e s u l t s i m p r o v et h ek n o w no n e s ，c o n s i s t i n go f ( i ) f o rt h ew a v e l e n g t ha s s i g n m e n t o no p t i c a lr i n g sw i t h l i m i t e dc o n v e r t e r s ，t h ec o n v e r t e rw i t hd e g r e e4i m p m v e s t h ek n o w nb e s tc o n v e r t e rw i t hd e g r e e5 ( i i ) f o rt h em i n i m u ms p a n n i n g t r e ea n dt r i a n g u l a t i o no nr m e s ha n da r o b ，t h ep r o p o s e d a l g o r i t h m si m p r o v et h ek n o w np a r a l l e la l g o r i t h m si nt i m ec o m p l e x i t ya n dc o s t ，a m o n gw h i c h s o m ec o n s t a n tt i m ea l g o r i t h m sa r ep r o p o s e d ( 2 ) f o rt h ef n s tt i m es o m en e ww a v e l e n g t ha s s i g n m e n tp r o b l e m sa r es t u d i e d ，i n c l u d i n g ( i ) s t u d yt h ew a v e l e n g t ha s s i g n m e n t o no p t i c a lr i n gw i t h a n yf i x e dc o n v e r t e ra n dp r o p o s ea l l a l g o r i t h mf o ra n yg e n e r a lc a 5 e ( i i ) p r o p o s ea n ds t u d yt h em i n i m u mw a v e l e n g t hb r o a d c a s ta n d m u l t i c a s tp r o b l e mo na n yt o p o l o g yo p t i c a ln e t w o r k t h e i rh a r d n e s sr e s u l t sh a v eb e e np r o v e n a n d a p p r o x i m a t i o na l g o r i t h m s w i t h9 0 0 d p e r f o r m a n c e h a v eb e e nd e s i g n e d ( 3 ) s o m en e wt e c h n o l o g i e sh a v ea l s ob e e np r o p o s e di nt h ed i s s e r t a t i o nf o rt h ef i r s tt i m e t h e p e r m u t a t i o ng r o u ph a sb e e nu s e dt os t u d yt h ea b i l i t yo ff i x e dc o n v e r t e r so nr i n gn e t w o r k s w e b e l i e v ei tc a na l s ob eu s e dt os t u d yo t h e rt o p o l o g i e sa n do t h e rc o n v e r t e r s t h es e t t i n go fs w i t c h a c c o r d i n g t ot h ea d j a c e n tm a t r i xo f a g r a p hi su s e d t oe m b e dt h eg r a p ht oam e s h t h i st e c h n o l o g y h a sb e e nn s et od e s i g n a l g o r i t h m sf o rt h em i n i m u ms p a n n i n g t r e ep r o b l e m i tc a na l s ob eu s e dt o s t u d y o t h e rp r o b l e m si ng r a p ht h e o r y i v 0 全文梗概 本章摘要：本章概述了光网的发展历史和现状，并指出光网中需要解决的 若干技术问题；然后提出了本文的研究内容，并综述了文中取得的研究成 果；最后给出了全文的组织结构 0 1 研究背景 随着社会的发展，通信网络已经逐渐成为人们生活中不可缺少的部分。在各个方面得到 了广泛应用。目前大多数实际使用的网络( 包括各种电信网络和计算机网络) 都是基于电子 信号，尤其是在交换节点上存在大量的电子器件，这种基于电信号的通信技术在适应高速、 大容量的需求时，存在着诸如带宽限制、时钟偏移、高干扰、高功耗等缺点。由此产生了通 信网络中的“电子瓶颈”现象，使得网络存在着带宽的上限，约为4 0 g b p s 。近年来随着“信 息高速公路”的提出，各种各样的新兴的通信业务也被提了出来，比如视频点播、电视会议、 远程多媒体教学等这些业务对于通信网络的带宽有着极高的要求。已经逐渐接近或超过了 传统网络的带宽上限。为了解决这个问题，以满足各种业务对带宽不断增长的要求，基于光 信号的全光网络的概念就被提了出来，并被作为未来通信网络的主要方向得到了广泛地研 究。 早在上个世纪5 0 年代，当阿瑟肖洛( a l s c h a w l o w ，诺贝尔物理奖获得者) 等川提 出了激光的概念后，基于光传输的高速通信系统的思想就被提了出来。在6 0 年代中期，实 验室里已经开展了导波光系统的研究 2 1 。1 9 7 0 年，康宁公司制造出世界上第一根低损耗光纤， 不久半导体激光二极管也被发明了，这时光传输系统的真正使用成为了可能，对于全光信息 高速公路的想象激发了研究者、业务提供商和公众的巨大兴趣。在实验室里，大量的研究得 到进行，从7 0 年代早期到8 0 年代后期，光纤传输系统的效能( 传输的比特率乘上传输的距 离) 大致以指数的速率增长，到8 0 年代中期已经达到了传1 0 0 公里高达8 0 b p s 的速率。1 9 8 8 年铺设了第一条横跨大西洋的海底光线光缆( 使用电中继器) 。而在8 0 年代后期，由于e d f a ( 掺铒光纤放大器) 的出现，光纤传输的距离被极大地增加了。从7 0 年代后期到9 0 年代中 期，光纤传输的带宽大致每年翻一番。到了9 0 年代中期采用时分复用技术的单信道带宽已 经达到l o o g b p s 左右。 由于光纤传输中的光信号相对电缆传输的电信号具有低功耗、高抗干扰能力等优点，以 及光纤中潜在的巨大带宽，使得在l o 多年前光纤通信就被肯定为未来通信建设发展的主体。 从上世纪8 0 年代后期以来，在世界范围内已经铺设了数量巨大的光缆。然而在早期，这些 光缆只是作为电缆的替代品，光缆本身潜在的巨大带宽并没有得到充分的利用。这主要是因 为早期的业务主要是电话业务，即语音数据的传输。这种业务对网络的带宽要求很低，事实 上整个美国在业务高峰期间所有的电话业务总量也小于单根光纤所具有的信道容量。随着网 络的发展，尤其是计算机网络的飞速发展，各种各样的新型业务不断涌现，当面向这些新业 务并需要提供高质量的业务服务时，能够在一个较大的范围内支持这些应用的通信基础结构 就只有真正基于光信号的全光网络。 另外一方面，在光纤通信中采用时分复用和单波长传输的方式的带宽也已经接近极限， 如果希望进一步提高系统速率就会产生技术和经济上的问题。然而一根光纤中拥有近4 0 t h z 的巨大潜在带宽容量，为了能够充分利用这些资源，9 0 年代后期，波分复用( w d m ) 技术 被提了出来。采用这种技术可以将光纤中的带宽分成不同的通信信道，这些信道使用不同频 率的波长进行通信。w d m 技术的使用使得光纤的传输速率一下子跳跃到了t b p s 的范围。 所谓全光网，简单讲就是在网络传输中端用户节点之间的信号通道保持光的形式，即端 到端的全光路，中间没有光电转换器。这样，在网络中光信号的流动就没有光电转换的障碍， 信号传递过程无需面对电子器件处理信息速率难以提高的困难，从而克服了电子器件带来的 “电子瓶颈”现象。基于w d m 技术的全光网与传统的电信网相比具有更大的带宽，并且 具有以往的通信网和现行的光电通信网所不具备的优点： ( 1 ) 以波长选择路由，对传输码率、数据格式及调制方式均具有透明性，可提供多种 协议业务，可不受限制地提供端一端业务： ( 2 ) 加入新的网络节点时，不影响原有网络结构和设备，降低成本，具有网络可扩展 性； ( 3 ) 可根据通信业务量的需求，动态地改变网络结构，充分利用网络资源，具有网络 可重组性： ( 4 ) 结构简单，端到端采用透明光通路连接，沿途没有光电转换与存储，网络中许多 2 ， 光器件都是无源的，可靠性高、易维护。 由于上面的这些优点，近年来基于w d m 技术的全光网已逐渐成为了通信网络研究的主 要方向，而且随着各种技术的成熟，其实用化的工作也在不断地进行，包括各种传输标准、 协议的建立，实用网络的建设等。 随着研究的深入，大量具有挑战性的问题被提了出来，其中一类重要的问题就是全光网 中的波长分配问题。这类问题提出的背景是因为在全光网中采用了w d m 技术，而由于现 实技术的限制，在一根光纤中通常不能同时容纳太多的波长信道( 目前的技术大概为1 6 0 条波长左右) 。那么在大规模的网络中，同时可能会有大量的通信请求，为了能够满足这些 请求，如何将有限的波长分配给这些请求就是一个重要的问题，称为波长分配问题。这个问 题解决的好坏将直接影响网络的性能。在该问题提出之后，就进行了大量的研究( 关于这方 面研究的综述，本文第1 章将有详细的描述) 。这类问题不仅具有重要的应用价值，同时由 于它们也是一类组合优化问题，在大多数网络结构中都是n p 难的，并且与图的着色问题有 着很强的关系，所以对于这类问题的研究在理论计算机科学的研究方面具有重要的理论价 值。本文在第一部分中研究了全光网中的波长分配问题。 在上个世纪7 0 年代光纤技术被提出并得到发展之后，光纤不仅被应用于大范围的电信 通信网络中，还被用来建设并行机中的互连网络。由于光信号传输相对于电信号传输的优点， 在8 0 年代末、9 0 年代初研究人员将一类高性能的互连结构：可重构造网孔结构( r m e s h ) 中的电总线替换成光总线，从而使得这类结构的通信性能得到了提高。后来到了9 0 年代中 期，一类通信能力更强的互连网络( a r o b 和l a r p b s ) 被提了出来，这类网络中采用了 一种称为流水线式的光总线，主要利用了光纤中光脉冲的传输延迟可以精确控制的特性，使 得可以在一根光纤中采用流水线的方式传输数据。这些基于光通信技术的互连网络一经提出 之后，就吸引了并行计算机界的广泛关注，大量的算法在这些网络上提了出来( 关于这类网 络发展的历史和研究现状，本文第4 章将详细描述) 。由于这类网络具有强大的通信能力， 使得在它们上面设计出了很多高效的并行算法，甚至乎在很多方面算法的性能超过了经典的 理论模型p r a m ，而相对于p r a m 模型，这类网络又更易于实现，所以对于这类网络的研 究具有重要的理论和实际价值。本文的第二部分将研究这些网络上的并行算法。 0 2 研究内容及主要成果 本文的研究内容包括两部分：全光网中的波长分配问题和基于光通信的并行算法研究。 下面分别介绍本文在这两个方面的研究内容，其成果均以定理的形式给出 0 2 1 全光网波长分配问题 对于波长分配问题，我们主要研究了两类问题：一类问题是环形网络上某些节点具有固 定波长转换器或有限波长转换器时，给定一些端到端的通信请求，如何利用这些波长转换器 来实现高效的波长分配；另外一类问题是对于任意拓扑结构的网络，给定一个广播或多播请 求。如何使用尽可能少的波长实现这个请求。 1 环网上的波长分配 环形网络是广域网中主干网的常用结构之一。对于环形光网上的波长分配问题已经有了 很多研究，包括：静态请求的波长分配，动态请求的波长分配等，其中对于网络的节点上存 在波长转换器的情况，也有一些研究结果。我们研究了有固定转换器和有限转换器的情况下， 给定一些静态请求的波长分配问题。我们的研究结果有的是首次提出的，有的是改进了已有 的研究结果。主要内容包括： ( 1 ) 固定波长转换器的情况：当任意节点上具有任意的固定转换器时，我们提出用置 换来表示转换器的转换能力，并用置换的乘积表示连续多个固定转换器的转换效果，从而用 一个置换群来描述整个环网上的波长转换，基于这种数学表示，我们提出了一个根据环网上 所有固定转换器的总效果对环网上的波长信道进行分解的算法，可以将所有的波长信道分解 成一些连续的循环信道序列；相应的我们还提出了两个对通信请求进行预处理的算法，将环 网上的一个通信请求集合分解成一些连续的循环请求序列；基于这些算法，我们进一步提出 了一个波长分配算法，该算法对于环网上任意的固定转换模式都能给出一个较好的波长分配 方案。就我们所知，这是第一个在任意固定转换模式的光环网上的波长分配算法。同时我们 提出的用置换群描述波长转换的方法具有一定的新意，我们认为这种方法是一种比较有前途 的分析波长分配的数学方法，可以用于分析其它结构上的波长分配问题。主要结论用下面的 定理描述。 定理o 1 ：给定一个有向光环网g = ( 矿，e ) ，g 中有w 个波长，在每个节点i ( 0 f 5n 1 ) 上都有一个固定的波长转换器，对应的置换为盯，所有置换的乘积 4 、 c r d 盯? q j 得到的新的置换的型为1 “2 “七“1 ，满足w = 乏慨，则对于任意负载 l ，t s 娶叫等卜请求集钆都可以在g 上无阻塞地删满足。 ( 2 ) 有限波长转换器的情况：我们设计了一种度数为4 的转换器，并提出了一个波长 分配算法。当在环网的某个节点上放置了一个这样的转换器之后，使用我们的算法可以实现 波长的充分利用。进一步我们还证明了如果要实现波长的充分利用，度数4 是下界，即不存 在度数小于4 的有限转换器，当在环网的某个节点上放置了一个这样的转换器时，能够完全 利用波长，从而证明了我们设计的转换器的最优性。关于这个问题，以前最好的结果是度数 为5 的转换器，我们设计的转换器改进了这个结果。当可以在两个节点上放置转换器时，我 们设计了两个度数为2 的转换器，放置了这两个转换器之后在环网上也能实现波长的充分利 用。主要结果用下面的定理表示。 定理o 2 ；存在一个度数为4 的有限波长转换器，当在一个光环网上的任意一个节点上 放置了一个这样的转换器时，对于环网上的任意负载为，的请求集合，都可以只用，种波长 来实现这个集合中的所有请求。 定理o 3 ：如果环网中的节点数h 足够大，并且在环网中只有一个节点有波长转换器， 那么为了实现波长的完全利用，转换器的度数最少为4 。 定理0 4 ：存在两个度数为2 的有限波长转换器，当在一个光环网上的任意两个相邻的 节点上放置了这两个转换器时，对于环网上的任意负载为f 的请求集合，都可以只用f 种波 长来实现这个集合中的所有请求。 2 任意拓扑结构光网上的广播和多播问题 广播和多播是常见的通信模式，而实际中存在大量的不规则网络，这些网络可以用一个 图来表示。我们提出了这种网络上以优化波长的利用为目标的优化问题：最少波长广播问题 和最少波长多播问题。这两个问题在实际的光网中具有重要的应用价值，同时这两个问题作 为两个组合优化问题也具有一定的理论意义。 ( 1 ) 广播问题：我们定义了最少波长广播问题，将使用最少的波长实现一个广播请求 的问题转换成图上的一个问题，即使用最少的波长来构造一棵生成树。我们证明了这个问题 比如：一个置换用不相交的轮换的乘积表示为盯= ( 1 2 5 8 x 3 6 7 ) ( 4 x 9 ) ，包含2 个长为i 、1 个长为3 和1 个长为4 的轮换，则称盯是一个1 2 3 4 型的置换 5 是n p 完全的，并且进一步分析了这个问题的近似难度，证明了问题不能够常数近似。相应 地提出了一个近似算法，并分析了算法的近似性能，通过分析看出，这个算法是接近最优的 我们还把问题推广到一般的情况：波长带权值的情况，这种情况具有更广的应用范围，并提 出了一个新问题：最小权波长广播问题，采用类似的方法，我们证明了这个问题是n p 完全 的，并分析了近似难度，最后提出了一个近似算法，并分析了算法的精确的近似比。同样这 个算法也是接近最优的。主要结果用下面的定理表示。 定理0 5 最少波长广播问题是n p 完全的，并且除非p = n p ，否则存在一个常数卵 1 ， 该问题不能够，7 h 0 一1 ) 近似。 定理0 6 最少波长广播问题可以1 n 伽一1 ) + 1 近似，其中n ( n i ) 为实例中的顶点数。 定理0 7 最小权波长广播问题是n p 完全的，并且除非p = n p ，否则存在一个常数 刁 l ，该问题不能够r l n ( n 一1 ) 近似。 定理0 8 存在近似算法，任给一个有n ( 1 ) 个顶点的最小权波长广播问题实例， 算法的近似比为日。，这里日。= 是第n - 1 个调和数。 ( 2 ) 多擅问题：我们定义了最少波长多播问题，将使用最少的波长实现一个多播请求 的问题转换成图上的一个问题，即使用最少的波长来构造一棵s t e i n e r 树。我们证明了这个 问题是n p 完全的，并且进一步分析了这个问题的近似难度，证明了问题不能够对数近似。 然后先针对这个问题的一些特殊情况设计了相应的近似算法，并逐渐将约束放松，最后针对 一般的情况提出了一个近似算法。这个算法是一个非平凡的算法。和广播问题类似，我们将 多播问题推广到更一般的波长带权的情况，提出了最小权波长多播问题，证明了问题的近似 难度，并对于问题的一种特殊情况提出了近似算法。主要结果用定理表示如下。 定理0 9 最少波长多播问题是n p 完全的，并且除非 ，p d t i m e ( n m e 蝌町) ，否则最 少波长多播问题不能够0 ( 2 ”g ”1 近似，其中占 o 任意。 定理0 1 0 最少波长多播问题可以o ( 4 nl o g n ) 近似。 定理0 1 1 最小权多播问题是n p 完全的，并且除非胭d t i m e ( n 4 e “4 ) ，否则最 小权波长多播问题不能够0 ( 2 0 9 “4 ) 近似，其中s o 任意。 定理0 1 2 满足同一种波长覆盖的顶点都连通的最小权波长多播问题可以o ( 1 n n ) 近似。 6 0 2 2 基于光通信的并行计算 基于光通信技术的r m e s h 和a r o b 模型被提出来之后，大量数值和非数值问题在这两 种模型上得到了研究。我们在它们上面考虑了图论和计算几何里面的三个基本问题，分别提 出了相应的并行算法，这些算法有些改进了现有的结果，有些是我们首次提出的这些结果 从并行算法设计的角度是具有一定意义，尤其是其中的几个常数时间的并行算法是首次提出 的，在理论上非常有意义。 ( 1 ) 最小生成树的构造问题：最小生成树的构造是图论中的基本算法问题之一，具有 熏要的理论和应用价值。在r _ m s h 模型上，我们首先设计了一个常数时间的选择算法，然 后设计了一种按照图的邻接矩阵将图嵌入到网孔结构中的方法，利用这种嵌入的方法，我们 可以在常数时间内判断顶点间的连通性，并计算图的传递闭包。使用这些结果，我们分别在 两种不同规模的p 4 v i e s h 上提出了两个最小生成树的并行构造算法。这两个算法改进了已知 的砌皿s h 上的同类算法。而在a i 的b 上。利用a r o b 上的两个更好的选择算法，结合我 们在必d e s h 上提出的算法，我们得到了两个时间复杂度更好的并行算法，这两个算法是首 次在a r o b 上提出的最小生成树的构造算法。主要结果用定理表示如下。 定理o 1 3 给定无向连通加权图g ( v ，e ) ，其中n 刮vi ，g 的最小生成树可以在规模 为n n 的r m e s h 上用o ( 1 0 9 2n 1 的时间求得。 定理o 1 4 给定无向连通加权图g ，e ) ，其中h = iv ，g 的最小生成树可以在规模 为弗“5 n 的r m e s h 上用o ( 1 0 9 n ) 的时间求得，其中0 占 1 是一个常数。 定理o 1 5 给定无向连通加权图g ( v ，占) ，其中n 爿vl ，g 的最小生成树可以在规模 为n n 的a r o b 上用o ( 1 0 9 n l o g l o g n ) 的时间求得。 定理0 1 6 给定无向连通加权图g ( v ，e ) ，其中n = l v i ，存在随机算法可以在规模为 ”的a r o b 上用o ( 1 0 9 n ) 2 的时间求出g 的最小生成树。 ( 2 ) 最小生成森林的维护问题：给定图的最小生成森林，考虑当图中的某些部分变化 时，如何修改已有的生成森林，使之仍然保持为新图的最小生成森林。这个问题具有重要的 实际价值。我们首先在r m e s h 上提出了一些对于内向树的操作的并行算法，然后利用这些 算法分别在二维和三维的r m e s h 上提出了最小生成森林的维护算法。在a r o b 上，我们 利用了光纤传输的有向性，利用a r o b 中光纤的有向连接的特性，提出了两个更加快速的 ：在本文中6 用于表示随机算法的期望上界 7 并行算法。这些都是关于这个问题在这些模型上的第一个结果。主要结果用定理表示如下。 定理0 1 7 给定无向加权单图g = 形矽n = 明，在月n 的二维r m e s h 上可以在d ( 1 0 9 n ) 时间内实现g 的最小生成森林的边更新。 定理0 1 8 给定无向加权单图g = 习，h = i 明，在n x n b 的三维r m e s h 上可以在d ( 1 ) 时间内实现g 的最小生成森林的边更新。 定理o 1 9 给定无向加权单图g = 习，月= i 吲，在n 的二维a r o b 上可以在o ( 1 0 9 l o g n ) 时间内实现g 的最小生成森林的边更新。 定理o 2 0 给定无向加权单图g = r k 习，n = i 卵，存在随机算法在n 的二维a r o b 上 用d ( 1 ) 时间实现g 的最小生成森林的边更新。 ( 3 ) 简单多边形的三角剖分问题：三角剖分是计算几何中的基本问题之一，对于这个 问题的串行算法和并行算法都得到了大量的研究。在r m e s h 上，已有结果研究平面点集和 其它一些受限的三角剖分问题，但是对于一般多边形的三角剖分还没有研究结果。我们首先 考虑了一种特殊的多边形：单调多边形的三角剖分问题，分别在r m e s h 和a r o b 上提出 了相应的并行算法，然后利用这些算法，我们进一步提出了对于一般多边形进行三角剖分的 并行算法。其中常数时间的算法是已知的第一个常数时间的并行算法。主要结果用定理表示 如下。 定理0 2 l ：给定n 个顶点的单调多边形，在”i t 的r m e s h 或a r o b 上，可以在d ( 1 ) 时间三角剖分这个单调多边形。 定理o 2 2 ：给定n 个顶点的简单多边形，在n n ”。的r m e s h ( 0 2 z 的有限转换器，此时波长分配问题可多项式时间解决。若一棵树中 只有个顶点的度数大于等于4 ，则称之为类二叉树( q u a s i - b i n a r yt r e e ) 。对于这类树， g a r g a n o 证明度数为3 的有限转换器就可以使波长分配问题多项式时间解决，而且可以构造 度数为9 的转换器，使用贪心策略能够有效解决波长分配问题。 a u l e t t a 等9 6 1 证明对任意的s ，可以构造度为2 1 兰( 1 n ! _ ! 兰+ 1 ) 的转换器，使得可以使 占占 用( 1 + 占) 三种波长贪心地实现任意负载三的通信请求。他们还证明对于二叉树，若转换器度 数为2 z 一1 ，则可以用贪心策略有效解决波长分配问题，在 3 7 】中他们进一步证明了二叉 树上度数q ( z ) 对于贪心策略是必须的。 对于无向的星形网络，当z 为偶数时，l w a m i 和s a s a k i 1 9 | 构造了一类度为2 的有限 转换器，放置在星形的中央节点上，则可以满足任意负载为z 的请求。 当在树网上考虑增量通信请求时，b a r t a l 和l e o n a r d i p 8 1 提出了一个d ( 1 0 9 月) 近似的算法， 、 并提出了一个下界q ( _ 器) 。 1 2 2 4 其它规则网络 e r l e b a c h 和j a n s e n 在 2 3 e e i 正明了网格( m e s h ) 结构上的波长分配问题是n p 完全的。 对于维数受限的网格，任给通信实例i ，a u m a n n 和r a b a n i 0 9 1 给出了一个o ( 1 0 9 n l o g i ，1 ) 近 似的算法，这个结果对于维数受限的t o r u s 结构同样成立。对于正方形网格，r a b a n i 4 0 1 将上 述结果改进为p o l y ( 1 0 9 l o g n ) 近似。在无向和有向情况下，这些结果都成立。 对于d - 维正方t o r u s ，如果宽度为偶数，考虑上面的a l l - t o a l l 通信，b e a u q u i e ，l 】证明 d + t z ( i ) = 三( ， ) = n4 8 ，并给出多项式时间的波长分配算法。 对于超立方网络上的置换通信，无向情况下，g u 和t a m a k i 【4 2 1 证明最多只要8 个波长就 可以实现置换通信；有向情况下，最多只需要2 个波长f 4 3 】。 如果一个网络是一个完全图的c a r t e s i a n 和时对于有向的a l l - t o a l l 通信，b e a u q u i e r 4 1 】 证明z ( x 。) = l ( 1 j ) ，并提出有效精确算法。 对树环网，r a g h a v a n 和u p 脚【删提出了一个近似度为3 的近似算法，这个结果被d e n g 等4 ”改进为2 5 。对于一个实际中常见的特例星环网，本文的作者和合作者在【4 6 】中提出了 一个算法，对任意负载为的通信请求，只需最多5 三2 种波长，并提出了一个下界9 三4 。 对网孔结构和树环网( t r e e - o f - r i n g ) 上的增量通信，b a r t a l 和l e o n a r d i ”埂出了o ( 1 0 9 n ) 近似的算法，并进一步证明了网孔结构上的下界为f ) ( 1 0 9 n ) 。 1 2 2 5 一般网络 在一般的网络上，对任意的请求实例，找一个负载最小的路由方案，这个问题等价于 一个常数边容量的有向整数多商品流问题。即使是容量为1 ，只有两个商品的多商品流问题 也是n p 完全的【”