具有缺弧和失效点的单定向超立方体的诊断度  

The Diagnosability of Unidirectional Hypercubes with Missing Arcs and Broken-down Vertices

作　　者：李丽娜 原军[1] LI Li-na;YUAN Jun(School of Applied Sciences,Taiyuan University of Science and Technology,Taiyuan 030024,China)

机构地区：[1]太原科技大学应用科学学院,太原030024

出　　处：《太原科技大学学报》2024年第3期323-328,共6页Journal of Taiyuan University of Science and Technology

基　　金：国家自然科学基金(61402317);山西省自然科学基金(201901D111253);太原科技大学博士启动金(20202058);太原科技大学研究生优秀创新项目(XCX212107)。

摘　　要：对于大规模多处理器系统,为了保证其可靠性,需要将发生故障的处理器及时诊断出来并进行更换。诊断度是系统能够自我识别的故障处理器的最大数目。n维单定向超立方体UQ_(n)是通过对超立方体Q_(n)所有的边进行定向得到的一个有向网络。研究了PMC模型下具有缺弧和失效点的单定向超立方体的诊断度。设S是UQ_(n)中缺弧和失效点的集合且S≤n/2」-1.通过对其缺弧和失效点的分布模式进行讨论,得到了UQ_(n)-S在PMC模型下的诊断度为UQ_(n)-S的最小入度,其中n≥3.For a large-scale multiprocessor system,to ensure its reliability,the faulty processors need to be diagnosed and replaced in time.Diagnosability is the maximum number of faulty processors that the system can self-identify.The n-dimensional unidirectional hypercube UQ_(n)is a directed network obtained by orienting all the edges of the hypercube Q_(n)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 vertices in the unidirectional hypercube UQ n with S≤n 2」-1.In this paper,by discussing the distributed patterns of the missing arcs and broken-down vertices,we show that the diagnosability of UQ_(n)-S is the minimum in-degree of UQ_(n)-S under the PMC model for n≥3.

关 键 词：多处理器系统 单定向超立方体 诊断度 PMC模型 

分 类 号：O157.5[理学—数学]