Approximate evaluation method of k-ary （n-1）-cube subnetwork reliability

doi:10.11772/j.issn.1001-9081.2022111719

Abstract

Abstract:

The implementation of the functions of a multiprocessor system relies heavily on the topological properties of the interconnection network of this system. The subnetwork reliability of k-ary n-cube network is an important factor that needs to be taken into account when the computing tasks are processed by the multiprocessor systems constructed with k-ary n-cube as topological structure. In order to accurately and efficiently measure the reliability of the k-ary （n-1）-cube subnetwork in a k-ary n-cube under the probabilistic fault condition， an approximate method to evaluate the reliability of k-ary （n-1）-cube subnetwork based on the Back Propagation （BP） neural network was proposed. Firstly， the generation method for dataset to train BP neural network was given by the aid of the Monte Carlo simulation method and the known upper and lower bounds on the reliability of the k-ary （n-1）-cube subnetwork. Then， the BP neural network model for evaluating the reliability of the k-ary （n-1）-cube subnetwork was constructed on the basis of the generated training dataset. Finally， the approximate evaluation results of the k-ary （n-1）-cube subnetwork reliability obtained by the BP neural network model were analyzed and compared with the results obtained by the approximate calculation formula and the evaluation method based on Monte Carlo simulation. The results obtained by the proposed method were more accurate compared with the approximate calculation formula， and the evaluation time of the proposed method was reduced by about 59% on average compared with the evaluation method based on Monte Carlo simulation. Experimental results show that the proposed method has certain advantages in balancing accuracy and efficiency.

Key words: multiprocessor system, interconnection network, k-ary n-cube, subnetwork reliability, Back Propagation (BP) neural network

摘要：

多处理器系统互连网络的拓扑性质对系统功能的实现起着重要的作用。k元n方体网络的子网络可靠性是以k元n方体为拓扑结构构建的多处理器系统处理计算任务时需要考虑的一个重要因素。为了精确高效地度量概率故障条件下k元n方体中k元（n-1）方体子网络的可靠性，提出基于反向传播（BP）神经网络的k元（n-1）方体子网络可靠性的近似评估方法。首先，利用蒙特卡洛仿真方法和k元（n-1）方体子网络可靠性的已有上下界给出用于训练BP神经网络的数据集的生成方法；其次，基于生成的训练数据集构造用于评估k元（n-1）方体子网络可靠性的BP神经网络模型；最后，对BP神经网络模型得出的k元（n-1）方体子网络可靠性的近似评估结果进行了分析，并与近似计算公式和基于蒙特卡洛的评估方法的结果进行了对比。与近似计算公式相比，所提方法得出的结果更为精确；与基于蒙特卡洛的评估方法相比，所提方法的评估耗时平均减少了约59%。实验结果表明，所提方法在兼顾精度和效率方面具有一定优势。

关键词: 多处理器系统, 互连网络, k元n方体, 子网络可靠性, 反向传播神经网络

CLC Number:

TP393.02

Kai FENG, Jiande LI, Zhangjian JI. Approximate evaluation method of k-ary （n-1）-cube subnetwork reliability[J]. Journal of Computer Applications, 2023, 43(12): 3875-3881.

冯凯, 李建德, 姬张建. k元（n-1）方体子网络可靠性的近似评估方法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3875-3881.

Figures/Tables 9

Tab.1 Validity analysis on upper and lower bounds of Rn,n-1k(p)

$Q n k$	$R U (p) - R L (p) ≤ δ$ 成立的 $p$ 的取值范围
$Q 33$	［0，0.688 8］
$Q 43$	［0，0.855 5］
$Q 35$	［0，0.867 5］
$Q 45$	［0，0.967 9］
$Q 53$	［0，0.942 3］
$Q 63$	［0，0.978 6］

Tab.1 Validity analysis on upper and lower bounds of Rn,n-1k(p)

$Q n k$	$R U (p) - R L (p) ≤ δ$ 成立的 $p$ 的取值范围
$Q 33$	［0，0.688 8］
$Q 43$	［0，0.855 5］
$Q 35$	［0，0.867 5］
$Q 45$	［0，0.967 9］
$Q 53$	［0，0.942 3］
$Q 63$	［0，0.978 6］

Fig.1 Structure of BP neural network forevaluating Qn-1k subnetwork reliability

Fig. 2 Calculation results of minimum simulation times with different confidence

Fig.3 Comparison of prediction accuracies of BP neural network with different hidden layer nodes

Fig.4 Comparison of training time of BP neural network with different initial learning rates

Tab. 2 Mean values of root mean square error on test sets ofdifferent datasets

