k元n方体的可靠性评估

doi:10.11772/j.issn.1001-9081.2019040714

计算机应用 ›› 2019, Vol. 39 ›› Issue (11): 3323-3327.DOI: 10.11772/j.issn.1001-9081.2019040714

k元n方体的可靠性评估

冯凯, 李婧

山西大学计算机与信息技术学院, 太原 030006

收稿日期:2019-04-26 修回日期:2019-06-22 出版日期:2019-11-10 发布日期:2019-08-21
通讯作者: 冯凯
作者简介:冯凯(1987-),男,山西临汾人,副教授,博士,CCF会员,主要研究方向:互连网络的容错性、图论及其应用;李婧(1996-),女,山西长治人,硕士研究生,主要研究方向:互连网络的容错性。
基金资助:
国家自然科学基金资助项目（61502286）；山西省应用基础研究项目（201701D221099）。

Reliability assessment of k-ary n-cube networks

FENG Kai, LI Jing

School of Computer and Information Technology, Shanxi University, Taiyuan Shanxi 030006, China

Received:2019-04-26 Revised:2019-06-22 Online:2019-11-10 Published:2019-08-21
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61502286), the Applied Basic Research Project of Shanxi Province (201701D221099).

摘要/Abstract

摘要： 并行计算机系统功能的实现很大程度上依赖于系统互连网络的性能。为了精确度量以k元n方体为底层拓扑结构的并行计算机系统的容错能力，研究了点故障模型下k元n方体中k元（n-1）方体子网络的可靠性。当k ≥ 3且为奇数时，分别在固定划分模式和灵活划分模式下对k元n方体中不同数目的k元（n-1）方体子网络保持无故障状态的平均失效时间进行了分析，并得出了这一子网络可靠性评估参数的计算公式。结果表明，当基于k为奇数的k元n方体构建的并行计算机系统指派子网络执行用户任务时，在点故障模型下灵活划分模式相比固定划分模式有着更好的容错能力。

关键词: 并行计算机系统, 互连网络, k元n方体, 可靠性, 平均失效时间

Abstract: The functions of a parallel computer system heavily rely on the performance of interconnection network of the system. In order to measure the fault tolerance abilities of the parallel computer systems with k-ary n-cubes as underlying topologies, the reliability of the subnetworks of k-ary (n-1)-cubes in a k-ary n-cube under the node fault model was studied. For odd k ≥ 3, the mean time to failure to maintain the fault free condition of different number of k-ary (n-1)-cubes in a k-ary n-cube was analyzed under the fixed partition pattern and the flexible partition pattern, respectively. And the calculation formulas for the reliability evaluation parameter of subnetwork were obtained. Under the node fault model, the results indicate that the parallel computer system which is built based on k-ary n-cubes with odd k has better fault tolerance ability under the flexible partition pattern when subnetworks in the system are assigned for the user task execution.

Key words: parallel computer system, interconnection network, k-ary n-cube, reliability, mean time to failure

中图分类号:

TP393.02

冯凯, 李婧. k元n方体的可靠性评估[J]. 计算机应用, 2019, 39(11): 3323-3327.

FENG Kai, LI Jing. Reliability assessment of k-ary n-cube networks[J]. Journal of Computer Applications, 2019, 39(11): 3323-3327.

参考文献

