计算机科学

计算机科学 ›› 2025, Vol. 52 ›› Issue (6A): 240700180-9.doi: 10.11896/jsjkx.240700180

• 计算机软件&体系架构 • 上一篇    下一篇

(n,k)-排列图的t/s诊断度与t/s 诊断算法研究

张世豪1, 冷明2   

  1. 1 江西理工大学软件工作学院 南昌 330013
    2 井冈山大学计算机科学系 江西 吉安 343009
  • 出版日期:2025-06-16 发布日期:2025-06-12
  • 通讯作者: 冷明(13367069363@163.com)
  • 作者简介:(1603993183@qq.com)
  • 基金资助:
    江西省自然科学基金(20202BABL202042);国家自然科学基金(62262032,61862035,61562046);江西省教育厅科技计划项目(GJJ2201604,GJJ201033,GJJ211037)

Study on t/s Diagnosability and t/s Diagnostic Algorithm of (n,k)-Arrangement Graphs

ZHANG Shihao1, LENG Ming2   

  1. 1 University School of Software Work,Jiangxi University of Science and Technology,Nanchang 330013,China
    2 Department of Computer Science,Jinggangshan University,Ji'an,Jiangxi 343009,China
  • Online:2025-06-16 Published:2025-06-12
  • About author:ZHANG Shihao,born in 2001,postgra-duate.His main research interests include fault diagnosis of network systems and so on.
    LENG Ming,born in 1975,Ph.D,professor,postgraduate supervisor.His main research interests include fault diagnosis,algorithm analysis and design,combination analysis and optimization, and so on.
  • Supported by:
    Jiangxi Provincial Natural Science Foundation(20202BABL202042),National Natural Science Foundation of China(62262032,61862035,61562046) and Science and Technology Plan Projects of the Education Department of Jiangxi Province(GJJ2201604,GJJ201033,GJJ211037).

PDF (PC)

33

摘要： 鉴于多处理器系统中日益严峻的故障风险挑战,特别是在超级计算机领域,如何有效提升系统的可靠性和容错能力成为了亟待解决的关键问题。(n,k)-排列图作为一种新型的互连网络拓扑结构应运而生,它是基于星图网络的推广和变形。它在保留星图网络原有的对称性和容错性的同时,具有更好的灵活性。目前对于(n,k)-排列图的可靠性研究尚不全面。基于此,展开了对(n,k)-排列图的t/s和t/s诊断算法研究。首先,给出了(n,k)-排列图的系列拓扑性质;然后,度量了(n,k)-排列图在PMC(Preparata,Metze,Chien)模型下的t/s诊断度;最后,设计了一个时间复杂度为O(N log2N)的快速诊断算法,用于识别(n,k)-排列图的所有故障结点。(n,k)-排列图的t/s诊断度被确定,进一步完善了(n,k)-排列图网络的可靠性指标,为其在应用和推广中的可靠性提供了重要的依据。

关键词: 可靠性, t/s诊断度, t/s诊断算法, (n,k)-排列图, PMC模型

Abstract: Given the increasingly severefault risks in multiprocessor systems,particularly in the field of supercomputers,enhancing system reliability and fault tolerance has emerged as a critical issue that requires urgent attention.In response to this need,the(n,k)-arrangement graph,as a novel interconnect network topology,has arisen.It is a generalization and variation of the star graph network,inheriting its inherent symmetry and fault tolerance while offering greater flexibility.However,the current research on the reliability of the(n,k)-arrangement graph is still incomplete.Based on this,exploring the t/s diagnosability and t/s diagnosis algorithm of the(n,k)-arrangement graph.Initially,we present a series of relevant topological properties.Subsequently,we prove the t/s diagnosability of the(n,k)-arrangement graph under the PMC model.Finally,we design a fast diagnosis algorithm with a time complexity of O(N log2N) to identify faulty nodes within the(n,k)-arrangement graph.The diagnosability of (n,k)-arrangement graphshavebeen identified,further refining the reliability metrics of (n,k)-arrangement graph networks,thereby offering crucial reliability performance criteria for their application and promotion.

Key words: Reliability, t/s diagnosability, t/s diagnostic algorithm, (n,k)-arrangement graph, PMC model

中图分类号: 

  • TP393