数据集	RMSE平均值	数据集	RMSE平均值
$D (Q 33)$	0.001 8	$D (Q 45)$	0.000 9
$D (Q 43)$	0.001 3	$D (Q 53)$	0.001 0
$D (Q 35)$	0.001 1	$D (Q 63)$	0.000 9

Tab. 2 Mean values of root mean square error on test sets ofdifferent datasets

数据集	RMSE平均值	数据集	RMSE平均值
$D (Q 33)$	0.001 8	$D (Q 45)$	0.000 9
$D (Q 43)$	0.001 3	$D (Q 53)$	0.001 0
$D (Q 35)$	0.001 1	$D (Q 63)$	0.000 9

Fig.5 Evaluation results of BP neural network model

Fig. 6 Comparison of different evaluation results with true values

Tab.3 Evaluation time and RMSE of two methods

$Q n k$	基于BP神经网络的评估方法的耗时/s	基于蒙特卡洛模拟的评估方法的耗时/s	$R M S E$
$Q 33$	35.830 8	87.124 9	0.003 4
$Q 43$	41.399 8	103.177 7	0.003 2
$Q 35$	43.346 8	113.514 3	0.003 2
$Q 45$	64.238 6	158.609 7	0.004 1
$Q 53$	50.139 6	121.206 7	0.003 6
$Q 63$	69.456 5	172.031 8	0.004 6

Tab.3 Evaluation time and RMSE of two methods

$Q n k$	基于BP神经网络的评估方法的耗时/s	基于蒙特卡洛模拟的评估方法的耗时/s	$R M S E$
$Q 33$	35.830 8	87.124 9	0.003 4
$Q 43$	41.399 8	103.177 7	0.003 2
$Q 35$	43.346 8	113.514 3	0.003 2
$Q 45$	64.238 6	158.609 7	0.004 1
$Q 53$	50.139 6	121.206 7	0.003 6
$Q 63$	69.456 5	172.031 8	0.004 6

References 24

1	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
2	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
3	WU X， LATIFI S. Substar reliability analysis in star networks ［J］. Information Sciences， 2008， 178（10）： 2337-2348. 10.1016/j.ins.2007.11.015
4	LIN L， XU L， ZHOU S， 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
5	LI X， ZHOU S， 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
6	HUANG Y， LIN L， WANG D. On the reliability of alternating group graph-based networks［J］. Theoretical Computer Science， 2018， 728： 9-28. 10.1016/j.tcs.2018.03.010
7	ZHANG Q， XU L， ZHOU S， et al. Reliability analysis of subsystem in dual cubes ［J］. Theoretical Computer Science， 2020， 816： 249-259. 10.1016/j.tcs.2020.02.028
8	FENG K， MA X， WEI W. Subnetwork reliability analysis of bubble-sort graph networks［J］. Theoretical Computer Science， 2021， 896： 98-110. 10.1016/j.tcs.2021.10.007
9	LV M， FAN J， FAN W， et al. Fault diagnosis based on subsystem structures of data center network BCube ［J］. IEEE Transactions on Reliability， 2022， 71（2）： 963-972. 10.1109/tr.2021.3140069
10	LIU X， ZHOU S， LIU J， et al. Reliability analysis of the cactus-based networks based on subsystem［J］. The Computer Journal， 2022，2022： No.bxac163. 10.1093/comjnl/bxac163
11	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
12	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
13	FENG K， JI Z， 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
14	LV Y， FAN J， HSU D F， et al. Structure connectivity and substructure connectivity of k-ary n-cube networks［J］. Information Sciences， 2018， 433/434： 115-124. 10.1016/j.ins.2017.11.047
15	LIU A， WANG S， YUAN J， et al. The h-extra connectivity of k-ary n-cubes［J］. Theoretical Computer Science， 2019， 784： 21-45. 10.1016/j.tcs.2019.03.030
16	WANG S， ZHANG G， 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
17	YANG Y， LI J， WANG S. Embedding various cycles with prescribed paths into k-ary n-cubes［J］. Discrete Applied Mathematics， 2017， 220： 161-169. 10.1016/j.dam.2016.12.006
18	冯凯，李婧. k元n方体的子网络可靠性研究［J］. 计算机科学， 2020， 47（7）： 31-36. 10.11896/jsjkx.190700170
	FENG K， LI J. Study on subnetwork reliability of k-ary n-cubes ［J］. Computer Science， 2020， 47（7）： 31-36. 10.11896/jsjkx.190700170
