论文部分内容阅读
多级互连网络在并行计算等许多实际问题中有着重要的应用,它对系统的软硬件性能都有很大影响。位变换网络是一类结构良好、而且包含绝大部分在文献中得到深入研究的多级网络,本文着重对这类网络的结构、路由算法和可重排性进行较系统的探讨。
在第一章对背景和问题作了简单的介绍后,我们在第二章给出位变换网络的一个完全基于图论术语的刻划,这一结果将Bermond等人针对单一网络的结论推广到所有的位变换网络,将对多级网络结构的了解大大推进了一步,并且澄清了一些对位变换网络结构的模糊认识。
多级网络的分层叉积是Even等人引进的一个较新的概念,它不仅是研究网络结构的一个有力的工具,而且对于路由算法设计有着广泛的应用前景。第三章我们给出位变换网络分解为一些“均匀”因子的结果,该结果使得我们在第四章成功地将置换路由问题转化为一类特殊的矩阵问题。这一转化将Linial等人关于洗牌交换网络的一个结论推广到所有位变换网络,并且由此得到可重排网络的一个必要条件,部分解释了为什么许多已有的工作对2n-1级网络的关注。
第五章专门讨论2n-1级网络的可重排性。这一领域最重要的问题之一就是Bene(s)1975年提出的一个猜想,我们将这一猜想放到一个更广泛的问题中,并对它作了较多的讨论。特别地,我们给出了包含Bene(s)猜想在内的一类可重排性问题一个新颖的数学描述。我们还着重对Cam关于这一猜想的证明作了深入分析,简化了他的方法,并指出他的证明是不完全的。
随着相关科学技术的进步,越来越多的研究兴趣集中到光信息在多级网络中的传输问题上来。我们在第六章证明了位变换网络中的光信息传输问题在理论上与传统的电多级网络是等价的,从而说明已有的理论并不过时。在正式给出无干扰可重排性的定义后,我们建立了它与电网络中的可重排性问题之间的关系,并证明DilatedBene(s)网络是级数最少的无干扰可重排网络。