具有缺弧和失效点的单定向超立方体的诊断度
The Diagnosability of Unidirectional Hypercubes with Missing Arcs and Broken-down Vertices
李丽娜 1原军1
作者信息
- 1. 太原科技大学 应用科学学院,太原 030024
- 折叠
摘要
对于大规模多处理器系统,为了保证其可靠性,需要将发生故障的处理器及时诊断出来并进行更换.诊断度是系统能够自我识别的故障处理器的最大数目.n维单定向超立方体UQn是通过对超立方体Qn所有的边进行定向得到的一个有向网络.研究了PMC模型下具有缺弧和失效点的单定向超立方体的诊断度.设S是UQn中缺弧和失效点的集合且|S|≤(「)n2」-1.通过对其缺弧和失效点的分布模式进行讨论,得到了UQn-S在PMC模型下的诊断度为UQn-S的最小入度,其中n≥3.
Abstract
For a large-scale multiprocessor system,to ensure its reliability,the faulty processors need to be diag-nosed and replaced in time.Diagnosability is the maximum number of faulty processors that the system can self-i-dentify.The n-dimensional unidirectional hypercube UQnis a directed network obtained by orienting all the edges of the hypercube Qn in a special way.This paper investigated the diagnosability of unidirectional hypercubes with missing arcs and broken-down vertices under the PMC model.Let S be a set of missing arcs and broken-down verti-ces in the unidirectional hypercube UQn with|S|≤(「)n2」-1.In this paper,by discussing the distributed patterns of the missing arcs and broken-down vertices,we show that the diagnosability of UQn-S is the minimum in-degree of UQn-S under the PMC model for n≥3.
关键词
多处理器系统/单定向超立方体/诊断度/PMC模型Key words
multiprocessor system/hypercube/diagnosability/PMC model引用本文复制引用
基金项目
国家自然科学基金(61402317)
山西省自然科学基金(201901D111253)
太原科技大学博士启动金(20202058)
太原科技大学研究生优秀创新项目(XCX212107)
出版年
2024
NETL
NSTL
万方数据