在多處理器系統的錯誤診斷下，藉由比較診斷模式來偵錯是一個實際可行的方法。在系統層級之錯誤診斷下，比較診斷模式是更引人注意的方法。在MM*診斷模式下，我們假設在系統中的每個處理器都會診斷任二個有直接連結的處理器並且比較它們的回傳值是否相同。學者 Sengupta 和 Dahbura 在MM*診斷模式下，提出一個針對一般化可診斷系統之偵錯演算法，如果 N 代表此系統之處理器數量，則此偵錯演算法的時間複雜度為O(N5)。在本篇論文中，於MM*診斷模式下，我們藉由迴圈分解的性質，提出一個針對類超立方體之偵錯演算法，而我們的時間複雜度可以達到 (N(log2N)2)。

Diagnosis by comparison is a realistic approach to the fault diagnosis of multiprocessor systems. Comparison-based diagnosis is attractive approach to system-level fault diagnosis. The MM* comparison model assumes that every processor in the system to be diagnosed makes a comparison between the responses of any two processors with which it can communicate directly to the same system tasks. Sengupta and Dahbura proposed a diagnosis algorithm for general diagnosable systems under the MM* model, with O(N5) time complexity, where N is the number of processors in the system. In this thesis, we propose a diagnosis algorithm for hypercube-like networks under the MM* comparison model by exploiting cycle decomposition properties, and our diagnosis algorithm can achieve O(N(log2N)2) time complexity.

