概率故障条件下k元（n-m）方体子网络的可靠性

doi:10.11772/j.issn.1001-9081.2022030414

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (4): 1198-1205.DOI: 10.11772/j.issn.1001-9081.2022030414

• 先进计算 • 上一篇

概率故障条件下k元（n-m）方体子网络的可靠性

冯凯(), 刘彤

山西大学计算机与信息技术学院，太原 030006

收稿日期:2022-04-02 修回日期:2022-06-09 接受日期:2022-06-15 发布日期:2023-04-11 出版日期:2023-04-10
通讯作者: 冯凯
作者简介:刘彤（1997—），女，山西运城人，硕士研究生，CCF会员，主要研究方向：互连网络的容错性。
基金资助:
国家自然科学基金资助项目(61502286);山西省基础研究计划项目(20210302123438)

Reliability of k-ary （n-m）-cube subnetworks under probabilistic fault condition

Kai FENG(), Tong LIU

School of Computer and Information Technology，Shanxi University，Taiyuan Shanxi 030006，China

Received:2022-04-02 Revised:2022-06-09 Accepted:2022-06-15 Online:2023-04-11 Published:2023-04-10
Contact: Kai FENG
About author:LIU Tong， born in 1997， M. S. candidate. Her research interests include fault-tolerance of interconnection network.
Supported by:
National Natural Science Foundation of China(61502286);Basic Research Project of Shanxi Province(20210302123438)

摘要/Abstract

摘要：

k元n方体具有许多优良特性，已成为多处理器系统最常用的互连网络拓扑结构之一。当系统互连网络中发生故障时，系统子网络的保持能力对系统实际应用至关重要。为了精确度量k元n方体中任意规模子网络的容错能力，研究了有故障发生时k元n方体中k元（n-m）方体子网络的可靠性。当k（k≥3）为奇整数时，在概率故障条件下得出了k元n方体中存在无故障k元（n-m）方体子网络的概率的上界和下界，并给出了该可靠性的一种近似评估方法。实验结果表明，随着顶点可靠性的降低，k元（n-m）方体子网络可靠性的上下界趋于一致；当顶点可靠性较高时，利用近似评估方法得出的结果更为准确。

关键词: 多处理器系统, 互连网络, k元n方体, 子网络可靠性, 概率故障

Abstract:

The k-ary n-cube has many good characteristics， and it has become one of the most commonly used interconnection network topologies in multiprocessor systems. The maintenance ability of system subnetworks plays an important role for the practical applications of the systems when failures occur in the interconnection network. In order to accurately measure the fault tolerance of subnetworks with arbitrary size in a k-ary n-cube， the reliability of k-ary （n-m）-cube subnetworks in a k-ary n-cube in the presence of failures was studied. When k was an odd integer and k was bigger than 2， the upper bound and lower bound on the probability that at least one k-ary （n-m）-cube subnetwork was fault-free in a k-ary n-cube were obtained under the probabilistic fault condition， and an approximate method for evaluating the reliability was proposed. Experimental results show that there is a gradual convergence between the upper bound and lower bound on the k-ary （n-m）-cube subnetwork reliability as the vertex reliability decreases， and the evaluation result obtained by the approximate method is relatively accurate when the vertex reliability is large.

Key words: multiprocessor system, interconnection network, k-ary n-cube, subnetwork reliability, probabilistic failure

中图分类号:

TP393.02

冯凯, 刘彤. 概率故障条件下k元（n-m）方体子网络的可靠性[J]. 计算机应用, 2023, 43(4): 1198-1205.

Kai FENG, Tong LIU. Reliability of k-ary （n-m）-cube subnetworks under probabilistic fault condition[J]. Journal of Computer Applications, 2023, 43(4): 1198-1205.

图/表 3

表1 Qnk中两个Qn-mk子网络的不同相交情形

Tab. 1 Different intersection patterns of two Qn-mk subnetworks in Qnk

情形	子情形	相交情况	不同选法的总数	共有的顶点数
情形1	子情形1‑1	不相交	$n 2 n - 1 m - 1 n - m m - 1 (k 2 m - k 2 m - 1)$	$2 k n - m$
情形1	子情形1‑2	相交	$n 2 n - 1 m - 1 n - m m - 1 k 2 m - 1$	$2 k n - m - k n - 2 m + 1$
情形 $t$ $(2 ≤ t ≤ m - 1)$	子情形t‑1	不相交	$t 2 n t n - t m - t n - m m - t k (k - 1) k 2 m - t - 1$	$2 k n - m$
	子情形t‑g $(2 ≤ g ≤ t)$	不相交	$12 t g n t n - t m - t n - m m - t (k (k - 1)) g k 2 m - g - t$	$2 k n - m$
	子情形t‑ $(t + 1)$	相交	$12 n t n - t m - t n - m m - t k 2 m - t$	$2 k n - m - k n - 2 m + t$
