计算机科学 ›› 2020, Vol. 47 ›› Issue (7): 31-36.doi: 10.11896/jsjkx.190700170

• 计算机科学理论 • 上一篇    下一篇

k元n方体的子网络可靠性研究

冯凯, 李婧   

  1. 山西大学计算机与信息技术学院 太原030006
  • 收稿日期:2019-07-25 出版日期:2020-07-15 发布日期:2020-07-16
  • 通讯作者: 冯凯(fengkai@sxu.edu.cn)
  • 基金资助:
    国家自然科学基金(61502286);山西省应用基础研究项目(201701D221099)

Study on Subnetwork Reliability of k-ary n-cubes

FENG Kai, LI Jing   

  1. School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China
  • Received:2019-07-25 Online:2020-07-15 Published:2020-07-16
  • About author:FENG Kai,born in 1987,Ph.D,associate professor,master supervisor,is a member of China Computer Federation.His main research interests include fault-tolerance of interconnection network,graph theory and its applications.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China (61502286) and Applied Basic Research Project of Shanxi Province (201701D221099)

摘要: 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)方体子网络的算法,并通过实例验证了该算法的有效性。

关键词: k元n方体, 并行计算机系统, 概率故障, 互连网络, 子网络可靠性

Abstract: The k-ary n-cube is one of the most attractive interconnection network topologies for parallel computing systems.In order to accurately measure the fault tolerance on subnetworks in a k-ary n-cube,the k-ary (n-1)-cube reliability in a k-ary n-cube under the probabilistic fault model is studied.When k is an odd integer and k≥3,a lower bound on the k-ary (n-1)-cube reliability in a k-ary n-cube under the probability fault model is derived by clarifying the intersections of k-ary (n-1)-cube subnetworks in a k-ary n-cube,and an approximate k-ary (n-1)-cube reliability result is obtained.The approximation result is shown to be close to the simulation result,and these two results are getting overlapped as the node reliability decreases.Moreover,an algorithm is given for searching fault-free k-ary (n-1)-cubes in a k-ary n-cube in the presence of node failures,and the experimental results demonstrate the effectiveness of the proposed algorithm.

Key words: k-ary n-cube, Interconnection network, Parallel computer system, Probabilistic failure, Subnetwork reliability

中图分类号: 

  • TP393.02
[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.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!