[1] J.R. Armstrong and F.G. Gray, "Fault diagnosis in a boolean n cube array of multiprocessors," IEEE Transaction on Computers, vol. 30, no. 8, pp. 587-590, 1981.
[2] S. Abraham and K. Padmanabhan, "The Twisted Cube Topology for Multiprocessors: A Study of Network Asymmetry," Journal of Parallel and Distributed Computing, vol. 13, no. 1, pp. 104-110, 1991.
[3] T. Araki and Y. Shibata, "Diagnosability of Butterfly Networks under the comparison approach," IEICE Transaction on Fundamentals of Electronics Communications and Computer Science, vol. E85-A, pp. 1152-1160, 2002.
[4] T. Araki and Y. Shibata, "(t, k)-Diagnosable System: A Generalization of the PMC models," IEEE Transaction on Computers, vol. 52, no. 7, pp. 971-975, 2003.
[5] F.B. Chedid, "On the Generalized Twisted Cube," Information Processing Letters, vol. 55, no. 1, pp. 49-52, 1995.
[6] F.B. Chedid and R.B. Chedid, "A new variation on hypercubes with smaller diameter," Information Processing Letters, vol. 46, no. 6, pp. 275-280, 1993.
[7] G.Y. Chang, G.J. Chang, and G.H. Chen, "Diagnosabilities of Regular Networks," IEEE Transaction on Parallel and Distributed Systems, vol. 16, pp. 314-323, 2005.
[8] G.Y. Chang, G.H. Chen, and G.J. Chang, "(t, k)-Diagnosis for Matching Composition Networks," IEEE Transaction on Computers, vol. 55, no. 1, pp. 88-92, 2006.
[9] K.Y. Chwa and S.L. Hakimi, "Schemes for fault tolerant computing: a comparison of modularly redundant and t-diagnosisable systems," Information and Control, vol. 49 , pp. 212-238, 1981.
[10] K.Y. Chwa and L. Hakimi, "On Fault Identification in Diagnosable Systems," IEEE Transaction on Computers, vol. 30, no. 6, pp. 414-422, 1981.
[11] N.W. Chang and S.Y. Hsieh, "Conditional diagnosability of augmented cubes under the PMC model," IEEE Transaction on Dependable and Secure Computing, accepted.
[12] P. Cull and S.M. Larson, "The Mobius Cubes," IEEE Transaction on Parallel and Distributed Systems, vol. 44, no. 5, pp. 647-659, 1995.
[13] C.P. Chang, J.N. Wang, and L.H. Hsu, "Topological properites of twisted cubes," Information Sciences, vol. 113, pp. 147-167, 1999.
[14] C.P. Chang, T.Y. Sung, and L.H. Hsu, "Edge congestion and topological properites of crossed cube," IEEE Transaction on Parallel and Distributed Systems, vol. 11, no. 1, pp. 64-80, 2000.
[15] C.F. Chiang and J. J.M. Tan, "A Novel Approach to Comparison-Based Diagnosis for Hypercube-Like Systems," Journal of Information Science and Engineering, vol. 24, no. 1, pp. 1-9, 2008.
[16] R. Diestel, Graph Theory, third edition, Springer-Heidelberg, 2005.
[17] A.T. Dahbura and G.M. Masson, "A O(n2.5) Fault Identi¯cation Algorithm for Diagnosable Systems," IEEE Transaction on Computers, vol. 3, no. 6, pp. 486-492, 1984.
[18] E.P. Duarte Jr. and T. Nanya, "A Hierarchical Adaptive Distributed System-Level Diagnosis Algorithm," IEEE Transaction on Computers, vol. 47, no. 1, pp. 35-45, 1998.
[19] K. Efe, "A variation on the hypercube with lower diameter," IEEE Transaction on Computers, vol. 40, no. 11, pp. 1312-1316, 1991.
[20] K. Efe, "The Crossed Cube Architecture for Parallel Computation," IEEE Transaction on Parallel and Distributed Systems, vol. 3, no. 5, pp. 513-524, 1992.
[21] K. Efe, P.K. Blackwell, W. Slough, and T. Shiau, "Topological properties of the crossed cube architechure," Parallel Computing, vol. 20, pp. 1763-1775, 1994.
[22] J. Fan, "Diagnosability of the Mobius cubes," IEEE Transaction on Parallel and Distributed Systems, vol. 9, pp. 923-928, 1998.
[23] J. Fan, "Diagnosability of Crossed Cubes under the Comparison Diagnosis Model," IEEE Transaction on Parallel and Distributed Systems, vol. 13, pp. 687-692, 2002.
[24] J. Fan and X. Lin, "The t/k-Diagnosability of the BC Graphs," IEEE Transaction on Computers, vol. 54, no. 2, pp. 176-184, 2005.
[25] A.D. Friedman and L. Simoncini, "System-Level Fault Diagnosis," The Computer Journal, vol. 13, no. 3, pp. 47-53, 1980.
[26] A. Ghafoor, "Partitioning of Even Networks for Improved Diagnosability," IEEE Transaction on Reliability, vol. 39, no. 3, pp. 281-286, 1990.
[27] S.L. Hakimi and A.T. Amin, "Characterization of connection assignment of diagnosable systems," IEEE Transaction on Computers, vol. 23, pp. 86-88, 1974.
[28] S.Y. Hsieh and Y.S. Chen, "Strongly diagnosable product networks under the comparison diagnosis model," IEEE Transaction on Computers, vol. 57, no. 6, pp. 721-732, 2008.
[29] S.Y. Hsieh and Y.S. Chen, "Strongly diagnosis systems under the comparison diagnosis model," IEEE Transaction on Computers, vol. 57, no. 12, pp. 1720-1725, 2008.
[30] S.Y. Hsieh and C.W. Lee, "Diagnosability of Two-Matching Composition Networks under the MM* model," IEEE Transaction on Dependable and Secure Computing, accepted.
[31] P.A.J. Hilbers, M.R.J. Koopman, and J.L.A. van de Snepscheut, "The twisted cube," Proceedings of the Conference on Parallel Architectures and Languages Europ, Volume I: Parallel Architectures, pages 152-159, 1987.
[32] G.H. Hsu and J.J.M. Tan, "Conditional diagnosability of the BC Networks under the comparison diagnosis model," International Computer Symposium, vol. 1, pp. 269-274, 2008.
[33] A. Kavianpour, "Sequential diagnosability of star graphs," Computers and Electrical Engineering, vol. 22, no. 1, pp. 37-44, 1996.
[34] P. Kulasinghe and S. Betayeb, "Embedding binary trees into crossed cubes," IEEE Transaction on Computers, vol. 44, no. 7, pp. 923-929, 1995.
[35] P. Kulasinghe, "Connectivity of the crossed cube," Information Processing Letters, vol. 61, pp. 221-226, 1997.
[36] A. Kavianpour and K.H. Kim, "Diagnosability of hypercubes under the pessimistic one-step diagnosis strategy," IEEE Transaction on Computers, vol. 40, no. 2, pp. 232-237, 1991.
[37] A. Kavianpour and A.D. Friedman, "Efficient Design of Easily Diagnosable System," inProceedings of the 3th IEEE Computer Society's USA-Japan Computer Conference, pp. 173-181, 1978.
[38] S. Khanna and W.K. Fuchs, "A Linear Time Algorithm for Sequential Diagnosis in Hypercubes," Journal of Parallel and Distributed Computing, vol. 26, pp. 48-53, 1995.
[39] S. Khanna and W.K. Fuchs, "A Graph Partitioning Approach to Sequential Diagnosis," IEEE Transaction on Computers, vol. 46, no. 1, pp. 39-47, 1997.
[40] E. Kranakis and A. Pelc, "Better Adaptive Diagnosis of Hypercubes," IEEE Transaction on Computers, vol. 49, no. 10, pp. 1013-1020, 2000.
[41] P.L. Lai, J.J.M. Tan, C.H. Tsai, and L.H. Hsu, "The Diagnosability of Matching Composition Network under the comparison diagnosis model," IEEE Transaction on Computers, vol. 53, pp. 1064-1069, 2004.
[42] P.L. Lai, J.J.M. Tan, C.P. Chang, and L.H. Hsu, "Conditional diagnosability measures for large multiprocessor systems," IEEE Transaction on Computers, vol. 54, no. 2, pp. 165-175, 2005.
[43] P.L. Lai, J.J.M. Tan, L.H. Hsu, and E. Cheng, "Conditional diagnosability of Cayley Graphs generated by transposition trees," Journal of Interconnection Networks, vol. 9, no. 1-2, pp. 83-97, 2008.
[44] M. Malek, "A Comparison Connection Assignment for Diagnosis of Multiprocessor Systems," Proceedings of Seventh Int'l Symposium Computer Architecture, pp. 31-35, 1980.
[45] J. Maeng and M. Malek, "A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor Systems," Proc. 11th Int'l Symposium Fault-Tolerant Computing, pp. 173-175, 1981.
[46] C.-D. Park and K.Y. Chwa, "Hamiltonian Properties on the Class of Hypercube-Like Networks," Information Processing Letters, vol. 91, pp. 11-17, 2004.
[47] J.H. Park, H.C. Kim and H.S. Lim, "Fault-Hamiltonicity of Hypercube-Like Interconnection Networks," in Proceedings of the 19th IEEE International Parallel and Distributed Prcessing Symposium (IPDPS'05), Denver, CA, USA, Apr. 2005. IEEE Computer Society.
[48] F.P. Preparata, G. Metze, and R.T. Chien, "On the Connection Assignment Problem of Diagnosable Systems," IEEE Transaction on Computers, vol. 16, no. 12, pp. 448-454, 1967.
[49] M. Pease, R. Shostak, and L. Lamport, "Reaching Agreement in the Presence of Faults," Journal of ACM, vol. 27, no. 2, pp. 228-234, 1980.
[50] G. Sullivan, "An O(t3+|E|) Fault Identification Algorithm for Diagnosable Systems," IEEE Transaction on Computers, vol. 37, no. 4, pp. 388-397, 1988.
[51] A.K. Somani, "Sequential Fault Occurrence and Recon¯guration in System Level Diagnosis," IEEE Transaction on Computers, vol. 39, no. 12, pp. 1472-1475, 1990.
[52] A.K. Somani, "System Level Diagnosis: A Review," Technical Report, Dependable Computing Laboratory, Iowa State University, 1997.
[53] A. Subbiah and D.M. Blough, "Distributed Diagnosis in Dynamic Fault Environments," IEEE Transaction on Parallel and Distributed Systems, vol. 15, no. 5, pp. 453-467, 2004.
[54] A. Senqupta and A.T. Dahbura, "On Self-Diagnosable Multiprocessor Systems: Diagnosis by the Comparison Approach," IEEE Transaction on Computers, vol. 41, no. 11, pp. 1386-1396, 1992.
[55] A.K. Somani and O. Peleg, "On Diagnosability of Large Fault Sets in Regular Topology-Based Computer Systems," IEEE Transaction on Computers, vol. 45, no. 8, pp. 892-903, 1996.
[56] Y. Saad and M.H. Schultz, "Topological Properties of Hypercubes," IEEE Transaction on Computers, vol. 37, no. 7, pp. 867-872, 1988.
[57] A.S. Vaidya, P.S.N. Rao, and S.R. Shankar, "A Class of Hypercube-Like Networks," Proc. Fifth IEEE symposium Parallel and Distributed Processing(SPDP), pp. 800-803, 1993.
[58] D. Wang, "Diagnosability of Enhanced Hypercubes," IEEE Transaction on Computers, vol. 43, pp. 1054-1061, 1994.
[59] D. Wang, "Diagnosability of Hypercubes and Enhanced Hypercubes under the comparison diagnosis model," IEEE Transaction on Computers, vol. 48, pp. 1369{1374, 1999.
[60] X.F. Yang, "A Linear Time Fault Diagnosis Algorithm for Hypercube Multiprocessors under the MM* Comparison Model," Proceedings of the 12th Asian Test Symposium (ATS'03), pp. 50, 2003.
[61] X.F. Yang, "A Fast Pessimistic one-step Diagnosis Algorithm for Hypercube Multicomputer Systems," Journal of Parallel and Distributed Computing, vol. 64, no. 4, pp. 546-553, 2004.
[62] X.F. Yang, D.J. Evans, and G.M. Megson, "The Locally Twisted Cube," International Journal of Computer Mathematics, vol. 82, no. 4, pp. 401-413, 2005.
[63] X.F. Yang, G.M. Megson, and D.J. Evans, "A Comparison-based Diagnosis Algorithm tailored for Crossed Cube Multiprocessor Systems," Microprocessors and Microsystems, vol. 29, no. 4, pp. 169-175, 2005.
[64] C.-L. Yang, G.M. Masson, and R.A. Leonetti, "On Fault Isolation and Identification in t1/t1-Diagnosable Systems," IEEE Transaction on Computers, vol. 35, no. 6, pp. 639-643, 1986.
[65] X. Yang and Y.Y. Tang, "A (4n-9)/3 Diagnosis Algorithm on n-Dimensional Cube Network," Information Sciences, vol. 177, no. 8, pp. 1771-1781, 2007.
[66] H. Yang and X.F. Yang, "A Fast Diagnosis Algorithm for Locally Twisted Cube Multiprocessor Systems under the MM* model," Computers and Mathematics with Applications, vol. 53, no. 6, pp. 918-926, 2007.
[67] J. Zheng, S. Latii, E. Regentova, and X. Wu, "Diagnosability of Star Graphs under the Comparison Diagnosis Model," Information Processing Letters, vol. 93, no. 1, pp. 29-36, 2005.
[68] J. Zhao, F.J. Meyer, N. Park, and F. Lombardi "Sequential Diagnosis of Processor Array Systems," IEEE Transaction on Reliability, vol. 53, pp. 487-498, 2004.