计算机科学 ›› 2020, Vol. 47 ›› Issue (7): 31-36.doi: 10.11896/jsjkx.190700170
冯凯, 李婧
FENG Kai, LI Jing
摘要: k元n方体是并行计算机系统最常用的互连网络拓扑结构之一。为了精确度量k元n方体中子网络的容错能力,研究了概率故障条件下k元n方体中k元(n-1)方体子网络的可靠性。当k(k≥3)为奇整数时,通过厘清k元n方体中不同k元(n-1)方体子网络之间的相交情形,得出了k元(n-1)方体子网络的可靠性的一个下界,并给出了该可靠性的一个近似结果。实验结果表明,得出的近似结果与仿真结果十分接近,并且随着顶点可靠性的降低两者趋于一致。进一步地,提出了在发生点故障的k元n方体中搜寻k元(n-1)方体子网络的算法,并通过实例验证了该算法的有效性。
中图分类号:
[1]CHANG Y,BHUYAN L.A combinatorial analysis of subcubereliability in hypercube[J].IEEE Transactions on Computers,1995,44(7):952-956. [2]WU X,LATIFI S.Substar reliability analysis in star networks[J].Information Sciences,2008,178:2337-2348. [3]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. [4]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. [5]MAO W,NICOL D M.On k-ary n-cubes:theory and applica-tions[J].Discrete Applied Mathematics,2003,129(1):171-193. [6]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 Press,1997:1-17. [7]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. [8]CHEN X-B.Paired 2-disjoint path covers of faulty k-ary n-cubes[J].Theoretical Computer Science,2016,609:494-499. [9]FENG K,JI Z,WEI W.Subnetwork reliability analysis in k-ary n-cubes[J].Discrete Applied Mathematics,2019,267:85-92. [10]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. [11]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. [12]WANG S,ZHANG G,FENG K.Fault tolerance in k-ary n-cube networks[J].Theoretical Computer Science,2012,460:34-41. [13]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. [14]BONDY J A,MURTY U S R.Graph Theory[M].New York:Springer,2008:1-450. [15]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] | 冯凯, 马鑫玉. (n,k)-冒泡排序网络的子网络可靠性 Subnetwork Reliability of (n,k)-bubble-sort Networks 计算机科学, 2021, 48(4): 43-48. https://doi.org/10.11896/jsjkx.201100139 |
[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. |
|