论文部分内容阅读
多级互连网络是现代并行计算和交换系统的核心,如何构造具有良好通信能力、最优硬件代价和路由时间复杂度并可以无阻塞传输多播信号的多级互连网络是一个非常重要的研究课题。 通过探讨和研究如何在Omega网络上实现多播通信,本文将提出两种可以实现多播通信的新型无阻塞Omega网络结构:多-Omega网和3-Omega网。这两种网络结构都支持超大容量交换,可以无阻塞地实现多播,在硬件代价和路由时间上各有千秋。 本文将给出的多-Omega网以Omega和Omega×Omega-1为基础网,利用二分扩散的Omega×Omegal-1网循环构造出来,硬件成本为O(nlog2n),网络深度为O(log2n),路由时间为O(log2n)。本文将给出的3-Omega网以“Omega-1+Omega+Omega-1”组建而成,可以实现任意的多源点多播,硬件成本为O(nlogn),路由时间为O(nlogn),传输时延为O(logn),符合Claude Shannon于二十世纪五十年代提出的交换网络复杂度理论下限。 多-Omega网和3-Omega网无论在方法上还是在结果上都比现有的研究成果有一定的优势和创新,它们的设计与实现具有很好的通用性,对于进一步研究多播在多级互连网尤其是多播在Omega网上的实现具有积极的意义。