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

馮凱，李建德，姬張建

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

馮凱*，李建德，姬張建

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

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

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

0 引言

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

對(duì)于一些特定的用戶任務(wù)，多處理器系統(tǒng)只需指派系統(tǒng)的某個(gè)子網(wǎng)絡(luò)（具有與系統(tǒng)互連網(wǎng)絡(luò)相同的拓?fù)湫再|(zhì)，但規(guī)模較小的網(wǎng)絡(luò)）執(zhí)行，不僅可以減少資源消耗，還可以避免大規(guī)模網(wǎng)絡(luò)有效性較差的缺點(diǎn)。由于實(shí)際構(gòu)建的大規(guī)模多處理器系統(tǒng)中發(fā)生故障是不可避免的，網(wǎng)絡(luò)中較小規(guī)模子網(wǎng)絡(luò)的可靠性研究對(duì)系統(tǒng)實(shí)際應(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ò)是處理非線性問(wèn)題的有效工具，可以通過(guò)監(jiān)督學(xué)習(xí)解決回歸問(wèn)題。BP神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)分為輸入層、隱藏層和輸出層，它利用鏈?zhǔn)椒▌t通過(guò)反向傳播更新網(wǎng)絡(luò)參數(shù)，以減小損失函數(shù)數(shù)值，完成模型的訓(xùn)練。Hornik等［23］在理論上證明，構(gòu)造一個(gè)3層神經(jīng)網(wǎng)絡(luò)能夠以任意精度逼近任何非線性函數(shù)。給定訓(xùn)練集，BP神經(jīng)網(wǎng)絡(luò)可以以較高精度實(shí)現(xiàn)從輸入到輸出的映射功能。

圖1　用于評(píng)估子網(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ù)計(jì)算結(jié)果

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

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

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

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

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

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

2.3.3模型結(jié)果分析

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

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

2.3.4對(duì)比實(shí)驗(yàn)結(jié)果

圖6　不同評(píng)估結(jié)果與真值的對(duì)比

表3兩種方法的評(píng)估時(shí)長(zhǎng)及RMSE

Tab.3　Evaluation time and RMSE of two methods

3 結(jié)語(yǔ)

隨著多處理器系統(tǒng)應(yīng)用領(lǐng)域的不斷擴(kuò)大，系統(tǒng)互連網(wǎng)絡(luò)的設(shè)計(jì)需求日趨多樣化，許多新型互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)被相繼提出。利用基于BP神經(jīng)網(wǎng)絡(luò)的子網(wǎng)絡(luò)可靠性的近似評(píng)估方法對(duì)新型互連網(wǎng)絡(luò)的子網(wǎng)絡(luò)可靠性進(jìn)行評(píng)估值得進(jìn)一步研究，這將有助于新型互連網(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］. 計(jì)算機(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] 謝麗霞，王志華. 基于布谷鳥(niǎo)搜索優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)安全態(tài)勢(shì)評(píng)估方法［J］. 計(jì)算機(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ú)線網(wǎng)絡(luò)流量預(yù)測(cè)［J］. 計(jì)算機(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)計(jì)［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。

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

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