系統偵錯（system-level diagnosis）是根據系統中各個處理機相互測試的結果，推導出系統中錯誤處理機程序。系統偵錯應用在多處理機系統，包含五個重要的研究主題：偵測模式（diagnosis model）、偵錯策略（diagnosis strategy）、偵錯演算法（diagnosis algorithm）、故障分布模式（fault model）和可偵錯度（diagnosability）計算。本論文中，我們將重點關注在 (t,k)-偵錯策略及演算法和故障隨機分布時，已知的多處理機系統在PMC和MM*兩種偵測模式下的可偵錯度計算。
　　一個多處理器系統包含許多的處理器，假設故障的處理器個數有t個，我們將採用(t,k)-偵錯來進行系統偵錯。(t,k)-偵錯是一個多次偵錯的策略，表示每一次進行偵錯至少能夠辨識出k個有故障的處理機並且以正常的處理機更換取代。本篇論文探討故障的節點是到處都可能發生，不受任何限制。我們統一一個方法來計算各種多處理機系统的(t,k)-可偵錯度，包括超立方體（Hypercubes）、交叉立方體（Crossed Cubes）、雙扭立方體（Twisted Cubes）、局部雙扭立方體（Locally Twisted Cubes）、多重雙扭立方體（Multiply Twisted Cubes）、廣義雙扭立方體（Generalized Twisted Cubes）、遞迴環形（Recursive Circulants）、莫氏立方體（Möbius Cubes）、M立方體（Mcubes）、星圖（Star Graphs）、氣泡排序圖（Bubble-Sort Graphs）、煎餅圖（Pancake Graphs）和燒煎餅圖（Burnt Pancake Graphs）。觀察上面13種多處理機系统的共同特性，我們將提出一種新的網路拓樸結構圖Component-Composition Graphs (CCG)。由於CCG包含了13種多處理機系统，所以當我們推導出CCG的(t,k)-可偵錯度之後，這13種多處理機系统的(t,k)-可偵錯度都間接著被我們計算出來。

　　System-level diagnosis is a process of identifying faulty processors in a system by conducting tests on various processors and interpreting the test results. The application of system-level diagnosis is the diagnosis of multiprocessor systems. There are five important issues in system-level diagnosis: diagnosis model, diagnosis strategy, diagnosis algorithm, fault model and diagnosability. We focus the (t,k)-diagnosis strategy, (t,k)-diagnosis algorithm, random fault model and (t,k)-diagnosis diagnosability for some multiprocessor systems under the PMC and MM* models.
　　(t,k)-diagnosis, which is a generalization of sequential diagnosis, requires at least k faulty processors identified and replaced in each iteration provided there are at most t faulty processors, where t >= k. In this thesis, faulty nodes of multiprocessor systems may occur everywhere without any restriction. We propose a unified approach to compute the (t,k)-diagnosability for numerous multiprocessor systems, including hypercubes, crossed cubes, twisted cubes, locally twisted cubes, multiply twisted cubes, generalized twisted cubes, recursive circulants, Möbius cubes, Mcubes, star graphs, bubble-sort graphs, pancake graphs, and burnt pancake graphs. The key concept of our approach is to sketch the common graph properties of the above multiprocessor systems and demonstrate that their underlying topologies have a common super class of graphs, called component-composition graphs. We then show that the m-dimensional component-composition graph G for m >= 4 is a lower bound of the (t,k)-diagnosability. Based on this result, the (t,k)-diagnosability of the referred multiprocessor systems can be efficiently computed.

