计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2013年
22期
3-6
,共4页
可靠性%互连网络%k元n方体%故障集
可靠性%互連網絡%k元n方體%故障集
가고성%호련망락%k원n방체%고장집
reliability%interconnection networks%k-ary n-cubes%faulty sets
k元n方体Qkn是设计大规模多处理机系统时最常用的互连网络拓扑结构之一。对于1≤m≤n-1，设F 是Qkn中的一个由非空点集VF和非空边集 EF构成的故障集，满足Qkn-F 中不存在Qkn-m且VF破坏的Qkn-m的集合与 EF破坏的Q kn-m的集合互不包含。设 f*(n，m)是破坏Q kn中的所有子立方Q kn-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。举例说明了上界
k元n方體Qkn是設計大規模多處理機繫統時最常用的互連網絡拓撲結構之一。對于1≤m≤n-1，設F 是Qkn中的一箇由非空點集VF和非空邊集 EF構成的故障集，滿足Qkn-F 中不存在Qkn-m且VF破壞的Qkn-m的集閤與 EF破壞的Q kn-m的集閤互不包含。設 f*(n，m)是破壞Q kn中的所有子立方Q kn-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。舉例說明瞭上界
k원n방체Qkn시설계대규모다처리궤계통시최상용적호련망락탁복결구지일。대우1≤m≤n-1，설F 시Qkn중적일개유비공점집VF화비공변집 EF구성적고장집，만족Qkn-F 중불존재Qkn-m차VF파배적Qkn-m적집합여 EF파배적Q kn-m적집합호불포함。설 f*(n，m)시파배Q kn중적소유자립방Q kn-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。거례설명료상계
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 k n-1-1+n . The lower and upper bounds on f*(n,m) are km and Cm-1n-1km+C m-1n-2k m-1 , respectively. Finally, the example shows that the upper bound Cm-1n-1km+Cm-1n-2km-1 is optimal.
