一种递归构造的合成BANYAN网络  

The Recursively Constructed Composite Banyan Network

作　　者：任开新 顾乃杰 潘伟 刘刚 

机构地区：[1]中国科学技术计算机科学技术系,安徽合肥230027

出　　处：《电子学报》2003年第2期228-231,共4页Acta Electronica Sinica

摘　　要：该文提出了一种新的多路径多级互连网络———递归构造的合成BANYAN网络 ,网络由若干级 3× 3的开关组成 .通过增加中间链路 ,解决了在已有的由Seo和Feng提出的合成BANYAN网上不能实现所有置换的问题 .该网络无需复杂的数值计算 ,通过二进制操作就可以很容易的产生路由标志 ,得到更多的路径 ,从而大大提高了路由成功率和容错能力 .该文中还给出了路由算法 ,并提出通过设置标识开关性能的标志位 ,使在路由时选取正确的路由标志 ,提前避开不起作用的开关 ,达到“预容错”A new multipath multistage interconnection network called the recursively constructed composite banyan network is proposed.The basic building blocks of the network are 3×3 switching elements.The advantage of this network is to resolve the problem that the composite banyan network proposed by Seo and Feng can't perform arbitrary permutation by adding middle stages.The network can easily generate a primary routing tag and more alternate tags through simple binary operations,which increase the degree of fault tolerance.A permutation routing algorithm suitable for the network is introduced.The major feature of the network is pre fault tolerance.By setting a flag bit to identify whether the status of one witch is usable or not,the network can choose appropriate routing tag to avoid the switch that can't work in advance.

关 键 词：多级互连网络 合成BANYAN网 递归构造 路由标志 路由算法 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]