近日，我院理论计算机科学团队在互连网络的子网络容错性研究方面取得重要成果，研究成果以“Evaluating robustness of subnetworks for the split-star network”为题发表于计算机系统结构领域国际顶级期刊IEEE Transactions on Computers (简称TC)。该论文的第一作者和通讯作者为冯凯副教授，合作者为2023级硕士生谢国栋、姬张建副教授和美国蒙特克莱尔州立大学王大进教授。

大规模多处理器系统是助推科技进步和经济社会发展的重要工具，其计算任务的调度和执行依赖于系统互连网络的性能。系统互连网络的子网络容错性用于表征有故障发生时互连网络中特定规模子网络的保持能力，是度量互连网络性能的关键指标之一。针对子网络容错性研究中计算复杂度高、准确评估较难实现等问题，研究团队以极具应用前景的分裂星图网络为研究对象，将图论结构分析方法和组合分析方法交叉融合，围绕无故障子网络存在概率估计和子网络排除问题研究给出了子网络容错性的准确评估方法。

研究团队通过构建不同规模分裂星图子网络的符号化表示，厘清了同构意义下不同规模子网络的具体分布。基于此，首先利用结构性质通过构造性证明给出了使得n维分裂星图网络中不存在(n-m)维分裂星图子网络所需破坏的最小点数的上下界（见图1）。其次，借助组合分析方法给出了点可靠性为p时无故障(n-m)维分裂星图子网络存在概率的上下界和近似计算公式，并提出了一种仿真评估方法；实验结果表明，利用所得理论结果和所提仿真方法可以准确地得出无故障子网络存在概率（见图2）。

图1 子网络排除度量参数的上下界

图2 无故障子网络存在概率的评估结果

特别地，还构建了所研究的两个子网络容错性度量之间的相互关系，并以实例说明了利用所构建的相互关系可以有效提升子网络容错性的评估精度。

该研究工作得到计算智能与中文信息处理教育部重点实验室、国家自然科学基金项目（61502286）、山西省基础研究计划项目（20210302123438,202303021211002）等支持。

TC期刊于1952年创刊，是中国计算机学会（CCF）推荐的A类国际学术期刊，近五年年均录用论文仅200余篇，主要刊登计算机体系结构、并行与分布计算以及存储系统等领域的高质量前沿研究成果。

论文链接：https://ieeexplore.ieee.org/document/11059853/