加总线超立方网络上的容错寻径算法  

Research on the Fault-Tolerance Routing Algorithm on Hypercube Added with Buses

作　　者：刘长河[1] 寿玉亭[1] 童明生 

机构地区：[1]北京建筑工程学院基础部,北京100044 [2]北京理工大学计算中心,北京100081

出　　处：《北京工业大学学报》2000年第1期80-86,共7页Journal of Beijing University of Technology

基　　金：北京建筑工程学院博士启动基金

摘　　要：研究了加总线超立方网络的容错寻径问题．设 ＢＨｎ为一个已加总线的ｎ维超立方网络， Ｆ为其故障结点集合，｜Ｆ｜≤ｎ．研究了ＢＨｎ上任意两个非故障结点间的容错寻径问题．对于小规模的超立方网络，其直径由ｎ＋２降为３，而对于较大规模的超立方网络而言，其直径降到≤（ｎ／３）＋６．显然，当ｎ＞６时，ｎ＋２＞（ｎ／３）＋６．因此，加总线后的超立方网络同时具有更好的容错性能．The problem of fault-tolerant routing on hypercube is studied on the basis of the method of adding bus. Let BHn be a modified n-dimensional hypercube which is added with multiple buses, and F be the set of its faulty nodes, |F|≤n. According to the conclusion in this paper, the diameter of small system of BHn; reduces from n+2 to 3, and that of large system reduces to not more than (n / 3 ) + 6. It is well known that, n + 2 > (n / 3 ) + 6, for arbitrary n > 6, so the fault-tolerance capability of the modified hypercube is improved than that of hypercube when n > 6.

关 键 词：多处理器系统 总线 超立方网络 容错 寻径算法 

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