馮凱，李建德，姬張建

元（-1）方體子網(wǎng)絡(luò)可靠性的近似評估方法

馮凱*，李建德，姬張建

（山西大學(xué) 計算機與信息技術(shù)學(xué)院，太原 030006）（?通信作者電子郵箱fengkai@sxu.edu.cn）

多處理器系統(tǒng)互連網(wǎng)絡(luò)的拓?fù)湫再|(zhì)對系統(tǒng)功能的實現(xiàn)起著重要的作用。元方體網(wǎng)絡(luò)的子網(wǎng)絡(luò)可靠性是以元方體為拓?fù)浣Y(jié)構(gòu)構(gòu)建的多處理器系統(tǒng)處理計算任務(wù)時需要考慮的一個重要因素。為了精確高效地度量概率故障條件下元方體中元（-1）方體子網(wǎng)絡(luò)的可靠性，提出基于反向傳播（BP）神經(jīng)網(wǎng)絡(luò)的元（-1）方體子網(wǎng)絡(luò)可靠性的近似評估方法。首先，利用蒙特卡洛仿真方法和元（-1）方體子網(wǎng)絡(luò)可靠性的已有上下界給出用于訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)集的生成方法；其次，基于生成的訓(xùn)練數(shù)據(jù)集構(gòu)造用于評估元（-1）方體子網(wǎng)絡(luò)可靠性的BP神經(jīng)網(wǎng)絡(luò)模型；最后，對BP神經(jīng)網(wǎng)絡(luò)模型得出的元（-1）方體子網(wǎng)絡(luò)可靠性的近似評估結(jié)果進行了分析，并與近似計算公式和基于蒙特卡洛的評估方法的結(jié)果進行了對比。與近似計算公式相比，所提方法得出的結(jié)果更為精確；與基于蒙特卡洛的評估方法相比，所提方法的評估耗時平均減少了約59%。實驗結(jié)果表明，所提方法在兼顧精度和效率方面具有一定優(yōu)勢。

多處理器系統(tǒng)；互連網(wǎng)絡(luò)；元方體；子網(wǎng)絡(luò)可靠性；反向傳播神經(jīng)網(wǎng)絡(luò)

0 引言

科學(xué)與工程計算領(lǐng)域的許多問題都有龐大的信息量和計算量，如流體動力學(xué)分析、社會經(jīng)濟預(yù)測、材料建模與設(shè)計等，這些課題對計算性能提出了極高的要求。為了滿足人們對計算能力日益增長的需求，利用以某種模式連接的多處理器分?jǐn)側(cè)蝿?wù)進行協(xié)同并行計算是一種有效的解決方案，多處理器系統(tǒng)應(yīng)運而生。隨著多處理器系統(tǒng)規(guī)模的不斷增大，系統(tǒng)功能的實現(xiàn)越來越依賴于它的支撐通信和數(shù)據(jù)交互的連接模式（即系統(tǒng)的互連網(wǎng)絡(luò)，其中系統(tǒng)中的處理器用點表示，處理器之間的通信線路用邊表示）。

對于一些特定的用戶任務(wù)，多處理器系統(tǒng)只需指派系統(tǒng)的某個子網(wǎng)絡(luò)（具有與系統(tǒng)互連網(wǎng)絡(luò)相同的拓?fù)湫再|(zhì)，但規(guī)模較小的網(wǎng)絡(luò)）執(zhí)行，不僅可以減少資源消耗，還可以避免大規(guī)模網(wǎng)絡(luò)有效性較差的缺點。由于實際構(gòu)建的大規(guī)模多處理器系統(tǒng)中發(fā)生故障是不可避免的，網(wǎng)絡(luò)中較小規(guī)模子網(wǎng)絡(luò)的可靠性研究對系統(tǒng)實際應(yīng)用至關(guān)重要。

1 準(zhǔn)備工作

Tab.1　Validity analysis on upper and lower bounds of

2 本文方法

2.1　方法介紹

