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

Study on Subnetwork Reliability of k-ary n-cubes

作　　者：冯凯[1] 李婧 FENG Kai;LI Jing(School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China)

机构地区：[1]山西大学计算机与信息技术学院,太原030006

出　　处：《计算机科学》2020年第7期31-36,共6页Computer Science

基　　金：国家自然科学基金(61502286);山西省应用基础研究项目(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)方体子网络的算法,并通过实例验证了该算法的有效性。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.

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

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]