[1] S. B. Akers, D. Horel, and B. Krishnamurthy, “The star graph: an attractive alternative to the n-cube,” in Proceedings of the International Conference on Parallel Processing, pp. 393-400, 1987.
[2] S. B. Akers and B. krishnamurthy, “A group-theoretic model for symmetric interconnection networks,” IEEE Transactions on Computers, vol. 38, no. 4, pp. 555-566, 1989.
[3] F. J. Allan, T. Kameda, and S. Toida, “Approach to the diagnosability analysis of a system,” IEEE Transaction on Computers, vol. 25, pp. 1040-1042, 1975.
[4] T. Araki and Y. Shibata, “Diagnosability of networks by the cartesian product,” IEICE Transactions on Fundamentals of Electronics Communications and Computer Science, vol. 83, no. 3, pp. 465-470, 2000.
[5] T. Araki and Y. Shibata, “Diagnosability of butterfly networks under the comparison approach,” IEICE Transactions on Fundamentals of Electronics Communications and Computer Science, vol. E85-A, no. 5, pp. 1152-1160, 2002.
[6] T. Araki and Y. Shibata, “(t, k)-diagnosable system: a generalization of the PMC models,” IEEE Transactions on Computers, vol. 52, no. 7, pp. 971-975, 2003.
[7] J. R. Armstrong and F. G. Gray, “Fault diagnosis in a boolean n-cube array of microprocessors," IEEE Transactions on Computers, vol. 30, no. 8, pp. 587-590, 1981.
[8] F. Barsi, F. Grandoni, and P. Maestrini, “A theory of diagnosability in digital systems,” IEEE Transactions on Computers, vol. 25, pp. 585-593, 1976.
[9] P. Berman and A. Pelc, “Distributed probabilistic fault diagnosis for multiprocessor systems,” Proceeding of IEEE Computer Society 20th International Symposium of Fault-Tolerant Computing, pp. 340-346, 1990.
[10] L. Bhuyan and D. P. Agrawal, “Generalized hypercubes and hyperbus structure for a computer network,” IEEE Transactions on Computers, vol. 33, pp. 323-333, 1984.
[11] D. M. Blough, G. F. Sullivan, and G. M. Masson, “Almost certain diagnosis for intermittently faulty systems,” Proceeding of IEEE CS 18th International Sympsium on Fault-Tolerant Computing, pp. 260-265, 1988.
[12] D. M. Blough, G. F. Sullivan, and G. M. Masson, “Fault diagnosis for sparsely interconnected multiprocessor systems,” Proceeding of IEEE Computer Society 19th International Sympsium on Fault-Tolerant Computing, pp. 62-69, 1989.
[13] D. M. Blough and A. Pelc, “Reliable diagnosis and repair in constant-degree multiprocessor systems,” Proceeding of IEEE Computer Society 20th International Sympsium on Fault-Tolerant Computing, pp. 316-323, 1990.
[14] D. M. Blough, G. F. Sullivan, and G. M. Masson, “Efficient diagnosis of multiprocessor systems under probabilistic models,” IEEE Transactions on Computers, vol. 41, pp. 1126-1136, 1992.
[15] D. M. Blough, G. F. Sullivan, and G. M. Masson, “Intermittent fault diagnosis in multiprocessor system,” IEEE Transactions on Computers, vol. 41, pp. 1430-1441, 1992.
[16] G. Y. Chang, G. J. Chang, and G. H. Chen, “Diagnosabilities of regular networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 4, pp. 314-322, 2005.
[17] G. Y. Chang and G. H. Chen, “(t, k)-diagnosability of multiprocessor systems with applications to grids and tori,” SIAM Journal on Computing, vol. 37, no. 4, pp. 1280-1298, 2007.
[18] G. Y. Chang, G. H. Chen, and G. J. Chang, “(t, k)-diagnosis for matching composition networks,” IEEE Transactions on Computers, vol. 55, no. 1, pp. 88-92, 2006.
[19] G. Y. Chang, G. H. Chen, and G. J. Chang, “(t, k)-diagnosis for matching composition networks under the MM* model," IEEE Transactions on Computers, vol. 56, no. 1, pp. 73-79, 2007.
[20] F. B. Chedid, “On the generalized twisted cube,” Information Processing Letters, vol. 55, no. 1, pp. 49-52, 1995.
[21] C. A. Chen and S. Y. Hsieh, “t/t-Diagnosability of regular graphs under the PMC model,” ACM Transactions on Design Automation of Electronic Systems (TODAES), vol. 18, no. 2, article no. 20, 2013.
[22] K. Y. Chwa and S. L. Hakimi, “On fault identification in diagnosable systems,” IEEE Transactions on Computers, vol. 30, no. 6, pp. 414-422, 1981.
[23] K. Y. Chwa and S. L. Hakimi, “Schemes for fault tolerant computing: a comparison of modularly redundant and t-diagnosable systems,” Information and Control, vol. 49, pp. 212-238, 1981.
[24] P. Cull and S. M. Larson, “The Möbius cubes,” IEEE Transactions on Computers, vol. 44, no. 5, pp.647-659, 1995.
[25] A. T. Dahabura and G. M. Masson, “An o(n2.5) fault identification algorithm for diagnosable systems,” IEEE Transactions on Computers, vol. C-33, no. 6, pp. 486-492, 1984.
[26] A. T. Dahbura, “System-level diagnosis: a perspective for the third decade,” Concurrent Computation: Algorithms, Arhcitectures, Technologies. New York: Plenum 1988.
[27] A. T. Dahabura and G. M. Masson, “Improved diagnosability algorithm,” IEEE Transactions on Computers, vol. 40, no. 2, pp. 143-153, 1991.
[28] A. Das, K. Thulasiraman and V. K. Agarwal and K. B. Lakshmanan, “Multiprocessor fault diagnosis under local constraints,” IEEE Transactions on Computers, vol. 42, no. 8, pp. 984-988, 1993.
[29] K. Efe, “A variation on the hypercube with lower diameter,” IEEE Transactions on Computers, vol. 40, no. 11, pp. 1312-1316, 1991.
[30] K. Efe, “The crossed cube architecture for parallel computation,” IEEE Transactions on Parallel and Distributed Systems, vol. 3, no. 5, pp. 513-524, 1992.
[31] A.H. Esfahanian, “Generalized measures of fault tolerance with application to N-cube networks,” IEEE Transactions on Computers, vol. 38, no. 11, pp. 1586-1591, 1989.
[32] A. H. Esfahanian, L. M. Ni, and B. E. Sagan, “The twisted n-cube with application to multiprocessing,” IEEE Transactions on Computers, vol. 40, no. 1, pp. 88-93, 1991.
[33] J. Fan, “Diagnosability of the möbius cubes,” IEEE Transactions on Parallel and Distributed Systems, vol. 9, no. 9, pp. 923-928, 1998.
[34] J. Fan, “Diagnosability of crossed cubes under the comparison diagnosis model,” IEEE Transactions on Parallel and Distributed Systems, vol. 13, no. 10, pp. 1099-1104, 2002.
[35] J. Fan and X. Lin, “The t/k-diagnosability of the BC graphs," IEEE Transactions on Computers, vol. 54, no. 2, pp. 176-184, 2005.
[36] J. Fan, X. Lin, and X. Jia, “Optimal Path Embedding in Crossed Cubes,” IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 12, pp.1190-1200, 2005.
[37] A. D. Friedman, “A new measure of digital system diagnosis,” in Digest 1975 International Symposium on Fault-Tolerant Computing, pp. 167-170, 1975
[38] A. D. Friedman and L. Simoncini, “System-level fault diagnosis,” Computer, vol. 13, no. 3, pp. 47-53, 1980.
[39] H. Fujiwara and K. Kinoshita, “On the computational complexity of system diagnosis,” IEEE Transactions on Computers, vol. C-27, no. 10, pp. 881-885, 1978.
[40] S. L. Hakimi and A. T. Amin, “On the computational complexity of system diagnosis,” IEEE Transactions on Computers, vol. 23, no. 1, pp. 86-88, 1974.
[41] P. A. J. Hilbers, M. R. J. Koopman, and J. L. A. van de Snepscheut, “The twisted cube,” in Proceedings of the Conference on Parallel Architectures and Languages Europe, Volume I: Parallel Architectures, pp. 152-159, 1987.
[42] S. H. Hosseini, J. G. Kuhl and S. M. Reddy, “Diagnosis algorithm for distributed computing systems,” IEEE Transactions on Computers, vol. 33, pp. 223-233, 1984.
[43] S. Y. Hsieh and Y. S. Chen, “Strongly diagnosable product networks under the comparison diagnosis model,” IEEE Transactions on Computers, vol. 57, no. 6, pp. 721-731, 2008.
[44] 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.
[45] G. H. Hsu, C. F. Chiang, L. M. Shih, L. H. Hsu, and J.J.M. Tan, “Conditional diagnosability of hypercubes under the comparison diagnosis model,” Journal of Systems Architecture, vol. 55, no. 2, pp. 140-146, 2009.
[46] J. S. Jwo, S. Lakshmivarahan, and S. K. Dhall, “A new class of interconnection networks based on the alternating group,” Networks, vol. 23, pp. 315-326, 1993.
[47] K. Kaneko and N. Sawada, “An algorithm for node-to-set disjoint paths problem in burnt pancake graphs,” IEICE Transactions on Information and Systems, vol. E86VD, no. 12, pp. 2588-2594, 2003.
[48] K. Kaneko and N. Sawada, “An algorithm for node-to-node disjoint paths problem in burnt pancake graphs,” IEICE Transactions on Information and Systems, vol. E90VD, no. 1, pp. 306-313, 2007.
[49] A. Kavianpour and A. D. Friedman, “Efficient design of easily diagnosable systems,” in Proceedings of the 3rd USA-Japan Computer Conference, pp. 251-257, 1978.
[50] A. Kavianpour, “Sequential diagnosability of star graphs,” Computers & Electrical Engineering, vol. 22, no. 1, pp. 37-44, 1996.
[51] A. Kavianpour and K. H. Kim, “Diagnosabilities of hypercubes under the pessimistic one-step diagnosis strategy,” IEEE Transactions on Computers, vol. 40, no. 2, pp. 232-237, 1991.
[52] A. Kavianpour and K. H. Kim, “A comparative evaluation of four basic system-level diagnosis strategies for hypercubes,” IEEE Transactions on Computers, vol. 41, no. 1, pp. 26-37, 1992.
[53] 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.
[54] S. Khanna and W. K. Fuchs, “A graph partitioning approach to sequential diagnosis,” IEEE Transactions on Computers, vol. 46, no. 1, pp. 39-47, 1997.
[55] J. G. Kuhl and S. M. Reddy, “Fault diagnosis in fully distributed systems,” Proceedings of IEEE Computer Society 11th International Sympsium on Fault-Tolerant Computing, pp. 100-105, 1981.
[56] 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 Transactions on Computers, vol. 53, no. 8, pp. 1064-1069, 2004.
[57] P. L. Lai, J. J. M. Tan, C. P. Chang, and L. H. Hsu, “Conditional diagnosability measures for large multiprocessor systems,” IEEE Transactions on Computers, vol. 54, no. 2, pp. 165-175, 2005.
[58] S. Lakshmivarahan, J. S. Jwo, and S. K. Dhall, “Symmetry in interconnection networks based on cayley graphs of permutation groups: a survey,” Parallel Computing, vol. 19, no. 4, pp. 361-407, 1993.
[59] F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, San Mateo, CA, 1992.
[60] C. K. Lin, J. J. M. Tan, L. H. Hsu, E. Cheng, and L. Lipták, “Conditional diagnosability of cayley graphs generated by transposition trees under the comparison diagnosis model,” Journal of Interconnection Networks, vol. 9, no. 1 & 2, pp. 83-97, 2008.
[61] J. Maeng and M. Malek, “A comparison connection assignment for self-diagnosis of multiprocessor systems,” in: Proceeding 11th International Symposium on Fault Tolerant Computing, pp. 173-175, 1981.
[62] M. Malek, “A comparison connection assignment for diagnosable of multiprocessor systems,” in: Proceedings of the 7th International Symposium on Computer Architecture, pp. 31-36, 1980.
[63] S. Mallela and G. M. Masson, “Diagnosable systems for intermittent fault,” IEEE Transactions on Computers, vol. 27, pp. 460-470, 1978.
[64] G. G. L. Meyer, “A fault diagnosis algorithm for asymmetric modular architectures,” IEEE Transactions on Computers, vol. 30, pp. 81-83, 1981.
[65] J. H. Park and K. Y. Chwa, “Recursive circulants and their embeddings among hypercubes,” Theoretical Computer Science, vol. 244, pp. 35-62, 2000.
[66] J. H. Park, H. C. Kim, and H. S. Lim, “Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements,” IEEE Transactions on Parallel and Distributed Systems, vol. 17, no. 3, pp. 227-240, 2006.
[67] J. H. Park, H. S. Lim, and H. C. Kim, “Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements,” Theortical Computer Science, vol. 377, pp. 170-180, 2007.
[68] A. Pelc, “Undirected graph models for system-level fault diagnosis,” IEEE Transactions on Computers, vol. 40, pp. 1271-1276, 1991.
[69] F. P. Preparata, G. Metze, and R. T. Chien, “On the connection assignment problem of diagnosable systems,” IEEE Transactions on Electronic Computers, Vol. EC-16, No. 6, pp. 848-854, 1967.
[70] F. P. Preparata and J. Vuillemin, “The cube-connected cycles: a versatile network for parallel computation,” Communications of the ACM, vol. 24, pp. 300-309, 1981.
[71] J. D. Russell and C. R. Kime, “System fault diagnosis: masking, exposure, and diagnosability without repair,” IEEE Transactions on Computers, vol. C-24, pp. 1156-1161, 1975.
[72] Y. Saad and M. H. Schultz, “Topological properties of hypercubes,” IEEE Transactions on Computers, vol. 37, no 7, pp. 867-872, 1988.
[73] A. Sengupta and A. T. Danbura, “On self-diagnosable multiprocessor systems: diagnosis by the comparison approach,” IEEE Transactions on Computers, vol. 41, no. 11, pp. 1386-1396, 1992.
[74] N. K. Singhvi and K. Ghose, “The Mcube: a symmetrical cube based network with twisted links,” in: Proceedings of the 9th IEEE International Parallel Processing Symposium IPPS 1995, pp. 11-16, 1995.
[75] A. K. Somani, V. K. Agarwal, and D. Avis, “A generalized theory for system level diagnosis,” IEEE Transactions on Computers, vol. C-36, no. 5, pp. 538-546, 1987.
[76] A. K. Somani and V. K. Agarwal, “Distributed syndrome decoding for regular interconnected structure,” Proceeding of IEEE Computer Society 19th International Sympsium on Fault-Tolerant Computing, pp. 70-77, 1989.
[77] A. K. Somani, V. K. Agarwal and D. Avis, “On the complexity of single fault set diagnosability and diagnosis problems,” IEEE Transactions on Computers, vol. 38, pp. 195-201, 1989.
[78] A. K. Somani and O. Peleg, “On diagnosability of large fault sets in regular topology-based computer systems,” IEEE Transactions on Computers, vol. 45, no. 8, pp. 892-902, 1996.
[79] X. Song, “A wafer fault diagnosis scheme,” International Journal of Electronics, vol. 87, no. 12, pp. 1453-1459, 2000.
[80] Y. Suzuki and K. Kaneko, “An algorithm for node-disjoint paths in pancake graphs,” IEICE Transactions on Information and Systems, vol. E86-D, no. 3, pp. 610-615, 2003.
[81] G. Sullivan, “A polynomial time algorithm for fault diagnosability,” Proeedings of the 11th Annual Symposium on Computer Architecture, pp. 148-156, 1984.
[82] G. Sullivan, “An O(t3+|E|) fault identification algorithm for diagnosable systems,” IEEE Transactions on Computers, vol. 37, pp. 388-397, 1988.
[83] N. E. Tzeng and S.Wei, “Enhanced hypercubes,” IEEE Transactions on Computers, vol. 41, no. 11, pp. 1386-1396, 1992.
[84] A. S. Vaidya, P. S. N. Rao, and S. R. Shankar, “A class of hypercube-like networks,” in: Proc. 5th Symp. on Parallel and Distributed Processing, pp. 800-803, 1993.
[85] D.Wang, “Diagnosability of enhanced hypercubes,” IEEE Transactions on Computers, vol. 43, no. 9, pp. 1054-1061, 1994.
[86] D. Wang, “Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model,” IEEE Transactions on Computers, vol. 48, no. 12, pp. 1369-1374, 1999.
[87] J. Xu and S. ze Huang, “Sequentially t-diagnosable system: a characterization and its applications,” IEEE Transactions on Computers, vol. 44, no. 2, pp. 340-345, 1995.
[88] M. Xu, K. Thulasiraman, and X. D. Hu, “Conditional Diagnosability of Matching Composition Networks Under the PMC Model,” IEEE Transactions on Circuits and Systems II, vol. 56, no. 11, pp. 875-879, 2009.
[89] T. Yamada, T. Ohtsukab, A. Watanabe, and S. Ueno, “On sequential diagnosis of multiprocessor systems,” Discrete Applied Mathematics, vol. 146, no. 3, pp. 311-342, 2005.
[90] C. L. Yang, G. M. Masson and R. A. Leonetti, “On fault isolation and identification in t/t-diagnosable systems,” IEEE Transactions on Computers, vol. C-35, no. 7, pp. 639-643, 1986.
[91] X. Yang, “A linear time fault diagnosis algorithm for hypercube multiprocessors under the MM* comparison model,” in: Proceedings of the 12th Asian Test Symposium, pp. 50-57, 2003.
[92] X. Yang, D. J. Evans, and G. M. Megson, “The locally twisted cubes,” International Journal of Computer Mathematics, vol. 82, no. 4, pp. 401-413, 2005.
[93] J. Zheng, S. Latifi, E. Regentova, K. Luo, and X. Wu, “Diagnosability of star graphs under the comparison diagnosis model,” Information Processing Letters, vol. 93, no. 1, pp. 29-36, 2005.
[94] S. Zhou, “The Conditional Diagnosability of Möbius cubes under the Comparison Model,” Proceedings of the 2009 IEEE International Conference on Information and Automation, pp. 96-100, 2009.
[95] S. Zhou, “The Conditional Diagnosability of Locally Twisted Cubes,” Proceedings of 2009 4th International Conference on Computer Science and Education, pp. 221-226, 2009.
[96] S. Zhou, “The Conditional Diagnosability of Twisted cubes under the Comparison Model,” 2009 IEEE International Symposium on Parallel and Distributed Processing with Applications, pp. 696-701, 2009.
[97] Q. Zhu, “On conditional diagnosability and reliability of the BC networks,” The Journal of Supercomputing, vol. 45, no. 2, pp. 173-184, 2008.
[98] Q. Zhu, S.Y. Liu, and M. Xu, “On conditional diagnosability of the folded hypercubes,” Information Sciences, vol. 178, no. 4, pp. 1069-1077, 2008.