超立方体网络环诊断策略的研究

计算机工程与科学

• 计算机网络与信息安全 • 上一篇下一篇

超立方体网络环诊断策略的研究

陈芳，张乾

（广西大学计算机与电子信息学院，广西南宁 530004）

收稿日期:2018-07-18 修回日期:2018-11-21 出版日期:2019-07-25 发布日期:2019-07-25
基金资助:
国家自然科学基金（61363002）

A cycle diagnosis strategy for hypercube networks

CHEN Fang,ZHANG Qian

(School of Computer and Electronic Information,Guangxi University,Nanning 530004,China)

Received:2018-07-18 Revised:2018-11-21 Online:2019-07-25 Published:2019-07-25

摘要/Abstract

摘要：

多处理器系统的传统故障诊断策略和条件可诊断策略已经被广泛研究，然而并未解决系统中存在的大量故障结点问题。提出一种新的策略——环诊断策略，即通过环分割方法对汉密尔顿环进行诊断，从而找出系统中存在的所有故障结点，并给出了超立方体网络的环诊断策略及一些重要性质。与此同时，提出了超立方体网络的环快速诊断算法，快速定位系统中的所有故障结点。基于以上策略，得到了在PMC模型下，n-维超立方体网络的环诊断度为(n2+n)/2，时间复杂度为O(n)，其中n表示多处理器系统中处理器的个数。与超立方体网络的传统故障诊断策略和条件诊断策略相比较，
本文提出的环诊断策略具有诊断度大、时间复杂度小的优点。

关键词: 环诊断策略, PMC模型, n-维超立方体网络, 诊断度, 时间复杂度

Abstract:

Traditional fault diagnosis strategies and conditional diagnosis strategies for multiprocessor systems have been widely studied，however, they have not solved the problem of a large number of fault nodes in the system. Therefore, we propose a new cycle diagnosis strategy, which uses the cycle-partitioning method to diagnose Hamilton cycles and find out all the fault nodes in the system. We also give out the cycle diagnosis strategy and some important properties of hypercube networks. Meanwhile, we also propose a quick cycle diagnosis algorithm of hypercube networks to quickly locate all fault nodes in the system. Based on the above strategy and under the PMC model, the cycle diagnosis degree of an ndimensional hypercube network is (n2+n)/2 and the time complexity is

O(n), where n represents the number of processors in multiprocessor systems. Compared with traditional fault diagnosis strategies and condition diagnosis strategies for hypercube networks, the proposed cycle diagnosis strategy has the advantages of large diagnosis degree and low time complexity.

Key words: cycle diagnosis strategy, PMC model, ndimensional hypercube network, diagnosis degree, time complexity

陈芳，张乾. 超立方体网络环诊断策略的研究[J]. 计算机工程与科学.

CHEN Fang,ZHANG Qian. A cycle diagnosis strategy for hypercube networks[J]. Computer Engineering & Science.

[1]	王喜1,2，张书奎2. 交错立方体在故障情形下的诊断度和诊断算法[J]. 计算机工程与科学, 2020, 42(04): 588-595.
[2]	宣恒农1,张润驰1,何涛2,刘凌波1. PMC模型下的一个贪婪诊断算法[J]. J4, 2015, 37(08): 1430-1435.
[3]	杨文川，刘健，于淼. 基于双数组Trie树的中文分词词典算法优化研究[J]. J4, 2013, 35(9): 127-131.

超立方体网络环诊断策略的研究

A cycle diagnosis strategy for hypercube networks

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 3

编辑推荐

Metrics

本文评价