BP神經(jīng)網(wǎng)絡(luò)是處理非線性問題的有效工具，可以通過監(jiān)督學(xué)習(xí)解決回歸問題。BP神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)分為輸入層、隱藏層和輸出層，它利用鏈?zhǔn)椒▌t通過反向傳播更新網(wǎng)絡(luò)參數(shù)，以減小損失函數(shù)數(shù)值，完成模型的訓(xùn)練。Hornik等［23］在理論上證明，構(gòu)造一個3層神經(jīng)網(wǎng)絡(luò)能夠以任意精度逼近任何非線性函數(shù)。給定訓(xùn)練集，BP神經(jīng)網(wǎng)絡(luò)可以以較高精度實現(xiàn)從輸入到輸出的映射功能。

圖1　用于評估子網(wǎng)絡(luò)可靠性的 BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

2.2　數(shù)據(jù)集生成方法

算法1 訓(xùn)練數(shù)據(jù)集生成算法。

10） else

19） end if

20） end for

24） else

26） end if

27） end for

29） end if

30） end for

圖2　不同置信度下最小模擬次數(shù)計算結(jié)果

2.3　BP神經(jīng)網(wǎng)絡(luò)模型

2.3.1隱層節(jié)點數(shù)的選擇

圖3　不同隱層節(jié)點數(shù)下BP神經(jīng)網(wǎng)絡(luò)的預(yù)測精度對比

2.3.2初始學(xué)習(xí)率的選擇

從圖4可以看出，對于不同的訓(xùn)練數(shù)據(jù)集，不同初始學(xué)習(xí)率對BP神經(jīng)網(wǎng)絡(luò)模型訓(xùn)練時長的影響均不明顯。本文選取初始學(xué)習(xí)率為0.15。

圖4　不同初始學(xué)習(xí)率下BP神經(jīng)網(wǎng)絡(luò)的訓(xùn)練時間對比

2.3.3模型結(jié)果分析

表2　不同數(shù)據(jù)集的測試集上的均方根誤差的平均值

圖5　BP神經(jīng)網(wǎng)絡(luò)模型的評估結(jié)果

2.3.4對比實驗結(jié)果

圖6　不同評估結(jié)果與真值的對比

表3兩種方法的評估時長及RMSE

Tab.3　Evaluation time and RMSE of two methods

3 結(jié)語

隨著多處理器系統(tǒng)應(yīng)用領(lǐng)域的不斷擴大，系統(tǒng)互連網(wǎng)絡(luò)的設(shè)計需求日趨多樣化，許多新型互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)被相繼提出。利用基于BP神經(jīng)網(wǎng)絡(luò)的子網(wǎng)絡(luò)可靠性的近似評估方法對新型互連網(wǎng)絡(luò)的子網(wǎng)絡(luò)可靠性進行評估值得進一步研究，這將有助于新型互連網(wǎng)絡(luò)在多處理器系統(tǒng)中的應(yīng)用和推廣。

