隨著超大型積體電路科技的蓬勃發展及開發，多處理器系統可能會有成千上萬個處理器。對於一個龐大的平行處理系統而言，錯誤容忍度是值得探討的重要議題，因此多處理器系統的可靠度變得十分重要。為了維持多處理器系統之高可靠度，當一個處理器被判定是錯誤的處理器時，此處理器必須要由其他好的處理器所替換之。而把這些錯誤處理器找出來的方法，我們稱之為錯誤診斷。在多處理器系統的錯誤診斷下，藉由測試診斷模式或比較診斷模式來偵錯是常見且可行的方法，在本篇論文中，我們使用的方法是比較診斷模式。在比較診斷模式下，我們假設在系統中的每個處理器都會診斷任二個有直接連結的處理器並且比較它們的回傳值是否相同。
學者 Sengupta 和 Dahbura 提出了MM*診斷模式，並提出一個針對一般化可診斷系統之精確偵錯演算法，如果 N 代表此系統之處理器數量，則此精確偵錯演算法的時間複雜度為O(N5)。在本篇論文中，在MM*診斷模式下，我們提出一個針對類超立方體可診斷系統之精確偵錯演算法，而此精確偵錯演算法的時間複雜度為O(N(log2N)2)。而藉由漢米爾頓迴圈的性質，於MM*診斷模式下，我們提出一個針對類超立方體之精確偵錯演算法，而此精確偵錯演算法的時間複雜度更降低為O(N)。
我們可以把所提出之精確偵錯演算法應用在超立方體、交叉立方體、莫氏立方體、廣義雙扭立方體、雙扭立方體、局部雙扭立方體、遞迴環狀圖，透過我們所設計之精確偵錯演算法，所有錯誤處理器都可以在線性時間之內被找出來。

With the rapid development of technology, multiprocessor systems may contain hundreds or even thousands of processors (nodes) that communicate by exchanging messages through an interconnection network. Fault-tolerance computing is important for a massively parallel processing system and the reliability of processors in it is therefore becoming an important issue. In order to maintain high system reliability, whenever a processor is found faulty, it should be replaced by a fault-free processor. The technique of identifying faulty processors by constructing tests on the processors and interpreting the outcomes is known as fault diagnosis. The precise fault diagnosis diagnoses all processors correctly. In the comparison diagnosis model, it allows a processor to perform diagnosis by contrasting the responses from a pair of neighboring processors through sending the identical assignment. Under the comparison diagnosis model, Sengupta and Dahbura put forward the MM* model and also designed a O(N5)-time precise fault diagnosis algorithm to diagnose faulty processors for general topologies by using the MM* model, where N is the number of processors in multiprocessor systems. In this thesis, we devised a O(N(log2 N)2)-time precise fault diagnosis algorithm to diagnose all faulty processors for hypercube-like networks by using the MM* model. Based on the Hamiltonian cycle properties, we improved the aforementioned results by presenting a O(N)-time precise fault diagnosis algorithm to diagnose all faulty processors for hypercube-like networks by using the MM* model. Applying our algorithms, the faulty processors in n-dimensional hypercubes, ndimensional crossed cubes, n-dimensional M¨obius cubes, n-dimensional generalized twisted cubes, n-dimensional twisted cubes, n-dimensional locally twisted cubes, and recursive circulants can all be diagnosed in linear time.

