3元n立方体网络的t/k可诊断度研究  

Research on t/k-diagnosability of 3-ary n-cube networks

作　　者：殷文 梁家荣[1] Yin Wen;Liang Jiarong(School of Computer&Electronic Information,Guangxi University,Nanning 530004,China)

机构地区：[1]广西大学计算机与电子信息学院,南宁530004

出　　处：《计算机应用研究》2021年第6期1790-1793,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(61862003,61761006);广西自然科学基金资助项目(2018GXNSFDA281052)。

摘　　要：可诊断度是评估多处理器系统可靠性的一个关键指标。t/k诊断策略通过允许至多k个无故障处理器被误诊为故障处理器,从而极大提高了系统的可诊断度。与t可诊断度和t_(1)/t_(1)可诊断度相比,t/k可诊断度可以更好地反映实际系统的故障模式。3元n立方是一种性质优良并且应用广泛的网络拓扑,在许多分布式多处理器的构建中被用做底层网络。根据一些引理以及确定系统为t/k可诊断的充分条件,研究得出当n≥3及0≤k≤n,3元n立方是t_(k,n)/k-可诊断的,其中t_(k,n)=2(k+1)n-(k+1)(k+2)。这个结果显示,在选择恰当的k值时,3元n立方的t/k可诊断度t_(k,n)远大于其t可诊断度2n和t_(1)/t_(1)可诊断度4n-3。Diagnosability is a key indicator for evaluating the reliability of multiprocessor systems.The t/k diagnosis strategy greatly improves the diagnosability of the system by allowing at most k fault-free processors to be misdiagnosed as faulty processors.Compared with t-diagnosability and t_(1)/t_(1)-diagnosability,t/k-diagnosability can better reflect the fault modes of a practical system.The 3-ary n-cube is a significant and common network topology,which is used as the underlying network in the construction of many distributed memory multiprocessors.According to some lemmas and the sufficient condition,this paper determined that a system was t/k-diagnosable,when n≥3 and 0≤k≤n,the 3-ary n-cube was t_(k,n)/k-diagnosable,where t_(k,n)=2(k+1)n-(k+1)(k+2).This result shows that when choosing an appropriate value of k,the t/k-diagnosability t_(k,n) of 3-ary n-cube is much greater than its t-diagnosability 2 n and t_(1)/t_(1)-diagnosability 4 n-3.

关 键 词：可诊断度 多处理器系统 t/k可诊断度 3元n立方 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]