Home Journal of Computer Science and Technology Article
Article Link
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Show Outline
Outline
Abstract
Keywords
Electronic Supplementary Material
References
Show full outline
Hide outline
Regular Paper

Probabilistic Fault Diagnosis of Clustered Faults for Multiprocessor Systems

School of Computer Science and Technology, Soochow University, Suzhou 215006, China
Provincial Key Laboratory for Computer Information Processing Technology, Soochow University, Suzhou 215006, China
Show Author Information

Abstract

With the development of high-performance computing and the expansion of large-scale multiprocessor systems, it is significant to study the reliability of systems. Probabilistic fault diagnosis is of practical value to the reliability analysis of multiprocessor systems. In this paper, we design a linear time diagnosis algorithm with the multiprocessor system whose threshold is set to 3, where the probability that any node is correctly diagnosed in the discrete state can be calculated. Furthermore, we give the probabilities that all nodes of a d-regular and d-connected graph can be correctly diagnosed in the continuous state under the Weibull fault distribution and the Chi-square fault distribution. We prove that they approach to 1, which implies that our diagnosis algorithm can correctly diagnose almost all nodes of the graph.

Keywords

regular graphclustered faultprobabilistic diagnosis algorithmPreparata Metze Chien model (PMC model)

Electronic Supplementary Material

Download File(s)
JCST-2010-11099-Highlights.pdf (731.1 KB)

References

[1]

Somani A K, Agarwal V K, Avis D. A generalized theory for system level diagnosis. IEEE Trans. Computers, 1987, C-36(5): 538–546. DOI: 10.1109/TC.1987.1676938.

Crossref Google Scholar
[2]

Preparata F P, Metze G, Chien R T. On the connection assignment problem of diagnosable systems. IEEE Trans. Electronic Computers, 1967, EC-16(6): 848–854. DOI: 10.1109/PGEC.1967.264748.

Crossref Google Scholar
[3]

Chang N W, Hsieh S Y. Structural properties and conditional diagnosability of star graphs by using the PMC model. IEEE Trans. Parallel and Distributed Systems, 2014, 25(11): 3002–3011. DOI: 10.1109/TPDS.2013.290.

Crossref Google Scholar
[4]

Li X Y, Fan J X, Lin C K, Cheng B L, Jia X H. The extra connectivity, extra conditional diagnosability and t/k-diagnosability of the data center network DCell. Theoretical Computer Science, 2019, 766: 16–29. DOI: 10.1016/j.tcs.2018.09.014.

Crossref
[5]

Li X Y, Fan J X, Lin C K, Jia X H. Diagnosability evaluation of the data center network DCell. The Computer Journal, 2018, 61(1): 129–143. DOI: 10.1093/comjnl/bxx 057.

Crossref Google Scholar
[6]

Lin L M, Huang Y Z, Wang X D, Xu L. Restricted connectivity and good-neighbor diagnosability of split-star networks. Theoretical Computer Science, 2020, 824-825: 81–91. DOI: 10.1016/j.tcs.2020.04.015.

Crossref Google Scholar
[7]

Lv M J, Fan J X, Zhou J Y, Cheng B L, Jia X H. The extra connectivity and extra diagnosability of regular interconnection networks. Theoretical Computer Science, 2020, 809: 88–102. DOI: 10.1016/j.tcs.2019.12.001.

Crossref Google Scholar
[8]

Wang S Y, Wang Z H, Wang M J S, Han W P. g-Good-neighbor conditional diagnosability of star graph networks under PMC model and MM* model. Frontiers of Mathematics in China, 2017, 12(5): 1221–1234. DOI: 10.1007/s11464-017-0657-9.

Crossref
[9]

Zhu Q, Zhang J, Li L L. The h-extra connectivity and h-extra conditional diagnosability of bubble-sort star graphs. Discrete Applied Mathematics, 2018, 251: 322–333. DOI: 10.1016/j.dam.2018.03.077.

Crossref
[10]