[1] 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.
[2] 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.
[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. T. Boesch and R. Tindell, “Circulants and their connectivities,” Journal of Graph Theory, vol.8, pp.129–138, 1984.
[6] F. B. Chedid, “On the generalized twisted cube,” Information Processing Letters, vol. 55, no. 1, pp. 49–52, 1995.
[7] 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.
[8] 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.
[9] 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.
[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] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Third Edition, The MIT Press, 2009 Massachusetts Institute of Technology.
[12] N.W. Chang and S.Y. Hsieh, “Conditional diagnosability of augmented cubes under the PMC model,” IEEE Transaction on Dependable and Secure Computing, vol. 9, no. 1, pp. 46{60, 2012..
[13] P. Cull and S. M. Larson, “The M¨obius cubes,” IEEE Transaction on Parallel and Distributed Systems, vol. 44, no. 5, pp. 647–659, 1995.
[14] C.P. Chang, J.N. Wang, and L.H. Hsu, “Topological properites of twisted cubes,” Information Sciences, vol. 113, pp. 147–167, 1999.
[15] 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.
[16] C. F. Chiang and 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.
[17] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. The MIT Press, 2009.
[18] R. Diestel, Graph Theory, third edition, Springer-Heidelberg, 2005.
[19] A. T. Dahbura and G. M. Masson, “A O(n2:5) fault identification algorithm for diagnosable systems,” IEEE Transaction on Computers, vol. 3, no. 6, pp. 486–492, 1984.
[20] 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.
[21] Elias P. Duarte Jr., Roverli P. Ziwich, and Luiz C. Albini, “A survey of comparisonbased system-level diagnosis,” ACM Computing Surveys, vol. 43, no. 22, Article 22, pp. 22:1–22:56, April 2011.
[22] K. Efe, “A variation on the hypercube with lower diameter,” IEEE Transaction on Computers, vol. 40, no. 11, pp. 1312–1316, 1991.
[23] K. Efe, “The Crossed Cube Architecture for Parallel Computation,” IEEE Transaction on Parallel and Distributed Systems, vol. 3, no. 5, pp. 513–524, 1992.
[24] 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.
[25] J. Fan, “Diagnosability of the M¨obius cubes,” IEEE Transaction on Parallel and Distributed Systems, vol. 9, pp. 923–928, 1998.
[26] J. Fan, “Diagnosability of Crossed Cubes under the Comparison Diagnosis Model,” IEEE Transaction on Parallel and Distributed Systems, vol. 13, pp. 687–692, 2002.
[27] 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.
[28] A.D. Friedman and L. Simoncini, “System-Level Fault Diagnosis,” The Computer Journal, vol. 13, no. 3, pp. 47–53, 1980.
[29] A. Ghafoor, “A class of fault-tolerant multiprocessor networks,” IEEE Transactions
on Reliability, vol. 38, no. 1, pp. 5–15, 1989.
[30] A. Ghafoor, “Partitioning of even networks for improved diagnosability,” IEEE Transactions on Reliability, vol. 39, no. 3, pp. 281–286, 1990.
[31] S.L. Hakimi and A.T. Amin, “Characterization of connection assignment of diagnosable systems,” IEEE Transaction on Computers, vol. 23, pp. 86–88, 1974.
[32] 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.
[33] 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.
[34] S.Y. Hsieh and C.W. Lee, “Diagnosability of Two-Matching Composition Networks under the MM* model,” IEEE Transaction on Dependable and Secure Computing, vol. 8, no. 2, pp. 246–255, 2011.
[35] 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.
[36] H. C. Hsu and P. L. Lai, “Adaptive diagnosis for grids under the comparison model,” The 26th International Conference on Advanced Information Networking and Applications Workshops, pages 1246–1251, 2012.
[37] 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.
[38] Y. Ishida, N. Adachi, and H. Tokumaru, “Diagnosability and distinguishability analysis and its applications,” IEEE Transactions on Reliability, vol. 36, no. 5, pp. 531–538, 1987.
[39] A. Kavianpour and K. H. Kim, “A comparative evaluation of four basic systemlevel diagnosis strategies for hypercubes,” IEEE Transactions on Reliability, vol. 41, no. 1, pp. 26–37, 1992.
[40] A. Kavianpour, “Sequential diagnosability of star graphs,” Computers and Electrical Engineering, vol. 22, no. 1, pp. 37–44, 1996.
[41] P. Kulasinghe and S. Betayeb, “Embedding binary trees into crossed cubes,” IEEE Transaction on Computers, vol. 44, no. 7, pp. 923–929, 1995.
[42] P. Kulasinghe, “Connectivity of the crossed cube,” Information Processing Letters, vol. 61, pp. 221–226, 1997.
[43] 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.
[44] A. Kavianpour and A. D. Friedman, “Efficient design of easily diagnosable system,” in Proceedings of the 3th IEEE Computer Society's USA-Japan Computer Conference, pp. 173–181, 1978.
[45] 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.
[46] 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.
[47] E. Kranakis and A. Pelc, “Better Adaptive Diagnosis of Hypercubes,” IEEE Transaction on Computers, vol. 49, no. 10, pp. 1013–1020, 2000.
[48] 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.
[49] 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.
[50] 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.
[51] M. Malek, “A Comparison Connection Assignment for Diagnosis of Multiprocessor Systems,” Proceedings of Seventh Int'l Symposium Computer Architecture, pp. 31–35, 1980.
[52] 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.
[53] Y. Pan, “Fault tolerance in the block-shift network,” IEEE Transactions on Reliability, vol. 50, no. 1, pp. 85–91, 2001.
[54] J. H. Park, “Panconnectivity and edge-pancyclicity of faulty recursive circulant G(2m, 4),” Theoretical Computer Science, vol. 390, no. 1, pp. 70–80, 2008.
[55] 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.
[56] J. H. Park and K. Y. Chwa, “Recursive circulant : a new topology for multicomputer networks,” in Proceedings of Internation Symposium Parallel Architectures, Algorithms and Networks(ISPAN'94), pp. 73–80. IEEE press, New York, 1994.
[57] 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.
[58] 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.
[59] 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.
[60] G. Simmons, “Almost all n-dimensional retangular lattices are Hamiltonian laceable,” Congressus Numerantium, vol. 21, pp. 103–108, 1978.
[61] G. Sullivan, “An O(t3+|E|) fault identification algorithm for diagnosable systems,” IEEE Transaction on Computers, vol. 37, no. 4, pp. 388–397, 1988.
[62] A.K. Somani, “Sequential Fault Occurrence and Reconfiguration in System Level Diagnosis,” IEEE Transaction on Computers, vol. 39, no. 12, pp. 1472–1475, 1990.
[63] A.K. Somani, “System Level Diagnosis: A Review,” Technical Report, Dependable Computing Laboratory, Iowa State University, 1997.
[64] 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.
[65] 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.
[66] 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.
[67] Y. Saad and M. H. Schultz, “Topological properties of hypercubes,” IEEE Transaction on Computers, vol. 37, no. 7, pp. 867–872, 1988.
[68] C. Tsai, “A quick pessimistic diagnosis algorithm for hypercube-like multiprocessor systems under the PMC model,” IEEE Transaction on Computers, vol. 62,
no. 2, pp. 259–267, 2013.
[69] 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.
[70] D. Wang, “Diagnosability of Enhanced Hypercubes,” IEEE Transaction on Computers, vol. 43, pp. 1054–1061, 1994.
[71] D. Wang, “Diagnosability of Hypercubes and Enhanced Hypercubes under the comparison diagnosis model,” IEEE Transaction on Computers, vol. 48, pp. 1369–
1374, 1999.
[72] T. L. Ye and S. Y. Hsieh, “A scalable comparison-based diagnosis algorithm for hypercube-like networks,” IEEE Transaction on Reliability, vol. 62, no. 4, pp.
789–799, 2013.
[73] 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.
[74] 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.
[75] 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.
[76] Liang-Cheng Ye, Jia-Rong Liang, and Hai-Xiang Lin, “A Fast Pessimistic Diagnosis Algorithm for Hypercube-Like Networks under the Comparison Model,” IEEE Transactions on Computers, vol. 65, pp. 2884-2888, Sept. 2016, doi:10.1109/TC.2015.2506562.
[77] 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.
[78] 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.
[79] X. Yang and Y. Y. Tang, “Efficient fault identification of diagnosable systems under the comparison model,” IEEE Transaction on Computers, vol. 56, no. 12, pp. 1612–1618, 2007.
[80] 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.
[81] 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.
[82] J. Zhao, F. J. Meyer, N. Park, and F. Lombardi, “Sequential diagnosis of processor array systems,” IEEE Transactions on Reliability, vol. 53, no. 4, pp. 487–498, 2004.
[83] J. Zheng, S. Latifi, 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.
[84] 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.