[1]FRIEDMAN A D,SIMONCINI L.System-level fault diagnosis[J].Computer,1980,13(3):47-53.
[2]SEERA M,LIM C P,ISHAK D,et al.Fault detection and diagnosis of induction motors using motor current signature analysis and a hybrid FMM-CART model[J].IEEE Trans on Neural Networks and Learning Systems,2011,23(1):97-108.
[3]FAN J,JIA X.Edge-pan cyclicity and path-embeddability of bijective connection graphs[J].Information Sciences,2008,178(2):340-351.
[4]FAN J,JIA X,LIU X,et al.Efficient unicast in bijective connection networks with the restricted faulty node set[J].Information Sciences,2011,181(11):2303-2315.
[5]PRETARATA F P,METZE G,CHIEN R T.On the connection assignment problem of diagnosis systems[J].IEEE Transactions on Computers,1967,16(12):848-854.
[6]MALEK M.A comparison connection assignment for diagnosisof multiprocessor systems [C]//Proc of the 7th annual symposium on Computer Architecture.New York:Association for Computing Machinery,1980:31-36.
[7]SENGUPTA A,DAHBURA A T.On self-diagnosable multi-processor systems:diagnosis by the comparisonapproach[J].IEEE Transactions on Computers,1992,41(11):1386-1396.
[8]PENG S L,LIN C K,TAN J J,et al.The g-good-neighbor conditional diagnosability of hypercube under PMC model.AppliedMathematics and Computation[J],2012,218(21):10406-10412.
[9]SY C N H.Conditional diagnosability of augmented cubes under the PMC model[J].IEEE Trans Dependable Secure Compute,2012,9(1):46.
[10]LAI P L,TAN J J,CHANG C P,et al.Conditional diagnosability measures for large multiprocessor systems[J].IEEE Transactions on Computers,2005,54(2):165-175.
[11]JUN Y,AIXIA L,XUE M,et al.The g good-neighbor conditional diagnosability of k-ary n-cubes under the PMC model and MM* model[J].IEEE Trans.Parallel Diatribe.Syst.,2015,26:1165-1177.
[12]SENGUPTA A,DAHBURA A T.On self-diagnosable multi-processor systems:diagnosis by the comparison approach[J].IEEETrans on Computers,1992,41(11):1386-1396.
[13]YANG X,TANG Y Y.Efficient fault identification of diagnosable systems under the comparison model[J].IEEE Transactions on computers,2007,56(12):1612-1618.
[14]HSIEH S Y,CHEN Y S.Strongly diagnosable product networks under the comparison diagnosis model[J].IEEE Transactions on Computers,2008,57(6):721-732.
[15]LAI P L.A systematic algorithm for identifying faults on hypercube-like networks under the comparison model[J].IEEE Transactions on Reliability,2012,61(2):452-459.
[16]ZHENG J,LATIFI S,REGENTOVA E,et al.Diagnosability of star graphs under the comparison diagnosis model[J].Information Processing Letters,2005,93(1):29-36.
[17]FRIEDMA N,ARTHUR D.A new measure of digital systemdiagnosis [C]//Proceedings Int.Symp.Fault-Tolerant Computing.1975:167-170.
[18]LIANG J,ZHANG Q,LI H.Structural properties and t/s-diagnosis for star networks based on the PMC model[J].IEEE Access,2017,5:26175-26183.
[19]LIANG J,ZHANG Q.The t/s-diagnosability of hypercube networks under the PMC and comparison models[J].IEEE Access,2017,5:5340-5346.
[20]LIN Y,LIN L,HUANG Y,et al.The t/s-diagnosability and t/s-diagnosis algorithm of folded hypercube under the PMC/MM* model[J].Theoretical Computer Science,2021,887:85-98.
[21]XIE Y,LIANG J,YIN W,et al.The properties and t/s-diagnosability of k-ary n-cube networks[J].The Journal of Supercomputing,2022,78(5):7038-7057.
[22]AKERS S B, KRISHNAMURTHY B.A group-theoretic model for symmetric interconnection networks[J].IEEE trans on Computers,1989,38(4):555-566.
[23]DAY K, TRIPATHI A.Arrangement graphs:a class of genera-lized star graphs[J].Information Processing Letters,1992,42(5):235-241.
[24]ZHOU S,XU J M.Fault diagnosability of arrangement graphs[J].Information Sciences,2013,246:177-190.
[25]LIN L, ZHOU S.Conditional connectivity for(n,k)-arrange-ment graphs [J].Math.Study,2012,45(4):350-364.
[26]GUO C,XIAO Z F,LENG M,et al.(t,k)-diagnosability of exchanged crossed cube under the PMC model[J].Journal on Communications,2019,40(6):190-202.
[27]LIANG J R,CHEN M J.Research on (t,k)-diagnosability for ugmented cube network under the comparison model[J].Journal on Communications,2017,38(8):9-18.
[28]YIN W,LIANG J,XIE Y,et al.The t/k-diagnosability of m-ary n-cube networks[J].Theoretical Computer Science,2024,986:114345.
[29]SUN X,FAN J,CHENG B,et al.The t/m-diagnosis strategy of augmented k-ary n-cubes[J].Theoretical Computer Science,2023,945:113671.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发