research-article

Diagnosability of Component-Composition Graphs in the MM* Model

Authors:

Sun-Yuan HsiehAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 19, Issue 3

Article No.: 27, Pages 1 - 14

https://doi.org/10.1145/2611759

Published: 23 June 2014 Publication History

Abstract

Diagnosability is an important metric for measuring the reliability of multiprocessor systems. This article adopts the MM* model and outlines the common properties of a wide class of interconnection networks, called component-composition graphs (CCGs), to determine their diagnosability by using their obtained properties. By applying the results to multiprocessor systems, the diagnosability of hypercube-like networks (including hypercubes, crossed cubes, Möbius cubes, twisted cubes, locally twisted cubes, generalized twisted cubes, and recursive circulants), star graphs, pancake graphs, bubble-sort graphs, and burnt pancake graphs, all of which belong to the class of CCGs, can also be computed.

References

[1]

S. B. Akers, D. Horel, and B. Krishnamurthy. 1987. The star graph: An attractive alternative to the n-cube. In Proceedings of the International Conference on Parallel Processing. 393--400.

[2]

S. B. Akers and B. Krishnamurthy. 1989. A group-theoretic model for symmetric interconnection networks. IEEE Trans. Comput. 38, 4, 555--566.

Digital Library

[3]

L. C. P. Albini, S. Chessa, and P. Maestrini. 2004. Diagnosis of symmetric graphs under the BGM model. Comput. J. 47, 1, 85--92.

[4]

T. Araki and Y. Shibata. 2003. (t, k)-diagnosable system: A generalization of the PMC models. IEEE Trans. Comput. 52, 7, 971--975.

Digital Library

[5]

J. R. Armstrong and F. G. Gray. 1981. Fault diagnosis in a boolean n cube array of multiprocessors. IEEE Trans. Comput. 30, 8, 587--590.

Digital Library

[6]

F. Barsi, F. Grandoni, and P. Maestrini. 1976. A theory of diagnosability of digital systems. IEEE Trans. Comput. C-25, 6, 585--593.

Digital Library

[7]

L. Bhuyan and D. P. Agrawal. 1984. Generalized hypercubes and hyperbus structure for a computer network. IEEE Trans. Comput. 33, 4, 323--333.

Digital Library

[8]

G. Y. Chang, G. J. Chang, and G. H. Chen. 2005. Diagnosabilities of regular networks. IEEE Trans. Parallel Distrib. Syst. 16, 4, 314--323.

Digital Library

[9]

G. Y. Chang, G. H. Chen, and G. J. Chang. 2006. (t, k)-diagnosis for matching composition networks. IEEE Trans. Comput. 55, 1, 88--92.

Digital Library

[10]

G. Y. Chang, G. H. Chen, and G. J. Chang. 2007. (t, k)-diagnosis for matching composition networks under the MM&ast; model. IEEE Trans. Comput. 56, 1, 73--79.

Digital Library

[11]

F. B. Chedid. 1995. On the generalized twisted cube. Inf. Process. Lett. 55, 1, 49--52.

Digital Library

[12]

C. A. Chen and S. Y. Hsieh. 2011. (t, k)-diagnosis for component-composition graphs under the MM&ast; model. IEEE Trans. Comput. 60, 12, 1704--1717.

Digital Library

[13]

K. Y. Chwa And L. Hakimi. 1981. On fault identification in diagnosable systems. IEEE Trans. Comput. 30, 6, 414--422.

Digital Library

[14]

P. Cull and S. M. Larson. 1995. The Mobius cubes. IEEE Trans. Comput. 44, 5, 647--659.

Digital Library

[15]

A. Das, K. Thulasiraman, and V. K. Agarwal. 1994. Diagnosis of t/(t + 1)-diagnosable systems. SIAM J. Comput. 23, 5, 895--905.

Digital Library

[16]

K. Efe. 1992. The crossed cube architechure for parallel computation. IEEE Trans. Parallel Distrib. Syst. 3, 5, 513--524.

Digital Library

[17]

J. Fan. 2002. Diagnosability of crossed cubes under the comparison diagnosis model. IEEE Trans. Parallel Distrib. Syst. 13, 7, 687--692.

