| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
(t, k) - Diagnosis for Matching Composition Networks under the MM* Model
January 2007 (vol. 56 no. 1)
pp. 73-79
(t, k) - diagnosis, which is a generalization of sequential diagnosis, requires at least k faulty processors identified and repaired in each iteration provided there are at most t faulty processors, where t\geq k. In this paper, a (t,k){\hbox{-}}\rm diagnosis algorithm under the MM* model is proposed for matching composition networks, which include many well-known interconnection networks, such as hypercubes, crossed cubes, twisted cubes, and Möbius cubes. It is shown that a matching composition network of n dimensions is (\Omega({\frac{2^{n}\ast\log n}{n}}),n){\hbox{-}}\rm diagnosable.
[1] 73 T. Araki and Y. Shibata, “$(t,k){\hbox{-}}\rm Diagnosable$ System: A Generalization of the PMC Models,” IEEE Trans. Computers, vol. 52, no. 7, pp. 971-975, July 2003.[2] T. Araki and Y. Shibata, “Diagnosability of Butterfly Networks under the Comparison Approach,” IEICE Trans. Fundamentals of Electronics Comm. and Computer Science, vol. E85-A, no. 5, pp. 1152-1160, 2002.[3] A. Caruso, S. Chessa, P. Maestrini, and P. Santi, “Diagnosability of Regular Systems,” J. Algorithms, vol. 1, no. 1, pp. 1-12, 2002.[4] C.P. Chang, P.L. Lai, J.J.M. Tan, and L.H. Hsu, “Diagnosability of $t{\hbox{-}}\rm Connected$ Networks and Product Networks under the Comparison Diagnosis Model,” IEEE Trans. Computers, vol. 53, no. 12, pp.1582-1590, Dec. 2004.[5] G.Y. Chang, G.H. Chen, and G.J. Chang, “$(t,k){\hbox{-}}\rm Diagnosis$ for Matching Composition Networks,” IEEE Trans. Computers, vol. 55, no. 1, pp. 88-92, Jan. 2006.[6] G.Y. Chang, “$(t,k){\hbox{-}}\rm Diagnosis$ for Grids and Tori under the PMC and MM* Models,” manuscript.[7] G.Y. Chang, “System-Level Diagnosis for Multiprocessor Systems,” PhD dissertation, Dept. of Computer Science and Information Eng., Nat'l Taiwan Univ., Taipei, Taiwan, 2005.[8] S. Chessa and P. Maestrini, “Correct and Almost Complete Diagnosis of Processor Grids,” IEEE Trans. Computers, vol. 50, no. 10, pp. 1095-1102, Oct. 2001.[9] P. Ciompi and L. Simoncini, “Analysis and Optimal Design of Self-Diagnosable Systems with Repair,” IEEE Trans. Computers, vol. 28, no. 5, pp. 362-365, May 1979.[10] P. Cull and S.M. Larson, “The Möbius Cubes,” IEEE Trans. Computers, vol. 44, no. 5, pp. 647-659, May 1995.[11] A.T. Dahbura, “System-Level Diagnosis: A Perspective for the Third Decade,” Concurrent Computation: Algorithms, Arhcitectures, Technologies, Plenum, 1988.[12] A.T. Dahabura and G.M. Masson, “An O(n2.5) Fault Identification Algorithm for Diagnosable Systems,” IEEE Trans. Computers, vol. 33, no. 6, pp. 486-492, June 1984.[13] K. Efe, “A Variation on the Hypercube with Lower Diameter,” IEEE Trans. Computers, vol. 40, no. 11, pp. 1312-1316, Nov. 1991.[14] J. Fan, “Diagnosability of the Möbius Cubes,” IEEE Trans. Parallel and Distributed Systems, vol. 9, no. 9, pp. 923-927, Sept. 1998.[15] J. Fan, “Diagnosability of Crossed Cubes under the Comparison Diagnosis Model,” IEEE Trans. Parallel and Distributed Systems, vol. 13, no. 7, pp. 687-692, July 2002.[16] A.D. Friedman and L. Simoncini, “System-Level Fault Diagnosis,” The Computer J., vol. 13, no. 3, pp. 47-53, 1980.[17] H. Fujiwara and K. Kinoshita, “On the Computational Complexity of System Diagnosis,” IEEE Trans. Computers, vol. 27, no. 10, pp.881-885, Oct. 1978.[18] S. Hart, “A Note on the Edges of the $n{\hbox{-}}\rm Cube$ ,” Discrete Math., vol. 14, pp. 157-163, 1976.[19] P.A.J. Hilbers, M.R.J. Koopman, and J.L.A. van de Snepscheut, “The Twisted Cubes,” Proc. Parallel Architecture and Language Europe, pp. 152-159, June 1987.[20] A. Kavianpour, “Sequential Diagnosability of Star Graphs,” Computers Electrical Eng., vol. 22, no. 1, pp. 37-44, 1996.[21] A. Kavianpour and K.H. Kim, “Diagnosabilities of Hypercubes under the Pessimistic One-Step Diagnosis Strategy,” IEEE Trans. Computers, vol. 40, no. 2, pp. 232-237, Feb. 1991.[22] S. Khanna and W.K. Fuchs, “A Linear Time Algorithm for Sequential Diagnosis in Hypercubes,” J. Parallel and Distributed Computing, vol. 26, pp. 38-53, 1995.[23] S. Khanna and W.K. Fuchs, “A Graph Partitioning Approach to Sequential Diagnosis,” IEEE Trans. Computers, vol. 46, no. 1, pp.39-47, Jan. 1997.[24] C. Kime, “System Diagnosis,” Fault-Tolerant Computing: Theory and Techniques, D.K. Pradhan, ed., vol. II, chapter 8, Prentice Hall, 1986.[25] P.L. Lai, J.J.M. Tan, C.H. Tsai, and L.H. Hsu, “The Diagnosability of the Matching Composition Network under the Comparison Diagnosis Model,” IEEE Trans. Computers, vol. 53, no. 8, pp. 1064-1069, Aug. 2004.[26] P.L. Lai, J.J.M. Tan, C.P. Chang, and L.H. Hsu, “Conditional Diagnosability Measures for Large Multiprocessor Systems,” IEEE Trans. Computers, vol. 54, no. 2, pp. 165-175, Feb. 2005.[27] J. Maeng and M. Malek, “A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor Systems,” Digest Int'l Symp. Fault Tolerant Computing, pp. 173-175, 1981.[28] M. Malek, “A Comparison Connection Assignment for Diagnosable of Multiprocessor Systems,” Proc. Seventh Ann. Symp. Computer Architecture, pp. 31-36, 1980.[29] F.P. Preparata, G. Metze, and R.T. Chien, “On the Connection Assignment Problem of Diagnosable Systems,” IEEE Trans. Electronic Computers, vol. 16, pp. 848-854, 1967.[30] V. Raghavan and A. Tripathi, “Sequential Diagnosability Is Co-NP Complete,” IEEE Trans. Computers, vol. 40, no. 5, May 1991.[31] Y. Saad and M.H. Schultz, “Topological Properties of Hypercubes,” IEEE Trans. Computers, vol. 37, no. 7, pp. 867-872, July 1988.[32] A. Sengupta and A.T. Danbura, “On Self-Diagnosable Multiprocessor Systems: Diagnosis by the Comparison Approach,” IEEE Trans. Computers, vol. 41, no. 11, pp. 1386-1396, Nov. 1992.[33] A.K. Somani, V.K. Agarwal, and D. Avis, “A Generalized Theory for System Level Diagnosis,” IEEE Trans. Computers, vol. 36, no. 5, pp. 538-546, May 1987.[34] D. Wang, “Diagnosability of Enhanced Hypercubes,” IEEE Trans. Computers, vol. 43, no. 9, pp. 1054-1061, Sept. 1994.[35] D. Wang, “Diagnosability of Hypercubes and Enhanced Hypercubes under the Comparison Diagnosis Model,” IEEE Trans. Computers, vol. 48, no. 12, pp. 1369-1374, Dec. 1999.[36] D.B. West, Introduction to Graph Theory, second ed. Prentice Hall, 2001.[37] J. Xu and S.Z. Huang, “Sequentially t-Diagnosable Systems: A Characterization and Its Application,” IEEE Trans. Computers, vol. 44, no. 2, pp. 340-345, Feb. 1995.[38] X. Yang, “A Linear Time Fault Diagnosis Algorithm for Hypercube Multiprocessors under the MM* Comparison Model,” Proc. 11th Int'l Symp. Fault-Tolerant Computing, pp. 173-175, 1980.
Index Terms:
Diagnosability, matching composition network, MM* model, multiprocessor system, precise diagnosis strategy, (t,k){\hbox{-}}\rm diagnosis.
Citation:
Guey-Yun Chang, Gen-Huey Chen, Gerard J. Chang, "(t, k) - Diagnosis for Matching Composition Networks under the MM* Model," IEEE Transactions on Computers, vol. 56, no. 1, pp. 73-79, Jan. 2007, doi:10.1109/TC.2007.1