[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.

[2] CHANG Y， BHUYAN L N. A combinatorial analysis of subcube reliability in hypercubes［J］. IEEE Transactions on Computers， 1995， 44（7）： 952-956.

[3] WU X， LATIFI S. Substar reliability analysis in star networks ［J］. Information Sciences， 2008， 178（10）： 2337-2348.

[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.

[5] LI X， ZHOU S， XU X， et al. The reliability analysis based on subsystems of （，）-star graph［J］. IEEE Transactions on Reliability， 2016， 65（4）： 1700-1709.

[6] HUANG Y， LIN L， WANG D. On the reliability of alternating group graph-based networks［J］. Theoretical Computer Science， 2018， 728： 9-28.

[7] ZHANG Q， XU L， ZHOU S， et al. Reliability analysis of subsystem in dual cubes ［J］. Theoretical Computer Science， 2020， 816： 249-259.

[8] FENG K， MA X， WEI W. Subnetwork reliability analysis of bubble-sort graph networks［J］. Theoretical Computer Science， 2021， 896： 98-110.

[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] 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.

[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.

[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.

[13] FENG K， JI Z， WEI W. Subnetwork reliability analysis in-ary-cubes ［J］. Discrete Applied Mathematics， 2019， 267： 85-92.

[14] LV Y， FAN J， HSU D F， et al. Structure connectivity and substructure connectivity of-ary-cube networks［J］. Information Sciences， 2018， 433/434： 115-124.

[15] LIU A， WANG S， YUAN J， et al. The h-extra connectivity of-ary-cubes［J］. Theoretical Computer Science， 2019， 784： 21-45.

[16] WANG S， ZHANG G， FENG K. Fault tolerance in-ary-cube networks ［J］. Theoretical Computer Science， 2012， 460： 34-41.

[17] YANG Y， LI J， WANG S. Embedding various cycles with prescribed paths into-ary-cubes［J］. Discrete Applied Mathematics， 2017， 220： 161-169.

[18] 馮凱，李婧.元方體的子網(wǎng)絡(luò)可靠性研究［J］. 計算機科學(xué)， 2020， 47（7）： 31-36.（FENG K， LI J. Study on subnetwork reliability of-ary-cubes ［J］. Computer Science， 2020， 47（7）： 31-36.）

[19] LV M， FAN J， CHEN G，et al. The reliability analysis of-ary-cube networks ［J］. Theoretical Computer Science， 2020， 835： 1-14.

[20] CHEN X B. Paired 2-disjoint path covers of faulty-ary-cubes［J］. Theoretical Computer Science， 2016， 609（Pt 2）： 494-499.

[21] 謝麗霞，王志華. 基于布谷鳥搜索優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)安全態(tài)勢評估方法［J］. 計算機應(yīng)用， 2017， 37（7）： 1926-1930.（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.）

[22] 戴宏亮，羅裕達(dá). 基于蝙蝠算法優(yōu)化反向傳播神經(jīng)網(wǎng)絡(luò)模型的無線網(wǎng)絡(luò)流量預(yù)測［J］. 計算機應(yīng)用， 2021， 41（S1）：185-188.（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.）

[23] HORNIK K， STINCHCOMBE M， WHITE H. Multilayer feedforward networks are universal approximators［J］. Neural Networks， 1989， 2（5）： 359-366.

[24] 盛驟，謝式千，潘承毅. 概率論與數(shù)理統(tǒng)計［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.）

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

FENG Kai*， LI Jiande， JI Zhangjian

（，，030006，）

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-ary-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-ary-cube as topological structure. In order to accurately and efficiently measure the reliability of the-ary （-1）-cube subnetwork in a-ary-cube under the probabilistic fault condition， an approximate method to evaluate the reliability of-ary （-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-ary （-1）-cube subnetwork. Then， the BP neural network model for evaluating the reliability of the-ary （-1）-cube subnetwork was constructed on the basis of the generated training dataset. Finally， the approximate evaluation results of the-ary （-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.

multiprocessor system; interconnection network;-ary-cube; subnetwork reliability; Back Propagation (BP) neural network

This work is partially supported by National Natural Science Foundation of China （61502286）， Basic Research Program of Shanxi Province （20210302123438）.

FENG Kai， born in 1987， Ph. D.， associate professor. His research interests include fault tolerance of interconnection network， graph theory and its applications.

LI Jiande， born in 1997， M. S. candidate. His research interests include fault tolerance of interconnection network.

JI Zhangjian， born in 1983， Ph. D.， associate professor. His research interests include pattern recognition， machine learning.

TP393.02

A

1001-9081（2023）12-3875-07

10.11772/j.issn.1001-9081.2022111719

2022?11?18；

2023?04?10；

2023?04?30。

國家自然科學(xué)基金資助項目（61502286）；山西省基礎(chǔ)研究計劃項目（20210302123438）。

馮凱（1987—），男，山西臨汾人，副教授，博士，CCF會員，主要研究方向：互連網(wǎng)絡(luò)的容錯性、圖論及其應(yīng)用；李建德（1997—），男，山西太原人，碩士研究生，CCF會員，主要研究方向：互連網(wǎng)絡(luò)的容錯性；姬張建（1983—），男，陜西澄城人，副教授，博士，CCF會員，主要研究方向：模式識別、機器學(xué)習(xí)。