李江昀，孙丽婷

(1. 北京科技大学 自动化学院，北京 100083；2. 北京科技大学 钢铁流程先进控制教育部重点实验室，北京 100083)

1 引言

Biswapped网络(BSN)是一种双层架构的互联网络，它提供了一种构建可扩展性、模块化、可继承性、容错性等大规模的并行计算机体系结构形式[1]。基于BSN的多处理器系统架构，是由2N个规模为N的处理器组组合而成，即含有22N个处理器。另一方面，作为非常有效的互联网络拓扑结构，MOT(mesh of tree)拥有2个非常理想的性能，即小直径及高的对分宽度，并且在只考虑速度的情况下，MOT被认为是最快速的互联网络，在解决如分组路由、排序、前置计算、矩阵乘法运算、最短路径、最近邻居等重要算法问题时，运行在MOT上的时间复杂度只达到

本文结合BSN及MOT的双重拓扑优势，提出一种新型网络架构BSN-MOT，并对新架构的模型及基本拓扑性质进行了具体分析；同时，本文研究了运行在该架构上的基本通信及应用等并行算法，并与其他2种流行的树形双层架构在算法时间复杂度上进行了比较，结果显示BSN-MOT更为快速。

其实，许多其他的树形双层架构都被研究给出，如MCT(mesh-connected tree)[2]、MMT(multmesh of tree)[3]、OMULT(optical multi-trees)[4]等。在文献[2]中，Kemal证明了MCT是比超立方体更简单，且成本更低的架构体系。Jana[3]给出了MMT，分析了其拓扑性质及架构有效性，并理论验证了其并行算法的快速性。 Islam[4]提出了OMULT，并与OTIS-Mesh的比较表明，OMULT更具有优势。然而，根据BSN的网络连通性及极大容错性，BSNMOT将会比其他双层树形架构更具有竞争力的架构体系，研究其拓扑性质对网络的分析及网络的设计具有重要的意义。……