[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A fast pessimistic diagnosis algorithm for generalized hypercube multicomputer systems

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

The reliability of processors is an important issue for designing a massively parallel processing system for which fault-tolerant computing is crucial. In order to achieve high system reliability and availability, a faulty processor (node) when found should be replaced by a fault-free processor. Within a multiprocessor system, the technique of identifying faulty nodes by constructing tests on the nodes and interpreting the test outcomes is known as system-level diagnosis. The topological structure of a multicomputer system can be modeled by a graph of which the vertices and edges correspond to nodes and links of the system, respectively. This work presents a system-level diagnosis algorithm for a generalized hypercube which is an attractive variance of a hypercube. The proposed algorithm is based on the PMC model and can isolate all faulty nodes to within a set which contains at most one fault-free node. If the total number of nodes to be diagnosed in a generalized hypercube is N, the proposed algorithm can run in O(Nlog N) time, and being superior to Yang’s algorithm proposed in 2004, it can diagnose not only a hypercube but also a generalized hypercube.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Altman J et al (1996) Constraint based system-level diagnosis of multiprocessors. In: Proceedings of IEEE 2nd European dependable computing conference, pp 403–414

    Google Scholar 

  2. Arabnia HR (1990) A parallel algorithm for the arbitrary rotation of digitized images using process-and-data-decomposition approach. J Parallel Distrib Comput 10(2):188–192

    Article  Google Scholar 

  3. Arabnia HR, Oliver MA (1989) A transputer network for fast operations on digitised images. Comput Graph Forum 8(1):3–12

    Article  Google Scholar 

  4. Arabnia HR (1993) A transputer-based reconfigurable parallel system. In: Proceedings of the sixth conference of North American transputer users group on transputer research and applications 6 (NATUG-6), IOS Press, Vancouver, Canada, pp 153–169

    Google Scholar 

  5. Armstrong JR, Gray FG (1981) Fault diagnosis in a Boolean n cube array of microprocessors. IEEE Trans Comput C-30:587–590

    Article  Google Scholar 

  6. Bartha T, Selenyi E (1997) Probabilistic system-level fault diagnostic algorithms for multiprocessors. Parallel Comput 22(13):1807–1821

    Article  MATH  Google Scholar 

  7. Bhandarkar SM, Arabnia HR (1995) The REFINE multiprocessor—theoretical properties and algorithms. Parallel Comput 21(11):1783–1805

    Article  Google Scholar 

  8. Bhuyan LN, Agrawal DP (1984) Generalized hypercube and hyperbus structures for a computer network. IEEE Trans Comput 33:323–333

    Article  MATH  Google Scholar 

  9. Bondy JA, Murty USR (1980) Graphs theory with applications. North-Holland, New York

    Google Scholar 

  10. Caruso A, Chessa S, Maestrini P, Santi P (2002) Diagnosability of regular systems. J Algorithms 45:126–143

    Article  MathSciNet  MATH  Google Scholar 

  11. Chang GY, Chang GJ, Chen GH (2005) Diagnosabilities of regular networks. IEEE Trans Parallel Distrib Syst 16(4):314–323

    Article  MathSciNet  Google Scholar 

  12. Chang GY, Chen GH, Chang GJ (2006) (t,k)-Diagnosis for matching composition networks. IEEE Trans Comput 55(1):88–92

    Article  MathSciNet  Google Scholar 

  13. Chang GY, Chen GH (2007) (t,k)-Diagnosability of multiprocessor systems with applications to grids and tori. SIAM J Comput 37(4):1280–1298

    Article  MathSciNet  MATH  Google Scholar 

  14. Chwa KY, Hakimi SL (1981) On fault identification in diagnosable systems. IEEE Trans Comput C-30:414–422

    Article  MathSciNet  Google Scholar 

  15. Cull P, Larson SM (1995) The Mobius cubes. IEEE Trans Comput 44:648–659

    Article  MathSciNet  Google Scholar 

  16. Efe K (1992) The crossed cube architecture for parallel computation. IEEE Trans Parallel Distrib Syst 3(5):513–524

    Article  Google Scholar 

  17. Fan J, Lin X (2005) The t/k-diagnosability of the BC graphs. IEEE Trans Comput 54(2):176–184

    Article  Google Scholar 

  18. Kavianpour A, Friedman AD (1978) Efficient design of easily diagnosable system. In: Proceedings of the 3th IEEE computer society’s USA–Japan computer conference, pp 173–181

    Google Scholar 

  19. Kavianpour A, Friedman AD (1984) Trade-offs in system level diagnosis of multiprocessor systems. In: Proceedings of AFIP national computer conference, pp 173–181

    Google Scholar 

  20. Kavianpour A, Kim KH (1991) Diagnosabilities of hypercubes under the pessimistic one-step diagnosis strategy. IEEE Trans Comput 40:232–237

    Article  Google Scholar 

  21. Khanna S, Fuchs WK (1997) A graph partitioning approach to sequential diagnosis. IEEE Trans Comput 46:39–47

    Article  MathSciNet  Google Scholar 

  22. Kranakis E, Pelc A (2000) Better adaptive diagnosis of hypercubes. IEEE Trans Comput 49:1013–1020

    Article  MathSciNet  Google Scholar 

  23. Lee RCT, Chang RC, Tseng SS, Tsai YT (1999) Introduction to the design and analysis of algorithms. Unalis Corporation, Taiwan

    Google Scholar 

  24. Maeng J, Malek M (1981) A comparison connection assignment for self-diagnosis of multiprocessor systems. In: Proc. 11th int’l symp. fault-tolerant computing, pp 173–175

    Google Scholar 

  25. Malek M (1980) A comparison connection assignment for diagnosis of multiprocessor systems. In: Proc. seventh int’l symp. computer architecture, pp 31–35

    Chapter  Google Scholar 

  26. Parhami B (1999) An introduction to parallel processing: algorithms and architectures. Plenum, New York

    Google Scholar 

  27. Preparata FP, Metze G, Chien RT (1967) On the connection assignment problem of diagnosable systems. IEEE Trans Comput 16:448–454

    Google Scholar 

  28. Somani AK (1997) System level diagnosis: a review. Technical report, Dependable Computing Laboratory, Iowa State University

  29. Somani AK, Peleg O (1996) On diagnosability of large fault sets in regular topology-based computer systems. IEEE Trans Comput 45(8):892–903

    Article  MATH  Google Scholar 

  30. Sullivan G (1984) A polynomial time algorithm for fault diagnosability. In: Proceedings of the 25th annual symposium on foundations of computer science, pp 148–156

    Google Scholar 

  31. Tzeng NF, Wei S (1991) Enhanced hypercubes. IEEE Trans Comput 40(3):284–294

    Article  Google Scholar 

  32. West DB (2001) Introduction to Graph theory, 2nd edn. Prentice-Hall, Upper Saddle River

    Google Scholar 

  33. Xu J (2001) Topological structure and analysis of interconnection networks. Kluwer Academic, Dordrecht

    MATH  Google Scholar 

  34. Yang X (2004) A fast pessimistic one-step diagnosis algorithm for hypercube multicomputer systems. J Parallel Distrib Comput 64:546–553

    Article  MATH  Google Scholar 

  35. Yang CL, Masson GM, Leonetti RA (1986) On fault isolation and identification in t 1/t 1-diagnosable systems. IEEE Trans Comput 35(7):639–643

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Information Engineering, National Chi Nan University, Puli, Nantou Hsien, 54561, Taiwan

    Dyi-Rong Duh, Chien-Hong Chen & Keh-Ning Chang

Authors
  1. Dyi-Rong Duh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chien-Hong Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Keh-Ning Chang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dyi-Rong Duh.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Duh, DR., Chen, CH. & Chang, KN. A fast pessimistic diagnosis algorithm for generalized hypercube multicomputer systems. J Supercomput 61, 605–618 (2012). https://doi.org/10.1007/s11227-011-0620-6

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-011-0620-6

Keywords

Search

Navigation