山西大学学报（自然科学版）2025，Vol.48Issue(3)：456-469,14.DOI:10.13451/j.sxu.ns.2024027
(n-m,k-m)-星图子网络的可靠性评估
Reliability Evaluation of(n-m,k-m)-star Graph Subnetworks
摘要
Abstract
The subnetwork reliability of the interconnection network of a multiprocessor system is a key indicator to assess the perfor-mance of the multiprocessor system.In order to characterize the fault tolerance of(n-m,k-m)-star graph subnetworks in an(n,k)-star graph,the probability of existing fault-free(n-m,k-m)-star graph subnetworks in an(n,k)-star graph under probabilistic fault condi-tion is analysed.For 1≤k≤n-1 and 1≤m≤k-1,the theoretical formulas of the upper and lower bounds of the probability of exist-ing(n-m,k-m)-star graph subnetworks are obtained,and an algorithm for searching fault-free(n-m,k-m)-star graph subnetworks in an(n,k)-star graph with only node failures is given.Moreover,an approximate method for evaluating the existence probability of fault-free(n-m,k-m)-star graph subnetworks is given based on Monte Carlo simulation.The experimental results show that the upper and lower bounds of the probability of existing(n-m,k-m)-star graph subnetworks are basically consistent with the approximate evalua-tion results as the node reliability gradually becomes smaller,and the relatively accurate evaluation result can be obtained by the ap-proximate method based on Monte Carlo simulation when the node reliability is relatively high or the difference between the upper and lower bounds of the probability of existing(n-m,k-m)-star graph subnetworks is significant.关键词
多处理器系统/互连网络/(n,k)-星图/概率故障/蒙特卡罗Key words
multiprocessor system/interconnection network/(n,k)-star graph/probabilistic failure/Monte Carlo分类
计算机与自动化引用本文复制引用
冯凯,杨嵛迦..(n-m,k-m)-星图子网络的可靠性评估[J].山西大学学报（自然科学版）,2025,48(3):456-469,14.基金项目
国家自然科学基金(61502286) （61502286）
山西省基础研究计划项目(20210302123438) （20210302123438）