Digital Library

[18]

P. A. J. Hilbers, M. R. J. Koopman, and J. L. J. Van De Snepscheut. 1987. The twisted cube. In Proceedings of the Conference on Parallel Architectures and Languages Europe: Parallel Architectures, Vol. 1. Lecture Notes in Computer Science, vol. 258, Springer, 152--159.

Digital Library

[19]

S. Y. Hsieh and C. A. Chen. 2010. Computing the (t, k)-diagnosability of component-composition graphs and its application. In Proceedings of 21^st International Symposium on Algorithms and Computation (ISAAC'10). 363--374.

[20]

S. Y. Hsieh and Y. S. Chen. 2008a. Strongly diagnosable product networks under the comparison diagnosis model. IEEE Trans. Comput. 57, 6, 721--732.

Digital Library

[21]

S. Y. Hsieh and Y. S. Chen. 2008b. Strongly diagnosable systems under the comparison diagnosis model. IEEE Trans. Comput. 57, 12, 1720--1725.

Digital Library

[22]

S. Y. Hsieh and T. Y. Chuang. 2009. The strong diagnosability of regular networks and product networks under the PMC model. IEEE Trans. Parallel Distrib. Syst. 20, 3, 367--378.

Digital Library

[23]

K. Kaneko and N. Sawada. 2003. An algorithm for node-to-set disjoint paths problem in burnt pancake graphs. IEICE Trans. Inf. Syst. E86-D, 12, 2588--2594.

[24]

P. L. Lai, J. J. M. Tan, C. H. Tsai, and L. H. Hsu. 2004. Diagnosability of the matching composition network under the comparison diagnosis model. IEEE Trans. Comput. 53, 8, 1064--1069.

Digital Library

[25]

C. W. Lee and S. Y. Hsieh. 2011a. Determining the diagnosability of (1,2)-matching composition networks and its applications. IEEE Trans. Depend. Secur. Comput. 8, 3, 353--362.

Digital Library

[26]

C. W. Lee and S. Y. Hsieh. 2011b. Diagnosability of two-matching composition networks under the MM&ast; model. IEEE Trans. Depend. Secur. Comput. 8, 2, 246--255.

Digital Library

[27]

C. W. Lee and S. Y. Hsieh. 2013. Diagnosabiltiy of multiprocessor systems. InScalable Computing and Communications: Theory and Practice. Wiley.

[28]

J. K. Lee and J. T. Butler. 1990. A characterization of t/s-diagnosability and sequential t-diagnosability in designs. IEEE Trans. Comput. 39, 10, 1298--1304.

Digital Library

[29]

F. T. Leighton. 1992. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann, San Fransisco.

Digital Library

[30]

J. Maeng and M. Malek. 1981. A comparison connection assignment for self-diagnosis of multiprocessor systems. In Proceedings of 11^th International Symposium on Fault-Tolerant Computing. 173--175.

[31]

J. H. Park and K. Y. Chwa. 2000. Recursive circulants and their embeddings among hypercubes. Theor. Comput. Sci. 244, 35--62.

Digital Library

[32]

J. H. Park, H. S. Lim, and H. C. Kim. 2007. Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements. Theor. Comput. Sci. 377, 170--180.

Digital Library

[33]

F. P. Preparata, G. Metze, and R. T. Chien. 1967. On the connection assignment problem of diagnosable systems. IEEE Trans. Electron. Comput. EC-16, 448--454.

[34]

A. Sengupta and A. Dahbura. 1992. On self-diagnosable multiprocessor system: Diagnosis by the comparison approach. IEEE Trans. Comput. 41, 11, 1386--1396.

Digital Library

[35]

A. S. Vaidya, P. S. N. Rao, and S. R. Shankar. 1993. A class of hypercube-like networks. In Proceedings of the 5^th Symposium on Parallel and Distributed Processing. 800--803.

Digital Library

[36]

D. Wang. 1999. Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model. IEEE Trans. Comput. 48, 12, 1369--1374.

Digital Library

[37]

M. Xu and J. Jing. 2012. The connectivity and super connectivity of bubble-sort graph. Acta Mathematicae Sinica 35, 5, 789--794.

[38]

X. Yang, D. J. Evans, and G. M. Megson. 2005. The locally twisted cubes. Int. J. Comput. Math. 82, 4, 401--413.

[39]

J. Zheng, S. Latifi, E. Regentova, K. Luo, and X. Wu. 2005. Diagnosability of star graphs under the comparison diagnosis model. Inform. Process. Lett. 93, 29--36.

Digital Library

Cited By

Senhadji-Navarro RGarcia-Vargas I(2023)Mapping Outputs and States Encoding Bits to Outputs Using Multiplexers in Finite State Machine ImplementationsElectronics10.3390/electronics1203050212:3(502)Online publication date: 18-Jan-2023
https://doi.org/10.3390/electronics12030502
Feng WWang S(2020)The Diagnosability of Wheel Networks with Missing Edges under the Comparison ModelMathematics10.3390/math81018188:10(1818)Online publication date: 16-Oct-2020
https://doi.org/10.3390/math8101818
Zhu QLi LLiu SZhang X(2019)Hybrid fault diagnosis capability analysis of hypercubes under the PMC model and MM⁎ modelTheoretical Computer Science10.1016/j.tcs.2018.07.019758(1-8)Online publication date: Feb-2019
https://doi.org/10.1016/j.tcs.2018.07.019
Show More Cited By

Index Terms

Diagnosability of Component-Composition Graphs in the MM* Model
1. Hardware
  1. Hardware test
  2. Robustness
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Component-Composition Graphs: (t,k)-Diagnosability and Its Application

$((t,k))$-diagnosis, which is a generalization of sequential diagnosis, requires that at least $(k)$ faulty processors should be identified and repaired in each iteration provided there are at most $(t)$ faulty processors, where $(t\ge k)$. In this ...
(t,k)-Diagnosis for Component-Composition Graphs under the MM* Model

(t,k)-Diagnosis, which is a generalization of sequential diagnosis, requires that at least k faulty processors be identified and replaced in each iteration provided there are at most t faulty processors, where t \ge k. Let \kappa (G) and n(G) be, ...
The g-good-neighbor diagnosability of (n,k)-star graphs

Many large-scale multiprocessor or multi-computer systems take interconnection networks as underlying topologies. Fault diagnosis is especially important to identify fault tolerability of such systems. The g-good-neighbor (conditional) diagnosability ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 19, Issue 3

June 2014

257 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/2634048

Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 23 June 2014

Accepted: 01 February 2014

Revised: 01 October 2013

Received: 01 May 2013

Published in TODAES Volume 19, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

National Science Council Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
118
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)1

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Senhadji-Navarro RGarcia-Vargas I(2023)Mapping Outputs and States Encoding Bits to Outputs Using Multiplexers in Finite State Machine ImplementationsElectronics10.3390/electronics1203050212:3(502)Online publication date: 18-Jan-2023
https://doi.org/10.3390/electronics12030502
Feng WWang S(2020)The Diagnosability of Wheel Networks with Missing Edges under the Comparison ModelMathematics10.3390/math81018188:10(1818)Online publication date: 16-Oct-2020
https://doi.org/10.3390/math8101818
Zhu QLi LLiu SZhang X(2019)Hybrid fault diagnosis capability analysis of hypercubes under the PMC model and MM⁎ modelTheoretical Computer Science10.1016/j.tcs.2018.07.019758(1-8)Online publication date: Feb-2019
https://doi.org/10.1016/j.tcs.2018.07.019
Lin LXu LZhou SHsieh S(2016)The Extra, Restricted Connectivity and Conditional Diagnosability of Split-Star NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2015.240045927:2(533-545)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1109/TPDS.2015.2400459
Lin LXu LZhou S(2015)Conditional diagnosability and strong diagnosability of Split-Star Networks under the PMC modelTheoretical Computer Science10.1016/j.tcs.2014.10.046562:C(565-580)Online publication date: 11-Jan-2015
https://dl.acm.org/doi/10.1016/j.tcs.2014.10.046

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents