一种超立方体混合属性驱动故障诊断策略

《Discrete Applied Mathematics》:A hybrid attribute-drived fault diagnosis strategy for hypercube

【字体: 大 中 小 】 时间:2026年09月20日 来源:Discrete Applied Mathematics 1.1

编辑推荐:

   ## 摘要 系统级故障诊断是确保多处理器系统可靠连续运行的一种重要方法。在实践中,处理器故障很少以单一故障模式出现,而是以故障模式的混合或复杂情境出现。因此,研究人员投入了大量精力,通过将故障模式的限制条件混合化来增强多处理器系统的故障诊断能力。g-额外r-分量连通度(cκ

  

## 摘要

系统级故障诊断是确保多处理器系统可靠连续运行的一种重要方法。在实践中,处理器故障很少以单一故障模式出现,而是以故障模式的混合或复杂情境出现。因此,研究人员投入了大量精力,通过将故障模式的限制条件混合化来增强多处理器系统的故障诊断能力。g-额外r-分量连通度(cκrg(G))和g-额外r-分量可诊断度(ctrg(G))是多处理器系统在面对g-额外故障模式与r-分量故障模式混合情形时衡量其弹性与容错能力的关键指标。目前已对许多流行网络在g=1情况下的这些指标进行了研究。本文在PMC模型下,确定了超立方体Qn的2-额外3-分量连通度和2-额外2-分量可诊断度,即当n≥12时,cκ32(Qn)=6n?16,ct22(Qn)=6n?15。

## 引言

光刻技术的持续进步是半导体制造的基石,它直接推动了超大规模集成电路(VLSI)的发展,通过不断缩小晶体管尺寸实现了这一目标。晶体管密度的提高从根本上改变了多处理器系统架构,使得在单个芯片上集成大量处理器、复杂的缓存层次结构和高速互连成为可能。这一基础性进步反过来催生了整个行业的空前增长,尤其是在云计算、人工智能(AI)和自动驾驶领域,这些领域高度依赖于大规模的并行计算能力。然而,集成度的提高也加剧了电应力和热应力、信号完整性等关键挑战。在如此高度集成的系统中,即使单个组件发生故障,也可能导致信号完整性显著下降。因此,确保高系统可靠性、优异的弹性和强大的故障诊断能力是维持信号完整性的基本前提。

多处理器系统的可靠性和弹性可以通过其底层拓扑结构的经典连通度来评估,该拓扑结构由图来建模,其中节点代表处理器,边代表通信链路。然而,经典连通度仅考虑最简单形式的图断连,这严重低估了网络在更复杂故障模式下的可靠性与弹性,例如额外故障模式、分量故障模式以及混合故障模式。这一差距推动了针对这些特定故障模式开发更高级的连通度概念。相应地,Fàbrega和Fiol [5] 提出了图G的g-额外连通度,记为κg(G),即需要移除的最少节点数,使得移除后G断连且残差图中每个分量至少包含g+1个节点。此后,Yang等人 [25] 建立了超立方体在0≤g≤n范围内的g-额外连通度。进一步地,Hsu等人 [9] 提出了图G的r-分量连通度的概念,记为cκr(G),即需要移除的最少节点数,使得移除后G断连且结果图至少包含r个分量,并刻画了超立方体Qn在1≤r≤n范围内的r-分量连通度。此后,Zhao等人 [30] 确定了超立方体Qn在n+1≤r≤2n?5范围内的r-分量连通度。随后,Li等人 [14] 提出了图G的g-额外r-分量连通度,记为cκrg(G),即需要移除的最少节点数,使得移除后G断连且结果图至少包含r个分量,每个分量至少包含g+1个节点。迄今为止,关于一些网络(如超立方体 [14]、k-元n-立方体(k≥3)[10]、[11]、冒泡排序网络 [15]、半超立方体 [6]、增强折叠超立方体类网络 [8] 和星图 [17])的g-额外r-分量连通度研究,主要集中在g=1且3≤r≤4的情形。此外,在边故障设置下,超立方体和超立方体类网络的分量边连通度已被刻画 [7]、[16],而其额外边连通度也已被研究 [3]、[20]、[27]、[28]。

强大的故障诊断能力是维持多处理器系统连续不间断运行的关键因素。在系统级故障诊断理论领域,Preparata等人 [18] 提出的PMC测试模型是最广泛采用的模型,该模型允许相邻处理器之间进行双向测试。为了量化多处理器系统在该诊断模型下的容错能力,图G的可诊断度,记为t(G),被定义为使得所有故障处理器都能被准确检测和隔离的最大故障处理器数目。然而,可诊断度存在一个缺陷,即它依赖于一个不太可能成立的要求——某个指定处理器的所有相邻处理器可能同时故障。为了克服这一缺陷,Lai等人 [13] 提出了条件可诊断度,其假设故障集不包含某个处理器的所有邻居。相应地,Zhang等人 [29] 发展了g-额外条件可诊断度,强调生存网络的每个分量至少包含g+1个节点。此外,Zhang等人 [26] 提出了r-分量可诊断度,强调生存网络至少包含r个分量。然而,在实践中,处理器故障很少以单一模式出现,而是以故障模式或情境的组合出现。为了更好地表征多处理器系统在混合故障模式下的容错能力,Liao等人 [15] 提出了g-额外r-分量可诊断度,该指标强调生存网络至少包含r个分量,每个分量至少包含g+1个节点,并确定了冒泡排序网络在PMC模型下g=1且2≤r≤3时的g-额外r-分量可诊断度。

超立方体是并行和分布式系统设计中一种流行的拓扑结构,具有许多优良特性,如并行随机存取机(PRAM)[12]、Intel iPSC/860 [4] 和连接机CM-2 [2] 等。尽管超立方体在单一故障模式下的连通度和可诊断度已被广泛研究,但在g-额外r-分量故障模式下的研究仍然未知,现有工作主要局限于g=1的情形。本文研究了超立方体在g-额外r-分量故障模式下的连通度和可诊断度。主要贡献总结如下:

(1) 首先,我们建立了超立方体Qn(n≥12)的2-额外3-分量连通度,即cκ32(Qn)=6n?16。

(2) 其次,我们确定了超立方体Qn(n≥12)在PMC模型下的2-额外2-分量可诊断度,即ct22(Qn)=6n?15。

本文其余部分组织如下。第2节回顾了超立方体的一些术语、符号和有用性质。第3节分别确定了超立方体的2-额外3-分量连通度和2-额外2-分量可诊断度。第4节总结了本文并对未来工作进行了展望。

## 第2节 术语与符号

互连网络可以建模为一个简单的无向图G=(V(G),E(G))。对于任意节点u∈V(G),u在G中的邻域记为NG(u),是u在G中所有邻居的集合;u在G中的闭邻域记为NG[u],定义为NG(u)∪{u}。对于任意节点子集F?V(G),定义NG(F)=(?u∈F NG(u))?F,NG[F]=(?u∈F NG(u))∪F。我们还用G[F]表示F诱导的子图,用G?F表示V(G)?F诱导的子图。对于两个节点子集F1,F2?V(G),|NG(F1)∩NG(F2)|……

## 第3节 主要结果

### 结论

本文研究了多处理器系统在g-额外r-分量故障模式下的连通度和可诊断度。利用超立方体的固有结构性质,我们建立了超立方体Qn(n≥12)的2-额外3-分量连通度和2-额外2-分量可诊断度,即在PMC模型下,cκ32(Qn)=6n?16,ct22(Qn)=6n?15。

本文建立了超立方体2-额外r-分量连通度的一般上界。由定理2.4(3)可知,这是……

## 致谢

本工作部分得到国家自然科学基金(编号61572010和61977016)、福建省自然科学基金(编号2025J01675和2024J01071)、福建省数学联合基金(编号2023SXLMMS04)以及中国国家留学基金委(CSC编号202108350054)的资助。

吴展奎 | 周树明 | 程易 | 郑伟星
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号