(n-m,k-m)-星图子网络的可靠性评估

摘要

多处理器系统互连网络的子网络可靠性是衡量系统性能的一个关键指标。为了刻画（n,k）-星图中（n-m,k-m）-星图子网络的容错性能，在概率故障条件下分析了（n,k）-星图中存在无故障（n-m,k-m）-星图子网络的概率。对于1≤k≤n-1和1≤m≤k-1，得出了（n-m,k-m）-星图子网络存在概率的上下界的理论公式，给出了仅考虑点故障的（n,k）-星图的无故障（n-m,k-m）-星图子网络的搜寻算法，并基于蒙特卡罗模拟提出了评估无故障（n-m,k-m）-星图子网络的存在概率的近似方法。实验结果表明，随着顶点可靠性逐渐变小，得出的（n-m,k-m）-星图子网络存在概率的上下界与近似评估结果基本吻合；当顶点可靠性较高或（n-m,k-m）-星图子网络存在概率的上下界相差较大时，利用基于蒙特卡罗的近似方法可以得出较为精确的评估结果。

关键词

多处理器系统 / 互连网络 / (n,k)-星图 / 概率故障 / 蒙特卡罗

Key words

multiprocessor system / interconnection network / (n,k)-star graph / probabilistic failure / Monte Carlo

基金资助

国家自然科学基金(61502286)

山西省基础研究计划项目(20210302123438)