k元n方体网络的可靠性  被引量:2

Reliability of k-ary n-cube networks

在线阅读下载全文

作  者:张国珍[1] 

机构地区:[1]山西大学数学科学学院,太原030006

出  处:《计算机工程与应用》2013年第22期3-6,共4页Computer Engineering and Applications

基  金:国家自然科学基金(No.61070229);教育部博士点基金(No.20111401110005)

摘  要:k元n方体Qkn是设计大规模多处理机系统时最常用的互连网络拓扑结构之一。对于1≤m≤n-1,设F是Qk n中的一个由非空点集V F和非空边集E F构成的故障集,满足Qkn-F中不存在Qkn-m且VF破坏的Qkn-m的集合与EF破坏的Qkn-m的集合互不包含。设f*(n,m)是破坏Qkn中的所有子立方Qkn-m所需要的故障集F的最小基数。证明了对于奇数k≥3,f*(n,1)为k+1,f*(n,n-1)为kn-1-1+n,f*(n,m)的上下界分别为Cm-1n-1km+Cm-1n-2km-1和km。举例说明了上界Cm-1n-1km+Cm-1n-2km-1是最优的。The [k-ary] [n]-cube [Qkn] is one of the most popular interconnection networks in large-scale multiprocessor systems. For [1≤m≤n-1], let [F] be a faulty set in [Qkn] consisting of a nonempty node set [VF] and a nonempty link set [EF] such that there does not exist a [Qkn-m] in [Qkn-F] and the set of [Qkn-m]’s damaged by [VF] and the set of [Qkn-m]??s damaged by [EF] do not contain each other. Let [f*(n,m)] be the minimum cardinality of the faulty set [F] required to damage all the [Qkn-m]’s in[Qkn]. In this paper, the following results are proved. For odd [k3], [f*(n,1)] is [k+1] and [f*(n,n-1)] is [kn-1-1+n]. The lower and upper bounds on [f*(n,m)] are [km] and [Cm-1n-1km+Cm-1n-2km-1], respectively. Finally, the example shows that the upper bound [Cm-1n-1km+Cm-1n-2km-1] is optimal.

关 键 词:可靠性 互连网络 k元n方体 故障集 

分 类 号:TP393[自动化与计算机技术—计算机应用技术] O157.5[自动化与计算机技术—计算机科学与技术]

 

参考文献:

正在载入数据...

 

二级参考文献:

正在载入数据...

 

耦合文献:

正在载入数据...

 

引证文献:

正在载入数据...

 

二级引证文献:

正在载入数据...

 

同被引文献:

正在载入数据...

 

相关期刊文献:

正在载入数据...

相关的主题
相关的作者对象
相关的机构对象