情形 $m$	子情形m‑1	不相交	$m 2 n m k (k - 1) k m - 1$	$2 k n - m$
情形 $m$	子情形m‑g $(2 ≤ g ≤ m)$	不相交	$12 m g n m (k (k - 1)) g k m - g$	$2 k n - m$
情形 $m + 1$	情形 $m + 1$	相交	$12 n m n - m m k 2 m$	$2 k n - m - k n - 2 m$

表1 Qnk中两个Qn-mk子网络的不同相交情形

Tab. 1 Different intersection patterns of two Qn-mk subnetworks in Qnk

情形	子情形	相交情况	不同选法的总数	共有的顶点数
情形1	子情形1‑1	不相交	$n 2 n - 1 m - 1 n - m m - 1 (k 2 m - k 2 m - 1)$	$2 k n - m$
情形1	子情形1‑2	相交	$n 2 n - 1 m - 1 n - m m - 1 k 2 m - 1$	$2 k n - m - k n - 2 m + 1$
情形 $t$ $(2 ≤ t ≤ m - 1)$	子情形t‑1	不相交	$t 2 n t n - t m - t n - m m - t k (k - 1) k 2 m - t - 1$	$2 k n - m$
	子情形t‑g $(2 ≤ g ≤ t)$	不相交	$12 t g n t n - t m - t n - m m - t (k (k - 1)) g k 2 m - g - t$	$2 k n - m$
	子情形t‑ $(t + 1)$	相交	$12 n t n - t m - t n - m m - t k 2 m - t$	$2 k n - m - k n - 2 m + t$
情形 $m$	子情形m‑1	不相交	$m 2 n m k (k - 1) k m - 1$	$2 k n - m$
情形 $m$	子情形m‑g $(2 ≤ g ≤ m)$	不相交	$12 m g n m (k (k - 1)) g k m - g$	$2 k n - m$
情形 $m + 1$	情形 $m + 1$	相交	$12 n m n - m m k 2 m$	$2 k n - m - k n - 2 m$

表2 Qn-mk子网络可靠性理论结果的有效性分析

Tab. 2 Validity analysis of theoretical results of Qn-mk subnetwork reliability

k	n	$m$	$p$	k	n	$m$	$p$
3	6	2	0.000~0.897	5	6	3	0.000~0.915
3	6	3	0.000~0.693	3	7	2	0.000~0.963
5	6	2	0.000~0.985	3	7	3	0.000~0.879

表2 Qn-mk子网络可靠性理论结果的有效性分析

Tab. 2 Validity analysis of theoretical results of Qn-mk subnetwork reliability

k	n	$m$	$p$	k	n	$m$	$p$
3	6	2	0.000~0.897	5	6	3	0.000~0.915
3	6	3	0.000~0.693	3	7	2	0.000~0.963
5	6	2	0.000~0.985	3	7	3	0.000~0.879

图1 Qnk中Qn-mk子网络的可靠性分析结果

Fig. 1 Reliability analysis results of Qn-mk subnetworks in Qnk

参考文献 24

1	HAYES J P， MUDGE T， STOUT Q F， et al. A microprocessor-based hypercube supercomputer［J］. IEEE Micro， 1986， 6（5）： 6-17. 10.1109/mm.1986.304707
2	SAAD Y， SCHULTZ M H. Topological properties of hypercubes［J］. IEEE Transactions on Computers， 1988， 37（7）： 867-872. 10.1109/12.2234
3	EFE K. A variation on the hypercube with lower diameter［J］. IEEE Transactions on Computers， 1991， 40（11）： 1312-1316. 10.1109/12.102840
4	BROOKS E D III. The indirect k-ary n-cube for a vector processing environment［J］. Parallel Computing， 1988， 6（3）： 339-348. 10.1016/0167-8191(88)90074-9
5	ANDERSON E， BROOKS J， GRASSL C， et al. Performance of the CRAY T3E multiprocessor［C］// Proceedings of the 1997 ACM/IEEE Conference on Supercomputing. New York： ACM， 1997： 1-17. 10.1145/509593.509632
6	ADIGA N R， BLUMRICH M A， CHEN D， et al. Blue Gene/L torus interconnection network［J］. IBM Journal of Research and Development， 2005， 49（2/3）： 265-276. 10.1147/rd.492.0265
7	WANG S Y， ZHANG G Z， FENG K. Fault tolerance in k-ary n-cube networks［J］. Theoretical Computer Science， 2012， 460： 34-41. 10.1016/j.tcs.2012.06.013
8	冯凯. k元n方体的条件强匹配排除［J］. 计算机应用， 2017， 37（9）： 2454-2456， 2490. 10.11772/j.issn.1001-9081.2017.09.2454
	FENG K. Conditional strong matching preclusion for k-ary n-cubes［J］. Journal of Computer Applications， 2017， 37（9）： 2454-2456， 2490. 10.11772/j.issn.1001-9081.2017.09.2454
9	冯凯，李婧. k元n方体的可靠性评估［J］. 计算机应用， 2019， 39（11）： 3323-3327. 10.11772/j.issn.1001-9081.2019040714
	FENG K， LI J. Reliability assessment of k-ary n-cube networks［J］. Journal of Computer Applications， 2019， 39（11）： 3323-3327. 10.11772/j.issn.1001-9081.2019040714
