计算机科学 ›› 2021, Vol. 48 ›› Issue (4): 43-48.doi: 10.11896/jsjkx.201100139
冯凯, 马鑫玉
FENG Kai, MA Xin-yu
摘要： 并行计算机系统互连网络的拓扑性质对系统功能的实现起着重要的作用。为了精确度量基于(n,k)-冒泡排序网络构建的并行计算机系统的子网络容错能力,建立了(n,k)-冒泡排序网络中(n－m,k－m)-冒泡排序子网络与特定字符串之间的一一对应关系,研究了点故障模型下(n,k)-冒泡排序网络中(n－m,k－m)-冒泡排序子网络的可靠性。当2≤k≤n－2,1≤m≤k－1时,首先在概率故障条件下给出了(n,k)-冒泡排序网络中存在无故障的(n－m,k－m)-冒泡排序子网络的概率估计,并通过仿真实验验证了所得结果的精确性;其次,得出了不同数目的(n－m,k－m)-冒泡排序子网络保持无故障状态的平均失效时间的计算公式,仿真实验表明理论结果与仿真结果趋于一致。
中图分类号:
| [1]CHANG Y,BHUYAN L N.A combinatorial analysis of subcube reliability in hypercube[J].IEEE Transactions on Compu-ters,1995,44(7):952-956. [2]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. [3]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. [4]KUNG T L,TENG Y H,LIN C K,et al.Combinatorial analysisof the subsystem reliability of the split-star network[J].Information Sciences,2017,415:28-40. [5]FENG K,JI Z,WEI W.Subnetwork reliability analysis in k-ary n-cubes[J].Discrete Applied Mathematics,2019,267:85-92. [6]ABRAHAM S,PADMANABHAN K.Reliability of the hypercube[C]//Proceedings of the 1988 International Conference on Parallel Processing.Piscataway:IEEE,1988:90-94. [7]ZHOU S,LI X,LI J,et al.Reliability assessment of multiprocessor system based on (n,k)-star network[J].IEEE Transactions on Reliability,2017,66(4):1025-1035. [8]LV M,ZHOU S,SUN X,et al.Reliability evaluation of datacenter network DCell[J].Parallel Processing Letters,2018,28(4):1850015. [9]FENG K,LI J.Reliability assessment of k-ary n-cube networks[J].Journal of Computer Applications,2019,39(11):3323-3327. [10]SHAWASH N.Relationships among popular interconnectionnetworks and their common generalization[D].Oakland:Oakland University,2008. [11]CHENG E,LIPTÁK L,SHERMAN D.Matching preclusion for the (n,k)-bubble-sort graphs[J].International Journal of Computer Mathematics,2010,87(11):2408-2418. [12]YANG Y X,QIU Y N.Sub-network preclusion in(n,k)-bubble-sort networks[J].Computer Science,2017,44(11):264-267. [13]ZHAO S,HAO R,WU L.The generalized connectivity of (n,k)-bubble-sort graphs[J].The Computer Journal,2019,62(9):1277-1283. [14]ZHAO S,HAO R.The fault tolerance of(n,k)-bubble-sort networks[J].Discrete Applied Mathematics,2020,285:204-211. [15]BONDY J A,MURTY U S R.Graph Theory[M].New York:Springer,2008:1-356. [16]SANE S.Combinatorial Techniques[M].New Delhi:Hindustan Book Agency,2016:57-79. |
| [1] | 徐佳庆, 胡小月, 唐付桥, 王强, 何杰. 基于随机森林的高性能互连网络阻塞故障检测 Detecting Blocking Failure in High Performance Interconnection Networks Based on Random Forest 计算机科学, 2021, 48(6): 246-252. https://doi.org/10.11896/jsjkx.201200142 |
| [2] | 冯凯, 李婧. k元n方体的子网络可靠性研究 Study on Subnetwork Reliability of k-ary n-cubes 计算机科学, 2020, 47(7): 31-36. https://doi.org/10.11896/jsjkx.190700170 |
| [3] | 师腾, 师海忠. 互连网络的模p剩余类加群的笛卡尔积模型 Model of Cartesian Product of Modulo p Residual Class Addition Group for Interconnection Networks 计算机科学, 2020, 47(6A): 299-304. https://doi.org/10.11896/JsJkx.190700047 |
| [4] | 林政宽,赵源,樊建席,程宝雷. 基于顶点度数的完全独立生成树研究 Research on Completely Independent Spanning Trees Based on Degree of Vertices 计算机科学, 2017, 44(6): 94-96. https://doi.org/10.11896/j.issn.1002-137X.2017.06.016 |
| [5] | 杨玉星,邱亚娜. k元n维冒泡排序网络的子网排除 Sub-network Preclusion in (n,k)-bubble-sort Networks 计算机科学, 2017, 44(11): 264-267. https://doi.org/10.11896/j.issn.1002-137X.2017.11.039 |
| [6] | 师海忠,常立婷,赵媛,张欣,王海锋. 2r-正则图连通圈网络的Hamilton分解 Hamiltonian Decomposition of 2r-regular Graph Connected Cycles Networks 计算机科学, 2016, 43(Z11): 304-307. https://doi.org/10.11896/j.issn.1002-137X.2016.11A.071 |
| [7] | 师海忠. 几类新的笛卡尔乘积互连网络 Some New Cartesian Product Interconnection Networks 计算机科学, 2013, 40(Z6): 265-270. |
| [8] | 师海忠. 互连网络的新模型:多部群论模型 New Model for Interconnection Networks:Multipartite Group-theoretic Model 计算机科学, 2013, 40(9): 21-24. |
| [9] | 师海忠，王国亮，马继勇，侯斐斐. 完全对换网络的一簇猜想 One Variety Conjectures of Complete-transposition Network 计算机科学, 2012, 39(Z6): 404-407. |
| [10] | 李勇,樊建席,王喜,周吴军. LHL-立方体互连网络及其性质 LHL-cube Interconnection Networks and their Properties 计算机科学, 2010, 37(8): 83-87. |
| [11] | 梁家荣,花仁杰. 具有失效链路的star网络可靠性分析 Reliability Analysis of star Network with Link Failures 计算机科学, 2010, 37(6): 106-110. |
| [12] | . 代数图论方法在并行处理中的应用研究 计算机科学, 2008, 35(11): 67-69. |
| [13] | . 基三分层互连网络和2-D Mesh的比较 计算机科学, 2007, 34(9): 253-255. |
| [14] | 李涛 陈宇明 赵精龙 倪长顺 杨愚鲁. 集群高速互连网络分析 计算机科学, 2005, 32(10): 20-22. |
| [15] | 曾庆华 陈天麒. 可扩展并行计算机系统结构和发展现状 计算机科学, 2003, 30(9): 158-161. |
|
||