Xu X, Zhou S M, Xu L. Diagnosabilities of regular networks under three-valued comparison models. International Journal of High Performance Computing and Networking, 2017, 10(4/5): 251–258. DOI: 10.1504/IJHPCN.2017.086529.

Crossref Google Scholar
[11]

Liang J R, Feng H, Du X J. Intermittent fault diagnosability of interconnection networks. Journal of Computer Science and Technology, 2017, 32(6): 1279–1287. DOI: 10.1007/s11390-017-1800-5.

Crossref Google Scholar
[12]

Sun X L, Zhou S M, Lv M J, Liu J F, Lian G Q. Intermittent fault diagnosability of some general regular networks. The Computer Journal, 2020, 63(1): 16–24. DOI: 10.1093/comjnl/bxy128.

Crossref Google Scholar
[13]

Blough D M, Sullivan G F, Masson G M. Efficient diagnosis of multiprocessor systems under probabilistic models. IEEE Trans. Computers, 1992, 41(9): 1126–1136. DOI: 10.1109/12.165394.

Crossref Google Scholar
[14]
Fussell D, Rangarajan S. Probabilistic diagnosis of multiprocessor systems with arbitrary connectivity. In Proc. the 19th International Symposium on Fault-Tolerant Computing. Digest of Papers, Jun. 1989, pp.560–565. DOI: 10.1109/FTCS.1989.105636.
Crossref
[15]

Tang Q Y, Song X Y. Diagnosis of parallel computers arbitrary connectivity. IEEE Trans. Computers, 1999, 48(7): 757–761. DOI: 10.1109/12.780885.

Crossref Google Scholar
[16]

Rangarajan S, Fussell D. Diagnosing arbitrarily connected parallel computers with high probability. IEEE Trans. Computers, 1992, 41(5): 606–615. DOI: 10.1109/12.142687.

Crossref Google Scholar
[17]

Huang K Y, Agarwal V K, Thulasiraman K. Diagnosis of clustered faults and wafer testing. IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 1998, 17(2): 136–148. DOI: 10.1109/43.681263.

Crossref Google Scholar
[18]

Tang Q Y, Song X Y, Wang Y K. Diagnosis of clustered faults for identical degree topologies. IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 1999, 18(8): 1192–1201. DOI: 10.1109/43.775637.

Crossref Google Scholar
[19]

Lu X J, Li J P, Seo C J. Probabilistic diagnosis of clustered faults for shared structures. Mathematical and Computer Modelling, 2009, 49(3/4): 623–634. DOI: 10.1016/j.mcm.2008.06.011.

Crossref Google Scholar
[20]

Lv M J, Zhou S M, Sun X L, Lian G Q, Liu J F, Wang D J. Probabilistic diagnosis of clustered faults for hypercube-based multiprocessor system. Theoretical Computer Science, 2019, 793: 113–131. DOI: 10.1016/j.tcs.2019.06.023.

Crossref Google Scholar
[21]

Akers S B, Krishnamurthy B. A group-theoretic model for symmetric interconnection networks. IEEE Trans. Computers, 1989, 38(4): 555–566. DOI: 10.1109/12.21148.

Crossref Google Scholar
[22]

Compeau P E C. Girth of pancake graphs. Discrete Applied Mathematics, 2011, 159(15): 1641–1645. DOI: 10.1016/j.dam.2011.06.013.

Crossref Google Scholar
[23]

Song S L, Zhou S M, Li X Y. Conditional diagnosability of burnt pancake networks under the PMC model. The Computer Journal, 2016, 59(1): 91–105. DOI: 10.1093/ comjnl/bxv066.

Crossref Google Scholar
Journal of Computer Science and Technology
Volume 38 Issue 4,
July 2023
Pages 821-833
DOI: 10.1007/s11390-021-1099-0
Cite this article:
Sun X-L, Fan J-X, Cheng B-L, et al. Probabilistic Fault Diagnosis of Clustered Faults for Multiprocessor Systems. Journal of Computer Science and Technology, 2023, 38(4): 821-833. https://doi.org/10.1007/s11390-021-1099-0
Metrics & Citations  
Article History
Copyright
Return