10	FENG K， JI Z J， WEI W. Subnetwork reliability analysis in k-ary n-cubes［J］. Discrete Applied Mathematics， 2019， 267： 85-92. 10.1016/j.dam.2019.07.003
11	LV M J， FAN J X， CHEN G， et al. The reliability analysis of k-ary n-cube networks［J］. Theoretical Computer Science， 2020， 835： 1-14. 10.1016/j.tcs.2020.05.003
12	DVOŘÁK T， GU M M. Neighbor connectivity of k-ary n-cubes［J］. Applied Mathematics and Computation， 2020， 379： No.125237. 10.1016/j.amc.2020.125237
13	YANG Y X， ZHANG L L. Hamiltonian paths of k-ary n-cubes avoiding faulty links and passing through prescribed linear forests［J］. IEEE Transactions on Parallel and Distributed Systems， 2022， 33（7）： 1752-1760. 10.1109/tpds.2021.3126254
14	XIE Y H， LIANG J R， YIN W， et al. The properties and t/s-diagnosability of k-ary n-cube networks［J］. The Journal of Supercomputing， 2022， 78（5）： 7038-7057. 10.1007/s11227-021-04155-y
15	DAS C R， KIM J. A unified task-based dependability model for hypercube computers［J］. IEEE Transactions on Parallel and Distributed Systems， 1992， 3（3）： 312-324. 10.1109/71.139205
16	CHANG Y， BHUYAN L N. A combinatorial analysis of subcube reliability in hypercubes［J］. IEEE Transactions on Computers， 1995， 44（7）： 952-956. 10.1109/12.392856
17	WU X L， LATIFI S. Substar reliability analysis in star networks［J］. Information Sciences， 2008， 178（10）： 2337-2348. 10.1016/j.ins.2007.11.015
18	LIN L M， XU L， ZHOU S M， et al. The reliability of subgraphs in the arrangement graph［J］. IEEE Transactions on Reliability， 2015， 64（2）： 807-818. 10.1109/tr.2015.2413372
19	LI X W， ZHOU S M， XU X， et al. The reliability analysis based on subsystems of （n，k）-star graph［J］. IEEE Transactions on Reliability， 2016， 65（4）： 1700-1709. 10.1109/tr.2016.2570544
20	T-L KUNG， TENG Y-H， LIN C-K， et al. Combinatorial analysis of the subsystem reliability of the split-star network［J］. Information Sciences， 2017， 415/416： 28-40. 10.1016/j.ins.2017.06.012
21	HUANG Y Z， LIN L M， WANG D J. On the reliability of alternating group graph-based networks［J］. Theoretical Computer Science， 2018， 728： 9-28. 10.1016/j.tcs.2018.03.010
22	冯凯，马鑫玉. （n，k）-冒泡排序网络的子网络可靠性［J］. 计算机科学， 2021， 48（4）： 43-48. 10.11896/jsjkx.201100139
	FENG K， MA X Y. Subnetwork reliability of （n，k）-bubble-sort networks［J］. Computer Science， 2021， 48（4）： 43-48. 10.11896/jsjkx.201100139
23	BONDY J A， MURTY U S R. Graph Theory， GTM 244［M］. London： Springer， 2008： 1-450. 10.1007/978-1-84628-970-5
24	SANE S S. The inclusion-exclusion principle［M］// Combinatorial Techniques， TRM 65. New Delhi： Hindustan Book Agency， 2013： 57-79. 10.1007/978-93-86279-55-2_4

[1]	冯凯, 李婧. k元n方体的可靠性评估[J]. 计算机应用, 2019, 39(11): 3323-3327.
[2]	冯凯. k元n方体的条件强匹配排除[J]. 计算机应用, 2017, 37(9): 2454-2456.
[3]	张彬连, 徐洪智. 多处理器系统可靠性约束下的节能调度算法[J]. 计算机应用, 2015, 35(6): 1590-1594.
[4]	张彬连徐洪智. 多处理器系统的在线节能调度算法[J]. 计算机应用, 2013, 33(10): 2787-2791.
[5]	赵元庆金显华. 3元n立方网络的2阶超连通性[J]. 计算机应用, 2013, 33(04): 1036-1038.
[6]	兰舟孙世新. 基于关键路径知识的任务调度遗传算法[J]. 计算机应用, 2008, 28(2): 272-274.
[7]	乔保军石峰计卫星. 基三分层网络中的受限多播路由算法[J]. 计算机应用, 2007, 27(4): 801-804.
[8]	乔保军石峰计卫星刘滨 . 基三分层网络中一种基于查表的确定路由算法[J]. 计算机应用, 2006, 26(9): 2162-2165.

概率故障条件下k元（n-m）方体子网络的可靠性

Reliability of k-ary （n-m）-cube subnetworks under probabilistic fault condition

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献 24

相关文章 8

编辑推荐

Metrics