论文摘要
传统的通信技术已经很难满足不断增长的通信容量的要求。许多新的通信技术应运而生,全光通信凭借其高带宽、低延迟、抗干扰能力强等优点成为最重要的通信技术之一。而基于波分复用（Wavelength Division Multiplexing,简称WDM）的全光网络已成为通信网络的重要研究方向,也是未来最具潜力的通信网络。由于现实中的技术限制,波长成为全光网络中最宝贵的资源。如果能够充分利用单根光纤中可以同时传输多路波长信号的特性,把较为复杂的通信模式嵌入在简单的光互连网络中,设计好的路由算法可以大大减少网络中所需的波长数,也可以通过优化设计大大简化互连网络的结构。波长分配是光网络设计的基本问题。设计波长分配算法是洞察光网络通信能力的基本方法,可以提高光网络中波长的利用率,改善整个网络的性能。已经证明该问题在大多数网络结构中是NP难的,所以对于这类问题具有重要的研究价值。采用光互连网络作为并行体系结构的通信网络是发展的必然趋势。不同的并行算法具有不同的通信模式,如何在光互连网上实现这些通信模式,是当前一个颇受关注的研究领域。网络嵌入是互连网络研究的一个重要方向。高效的嵌入会提高并行程序的运行效率。因此互连网络的嵌入问题也引起了研究者们的广泛关注。双环网络（Double-Loop Network,简称DLN）是一种重要的互连网络拓扑结构。它具有对称性、简单性和可扩展性等优点,具有比环网更好的抗毁性能和更短的平均通信时间,在计算机互连网络或分布式系统的拓扑结构中有很好的应用前景。本文讨论了将几个重要并行算法的通信模式嵌入在WDM双环网上的波长分配问题,其中包括数值分析领域中最基本的矩阵乘问题、在数字信号处理及图像处理等领域中广泛应用的快速傅立叶变换FFT、人工神经网络中的BP算法和Hopfield算法,并且讨论了两个网络嵌入问题,其中包括双环网嵌入RP（k）网络和mesh嵌入双环网。本文做的主要研究工作如下:（1）分析了并行矩阵乘算法中的ddd算法,基于WDM双环网,提出了一种嵌入算法MRDR,在此基础上分析了在WDM双环网上实现并行矩阵乘的波长分配问题,得到在此算法中所需的最小波长数为2,并给出了理论证明。（2）分析了在数字信号处理、图像处理等领域有着广泛应用的快速傅立叶变换（FFT）。基于WDM双环网,提出一种递归的嵌入算法FFT-DLN,针对四种基本嵌入算法生成法、对折嵌入算法、顺序映射和逆序映射,得到在WDM双环网上实现并行FFT的通信模式所需的波长数均为N/8（N≥8）。通过分析发现,对于相同规模的傅立叶变换,递归的对折嵌入算法和逆序映射具有更短的执行时间。（3）分析了在联想记忆、模式识别等方面有着广泛应用的Hopfield网络模型。基于WDM双环网,讨论了在其上实现Hopfield通信模式的波长分配问题,提出了一种路由策略及波长分配方案,在此基础上给出了实现Hopfield算法所需的波长数。（4）分析了人工神经网络中的并行BP算法。基于WDM双环网,讨论了在其上实现并行BP算法的波长分配问题,提出了一种路由策略及波长分配方案并进行了仿真实验,对实验结果进行了分析。（5）基于互连网络RP（k）和双环网,构造了10*k个节点的双环网结构,提出了一种将双环网嵌入RP（k）的算法DLN-RP（k）,此算法得到的四个性能参数拓展、负载、延伸、拥挤度分别为1,1,2,2,并证明了此结果为最优值。（6）设计了双环网的结构,讨论了将n*n的mesh嵌入双环网的算法,证明了此算法得到的四个性能参数分别为1,1,1,1,即嵌入算法的最优值。