[1] ABRAHAM S, PADMANABHAN K. Reliability of the hypercube[C]//Proceedings of the 1998 International Conference on Parallel Processing. Piscataway:IEEE,1988:90-94.
[2] CHANG Y, BHUYAN L N. A combinatorial analysis of subcube reliability in hypercube[J]. IEEE Transactions on Computers, 1995, 44(7):952-956.
[3] FITZGERALD K, LATIFI S, SRIMANI P K. Reliability modeling and assessment of the star-graph networks[J]. IEEE Transactions on Reliability, 2002, 51(1):49-57.
[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] WANG S, ZHANG G, FENG K. Fault tolerance in k-ary n-cube networks[J]. Theoretical Computer Science, 2012, 460:34-41.
[6] 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.
[7] 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.
[8] 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.
[9] CHEN X. Paired 2-disjoint path covers of faulty k-ary n-cubes[J]. Theoretical Computer Science, 2016, 609:494-499.
[10] 冯凯. k元n方体的条件强匹配排除[J]. 计算机应用, 2017, 37(9):2454-2456, 2490. (FENG K. Conditional strong matching preclusion for k-ary n-cubes[J]. Journal of Computer Applications, 2017, 37(9):2454-2456, 2490.)
[11] HSIEH S Y, KAO C Y. The conditional diagnosability of k-ary n-cubes under the comparison diagnosis model[J]. IEEE Transactions on Computers, 2013, 62(4):839-843.
[12] MAO W, NICOL D M. On k-ary n-cubes:theory and applications[J]. Discrete Applied Mathematics, 2003, 129(1):171-193.
[13] WANG S, FENG K, ZHANG G. Strong matching preclusion for k-ary n-cubes[J]. Discrete Applied Mathematics, 2013, 161(18):3054-3062.
[14] WANG F, ZHANG H. Matchings extend to Hamiltonian cycles in k-ary n-cubes[J]. Information Sciences, 2015, 305:1-13.
[15] 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.
[16] BONDY A, MURTY M R. Graph Theory[M]. London:Springer, 2008:1-356.

k元n方体的可靠性评估

Reliability assessment of k-ary n-cube networks

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李静, 罗金飞, 李炳超. 主动容错副本存储系统的可靠性分析模型[J]. 计算机应用, 2021, 41(4): 1113-1121.
[2]	赵季红, 吴豆豆, 曲桦, 殷振宇. 基于软件定义网络的可靠性虚拟网络映射保障机制[J]. 计算机应用, 2020, 40(3): 770-776.
[3]	高建, 毛莺池, 李志涛. 基于高斯混合时间序列模型的轨迹预测[J]. 计算机应用, 2019, 39(8): 2261-2270.
[4]	杨玉星, 李晓慧. 超立方体网络的3路结构连通度及子结构连通度[J]. 计算机应用, 2019, 39(2): 509-512.
[5]	陆秋琴, 靳超. 煤炭运输公路网络可靠性仿真分析[J]. 计算机应用, 2019, 39(1): 292-297.
[6]	李静, 刘冬实. 主动容错云存储系统的可靠性评价模型[J]. 计算机应用, 2018, 38(9): 2631-2636.
[7]	胡晶晶, 黄有方. 应对枢纽失效的轴辐式网络枢纽备份[J]. 计算机应用, 2018, 38(6): 1814-1819.
[8]	曲立平, 吴家喜. 基于评分可靠性的跨域个性化推荐方法[J]. 计算机应用, 2018, 38(11): 3081-3083.
[9]	施战, 辛煜, 孙玉娥, 黄河. 基于用户可靠性的众包系统任务分配机制[J]. 计算机应用, 2017, 37(9): 2449-2453.
[10]	冯凯. k元n方体的条件强匹配排除[J]. 计算机应用, 2017, 37(9): 2454-2456.
[11]	徐志强, 袁德砦, 陈亮. 基于稀疏随机矩阵的再生码构造方法[J]. 计算机应用, 2017, 37(7): 1948-1952.
[12]	周桥, 伊鹏, 门浩崧. 基于资源效用最大化的虚拟网络功能备份方法[J]. 计算机应用, 2017, 37(4): 948-953.
[13]	曹卫东, 朱远知, 翟盼盼, 王静. 基于灰色Elman神经网络软件可靠性预测模型[J]. 计算机应用, 2016, 36(12): 3481-3485.
[14]	张彬连, 徐洪智. 多处理器系统可靠性约束下的节能调度算法[J]. 计算机应用, 2015, 35(6): 1590-1594.
[15]	胡荣娜, 郭爱煌. 车联网中基于功率控制的传输可靠性算法[J]. 计算机应用, 2015, 35(6): 1523-1526.