19	LV M， FAN J， 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
20	CHEN X B. Paired 2-disjoint path covers of faulty k-ary n-cubes［J］. Theoretical Computer Science， 2016， 609（Pt 2）： 494-499. 10.1016/j.tcs.2015.11.007
21	谢丽霞，王志华. 基于布谷鸟搜索优化BP神经网络的网络安全态势评估方法［J］. 计算机应用， 2017， 37（7）： 1926-1930. 10.11772/j.issn.1001-9081.2017.07.1926
	XIE L X， WANG Z H. Network security situation assessment method based on cuckoo search optimized back propagation neural network［J］. Journal of Computer Applications， 2017， 37（7）： 1926-1930. 10.11772/j.issn.1001-9081.2017.07.1926
22	戴宏亮，罗裕达. 基于蝙蝠算法优化反向传播神经网络模型的无线网络流量预测［J］. 计算机应用， 2021， 41（S1）：185-188. 10.11772/j.issn.1001-9081.2020101679
	DAI H L， LUO Y D. Wireless network traffic prediction based on bat algorithm optimized back propagation neural network model［J］. Journal of Computer Applications， 2021， 41（S1）： 185-188. 10.11772/j.issn.1001-9081.2020101679
23	HORNIK K， STINCHCOMBE M， WHITE H. Multilayer feedforward networks are universal approximators［J］. Neural Networks， 1989， 2（5）： 359-366. 10.1016/0893-6080(89)90020-8
24	盛骤，谢式千，潘承毅. 概率论与数理统计［M］. 4版. 北京：高等教育出版社， 2008： 119-126.
	SHENG Z， XIE S Q， PAN C Y. Probability Theory and Mathematical Statistics［M］. 4th ed. Beijing： Higher Education Press， 2008： 119-126.

[1]	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.
[2]	Jialiang DUAN, Guoming CAI, Kaiyong XU. Memory combined feature classification method based on multiple BP neural networks [J]. Journal of Computer Applications, 2022, 42(1): 178-182.
[3]	CHU Surong, NIU Zhixian, SONG Chunhua, NIU Baoning. Progressive mesh simplification algorithm for mobile devices [J]. Journal of Computer Applications, 2020, 40(3): 806-811.
[4]	HAN Ying, ZHAO Meng, CHEN Shengyong, WANG Zhaoxi. Automatic screening of abnormal cervical nucleus based on maximum section feature [J]. Journal of Computer Applications, 2019, 39(4): 1189-1195.
[5]	FENG Kai, LI Jing. Reliability assessment of k-ary n-cube networks [J]. Journal of Computer Applications, 2019, 39(11): 3323-3327.
[6]	CHEN Wanzhi, LI Dongzhe. Intrusion detection method in industrial control network combining white list filtering and neural network [J]. Journal of Computer Applications, 2018, 38(2): 363-369.
[7]	HE Chun, LI Qi, WU Ranghao, LIU Bangxin. Diagnosis of fault circuit by modularized BP neural network based on fault propagation [J]. Journal of Computer Applications, 2018, 38(2): 602-609.
[8]	FENG Kai. Conditional strong matching preclusion for k-ary n-cubes [J]. Journal of Computer Applications, 2017, 37(9): 2454-2456.
[9]	CHEN Haoguang, WANG Yinhe. Adaptive control design for a class of nonlinear systems based on extended BP neural network [J]. Journal of Computer Applications, 2017, 37(6): 1670-1673.
[10]	ZHENG Cha, JI Lixin, LI Shaomei, GAO Chao. Face annotation in news images based on multi-modal information fusion [J]. Journal of Computer Applications, 2017, 37(10): 3006-3011.
[11]	LI Mingxu, DENG Xin, WANG Jin, WANG Xiao, ZHANG Xiaomou. Modeling and simulating thermotaxis behavior of Caenorhabditis elegans based on artificial neural network [J]. Journal of Computer Applications, 2016, 36(7): 1909-1913.
[12]	QIU Yana, YANG Yuxing. Link connectivity and restricted link connectivity of augmented bubble-sort networks [J]. Journal of Computer Applications, 2016, 36(11): 3006-3009.
[13]	YANG Kangkang, WU Shijing, LIU Yujie, ZHOU Lu. Conflict detection model in collaborative design based on constraint [J]. Journal of Computer Applications, 2015, 35(8): 2215-2220.
[14]	ZHANG Binlian, XU Hongzhi. Energy-efficient scheduling algorithm under reliability constraint in multiprocessor system [J]. Journal of Computer Applications, 2015, 35(6): 1590-1594.
[15]	SHAO Liangshan, GUO Yachan. Flame recognition algorithm based on Codebook in video [J]. Journal of Computer Applications, 2015, 35(5): 1483-1487.