Biswapped网络(BSN)的拓扑性质研究:点对称性和极大容错性

Biswapped网络(BSN)是一类两层结构的互连网络,它以任意图为模块且模块间采用一种完全两部图方式互连.BSN的互连形式与OTIS网络(即Swapped网络)类似但互连规则更一致,使得BSN展现出更好的性能.文中主要研究BSN的点传递性和容错性能.首先证明BSN能继承因子网络的点传递性质,为BSN上的分析和算法简单性找到理论依据.其次,通过直接构造网络中两点间最大数目的点不相交路径证明以任意连通图为因子网络的BSN是一致极大容错的.这些结果表明BSN既能继承因子网络的理想性能还展现某些好的新特性.最后,通过与OTIS网络、卡式积网络等层次类网络比较表明,BSN提供了一种构建可扩展性、模块化、容错性的大规模并行计算机系统的潜在有竞争力的体系结构形式.

一种基于Biswapped网络的并行矩阵乘算法

为了解决矩阵乘算法并行化的问题,根据Biswapped网络结构的特点,提出了一种基于Biswapped网络结构的矩阵乘并行算法。该算法采用一种新的矩阵映射方式,该算法操作简单且容易实现。理论分析和实验表明:该算法近似等效于Cannon算法。

基于Biswapped网络混合有效的负载均衡算法研究

本文针对大型层次网络Biswapped Network(BSN),提出了一种简单有效的负载均衡策略CDE-X,克服了传统方案中因大规模层次网络复杂高阶的拉普拉斯矩阵特征值的计算而呈现的不适用性缺点.在新算法中,均衡迭代过程大部分发生在BSN的因子网络内部,因而,CDE-X只需知道因子网络的结构及拉普拉斯特征值,从而在迭代均衡过程中提高了迭代收敛速度,并且降低了迁移负载流量的计算复杂性,同时降低了通信流量.理论比较证明,CDE-X不止降低了计算复杂性,更加降低了均衡迭代的步数,比传统的负载均衡策略X要更加简单、有效,更适用于大规模层次网络BSN.

基于并行处理的一种新型有效的网络架构BSN-MOT

结合BSN及MOT架构的双重优势,提出一种新型的双层架构体系BSN-MOT,并研究了其上的拓扑性质及在并行处理中应用的基本通信及应用等操作算法。算法包括行、列树广播、单向广播、数据求和、矩阵乘积、最短路径路由及多项式求根。最后,通过与其他2种有效的树形双层网络架构MMT及OMULT比较说明,基于BSN-MOT架构的通信算法要比其他2种网络有着更小的时间复杂度,且BSN-MOT是一种更具有竞争力的体系结构形式。