請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/36609
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 陳健輝 | |
dc.contributor.author | Guey-Yun Chang | en |
dc.contributor.author | 張貴雲 | zh_TW |
dc.date.accessioned | 2021-06-13T08:07:40Z | - |
dc.date.available | 2005-09-30 | |
dc.date.copyright | 2005-07-26 | |
dc.date.issued | 2005 | |
dc.date.submitted | 2005-07-21 | |
dc.identifier.citation | Bibliography
[1] S. B. Akers, D. Harel, and B. Krishnamurthy, “The star graph: an attractive alternative to the n-cube,” Proceedings of the International Conference on Parallel Processing, pp. 393-400, 1987. [2] S. B. Akers, D. Harel, and B. Krishnamurthy, “A group-theoretic model for symmetric interconnection networks,” IEEE Transaction 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. 85, 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] C. Berge, “Les probl`emes de coloration en th`eorie des graphes,” Publ. Inst. Statist. Univ. Paris, vol. 9, pp. 123-160, 1960. [10] 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. [11] L. Bhuyan and D. P. Agrawal, “Generalized hypercube and hyperbus structures for a computer network,” IEEE Transactions on Computers, vol. 33, no. 4, pp. 323-333, 1984. [12] 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. [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, “Fault diagnosis for sparsely interconnected multiprocessor systems,” Proceeding of IEEE Computer Society 19th International Sympsium on Fault-Tolerant Computing, pp. 62-69, 1989. [15] D. M. Blough, G. F. Sullivan, and G. M. Masson, “E cient diagnosis of multiprocessor systems under probabilistic models,” IEEE Transactions on Computers, vol. 41, pp. 1126-1136, 1992. [16] 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. [17] C. P. Chang, P. L. Lai, J. J. M. Tan, and L. H. Hsu, “Diagnosability of t-connected networks and product networks under the comparison diagnosis model” IEEE Transactions on Computers, vol. 53, pp. 1582-1590, 2004. [18] G. Y. Chang, G. J. Chang, and G. H. Chen, “Diagnosabilities of regular networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 53, pp. 1582-1590, 2005. [19] G. Y. Chang, G. H. Chen, and G. J. Chang, “(t, k)-diagnosis for matching composition networks,” IEEE Transactions on Computers,(minorly) revised. [20] G. Y. Chang, G. H. Chen, and G. J. Chang, “(t, k)-diagnosis for matching composition networks under the MM* model,” submitted to IEEE Transactions on Computers. [21] G. Y. Chang, “(t, k)-diagnosis for irregular systems under the PMC and MM* models,” manuscript. [22] G. Y. Chang, G. J. Chang, and G. H. Chen, ”Sequential diagnosis for irregular systems,” manuscript. [23] G. Y. Chang, “(t, k)-diagnosis for tori under the PMC and MM* models,” in preparation. [24] T. Chen, “Fault diagnosis and fault tolerance,” Springer-Verlag, 1992. [25] 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. [26] 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. [27] P. Cull and S. M. Larson, “The M¨obius cube,” IEEE Transactions on Computers, vol. 44,no. 5, pp. 647-659, 1995. [28] A. T. Dahbura, “System-level diagnosis: a perspective for the third decade,” Concurrent Computation: Algorithms, Arhcitectures, Technologies. New York: Plenum 1988. [29] A. T. Dahabura and G. M. Masson, “An O(n2.5) fault identification algorithm for diagnosable systems,” IEEE Transactions on Computers, vol. 33, no. 6, pp. 486-492, 1984. [30] A. T. Dahabura, G. M. Masson, and C. L. YANG, “Self-implicating structures for diagnosable systems,” IEEE Transactions on Computers, vol. 34, no. 8, pp. 718-723, 1985. [31] A. T. Dahabura and G. M. Masson, “Improved diagnosability algorithm,” IEEE Transactions on Computers, vol. 40, no. 2, pp. 143-153, 1991. [32] 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. [33] A. Das, K. Thulasiraman and V. K. Agarwal, “Diagnosis of t/(t + 1)-diagnosable systems,” SIAM Journal on Computing, vol. 23, no. 5, pp. 895-905, 1994. [34] K. Efe, “A variation on the hypercube with lower diameter,” IEEE Transactions on Computers, vol. 40, no. 11, pp. 1312-1316, 1991. [35] K. Efe, “The crossed cube architecture for parallel computing,” IEEE Transactions on Parallel and Distributed Systems, vol. 3, no. 5, pp. 513-524, 1992. [36] K. Efe, P. K. Blackwell, W. Slough and T. Shiau, “Topological properties of the crossed cube architecture,” Parallel Computing, vol. 20, pp. 1763-1775, 1994. [37] 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. [38] 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. [39] J. Fan, “Diagnosability of the M¨obius cubes,” IEEE Transactions on Parallel and Distributed Systems, vol. 9, no. 9, pp. 923-927, 1998. [40] J. Fan, “Diagnosability of crossed cubes under the comparison diagnosis model,” IEEE Transactions on Parallel and Distributed Systems, vol. 13, no. 7, pp. 687-692, 2002. [41] A. D. Friedman and L. Simoncini, “System-level fault diagnosis,” The Computer Journal, vol. 13, no. 3, pp. 47-53, 1980. [42] A. D. Friedman, “A new measure of digital system diagnosis,” Proceedings of IEEE Computer Society 5th International Sympsium on Fault-Tolerant Computing, pp. 167 170,1975. [43] H. Fujiwara and K. Kinoshita, “On the computational complexity of system diagnosis,” IEEE Transactions on Computers, vol. 27, no. 10, pp. 881-885, 1978. [44] D. Fussell and S. Rangarajan, “Probabilistic diagnosis of multiprocessor systems with arbitrary connectivity,” Proceeding of IEEE Computer Society 19th International Symposium of Fault-Tolerant Computing, pp. 560-565, 1989. [45] M. C. Golumbic, “Algorithmic Graph Theory and Perfect Graphs,” Academic Press, New York, 1980. [46] S. L. Hakimi and A. T. Amin, “Characterization of connection assignment of diagnosable systems,” IEEE Transactions on Computers, vol. 23, pp. 86-88, 1974. [47] S. Hart, “A note on the edges of the n-cube,” Discrete Mathmatics, vol. 14, pp. 157-163, 1976. [48] 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. [49] P. A. J. Hilbers, M. R. J. Koopman, J. L. A. van de Snepscheut, “The twisted cube,” Proceedings of Parallel Architecture and Language Europe, pp. 152-159, June 1987. [50] A. Kavianpour, “Sequential diagnosability of star graphs,” Computers Elect. Engng, 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 Reliability, vol. 41, pp. 26 37,1992. [53] 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. [54] S. Khanna and W. K. Fuchs, “A linear time algorithm for sequential diagnosis in hypercubes,” Journal of Parallel and Distributed Computing, vol. 26, pp. 38-53, 1995. [55] C. Kime, “System Diagnosis,” Fault-Tolerant Computing: Theory and Techniques, D.K. Pradhan, ed., vol. II, chapter 8. Englewood Cli s, N.J., Prentice Hall, 1986. [56] 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. [57] 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. [58] 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, Feb. 2005. [59] P. L. Lai, “On the diagnosis problems for multiprocessor systems,” Ph.D. dissertation, Department of of Computer Information Science, National Chiao Tung University, Hsinchu, Taiwan, 2004. [60] I. Leader, “Discrete isoperimetric inequalities,” Proc. Sympos. Appl. Math. Amer. Math. Society, Providence, RI, vol. 44, pp. 57-80 1991. [61] L. Lov´asz, “Normal hypergraphs and the perfect graph conjecture,” Discrete Mathematics, vol. 2, pp. 253-267, 1972. [62] L. Lov´asz, “A characterization of perfect graphs,” Journal of Combinatorial Theory Series B, vol. 13, pp. 95-98, 1972. [63] M. Malek, “A comparison connection assignment for diagnosable of multiprocessor systems,” Proeedings of the 7th Annual Symposium on Computer Architecture, pp. 31-36, 1980. [64] J. Maeng and M. Malek, “A comparison connection assignment for self-diagnosis of multiprocessor systems,” Digest of the International Sympsium on Fault Tolerant Computing, pp. 173-175, 1981. [65] S. N. Maheshwari and S. L. Hakimi, “On models for diagnosabile systems and probabilistic fault diagnosis,” IEEE Transactions on Computers, vol. 25, pp. 228-236, 1976. [66] S. Mallela and G. M. Masson, “Diagnosable systems for intermittent fault,” IEEE Transactions on Computers, vol. 27, pp. 460-470, 1978. [67] T. A. McKee and F. R. McMorris, “Topics in Intersection Graph Theory,” SIAM Monographs on DiscreteMathematics and Applications, Philadelphia, 1999. [68] G. G. L. Meyer, “A fault diagnosis algorithm for asymmetric modular architectures,” IEEE Transactions on Computers, vol. 30, pp. 81-83, 1981. [69] A. Pelc, “Undirected graph models for system-level fault diagnosis,” IEEE Transactions on Computers, vol. 40, pp. 1271-1276, 1991. [70] A. Pelc, “E cient distributed diagnosis in the presence of random faults,” Proceeding of IEEE Computer Society 23th International Sympsium on Fault-Tolerant Computing, vol. 16, pp. 462-469, 1993. [71] F. P. Preparata, G. Metze, and R. T. Chien, “On the connection assignment problem of diagnosable systems,” IEEE Transactions on Electronic Computers, vol. 16, pp. 848 854,1967. [72] 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. [73] S. Rangarajan and D. Fussell, “Probabilistic diagnosis algorithms tailored to system topology,” Proceeding of IEEE Computer Society 21th International Sympsium on Fault Tolerant Computing, pp. 230-237, 1991. [74] J. D. Russell and C. R. Kime, “System fault diagnosis: masking, exposure, and diag nosability without repair,” IEEE Transactions on Computers, vol. C-24, pp. 1156-1161, 1975. [75] Y. Saad and M. H. Schultz, “Topological properties of hypercubes,” IEEE Transactions on Computers, vol. 37, no 7, pp. 867-872, 1988. [76] P. Santi and S Chessa, “Reducing the number of Sequential diagnosis iteration in hypercubes,” IEEE Transactions on Computers, vol. 43, no. 1, pp. 89-92, 2004. [77] E. Scheinerman, “Almost sure fault tolerance in random graphs,” SIAM Journal on Computing, vol. 16, pp. 1124-1134, 1987. [78] 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. [79] A. K. Somani, V. K. Agarwal, and D. Avis, “A generalized theory for system level diagnosis,” IEEE Transactions on Computers, vol. 36, no. 5, pp. 538-546, 1987. [80] A. K. Somani, “System level diagnosis: a review,” Technical report, Dependable Com puting Laboratory, Iowa State University, 1997. [81] 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. [82] 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. [83] X. Song, “A wafer fault diagnosis scheme,” International Journal of Electronics, vol. 87,no. 12, pp. 1453-1459, 2000. [84] G. Sullivan, “A polynomial time algorithm for fault diagnosability,” Proeedings of the 11th Annual Symposium on Computer Architecture, pp. 148-156, 1984. [85] G. Sullivan, “An O(t3 + |E |) fault identification algorithm for diagnosable systems,” IEEE Transactions on Computers, vol. 37, pp. 388-397, 1988. [86] N. E. Tzeng and S. Wei, “Enhanced hypercubes,” IEEE Transactions on Computers, vol. 41, no. 11, pp. 1386-1396, 1992. [87] D. Wang, “Diagnosability of enhanced hypercubes,” IEEE Transactions on Computers, vol. 43, no. 9, pp. 1054-1061, 1994. [88] 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. [89] D. B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001. [90] J. Xu and S.Z. Huang, “Sequentially t-diagnosable systems: A characterization and its application,” IEEE Transactions on Computers, vol. 44, no. 2, pp. 340-345, 1995. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/36609 | - |
dc.description.abstract | 摘要
系統偵錯(system-level diagnosis)是根據系統中各個處理機相互測試的結果,推導出系統中錯誤處理機程序。系統偵錯原本應用在多處理機系統。最近,晶圓的測試也開始使用系統偵錯的技術。系統偵錯包含三個重要的研究主題:特性描述(characterization)、可偵錯度(diagnosabilities)計算、偵錯演算法設計。本論文主要考慮在兩個不同偵錯模式(PMC model 和MM* model)和兩類不同的偵錯策略(第一類偵錯策略包括單步偵錯(one-step diagnosis)、循序偵錯(sequential diagnosis)和 (t, k)-偵錯;第二類偵錯策略包括精確偵錯(precise diagnosis)和非精確偵錯(pessimistic diagnosis))下研究可偵錯度計算和偵錯演算法設計。 首先,本論文考慮單步偵錯策略。我們在兩個不同偵錯模式和第二類的兩種不同偵錯策略下探討規則多處理機系統(regular multiprocessor systems)之可偵錯度問題。本論文中推導出四個定理。根據這四個定理,可以得到許多常見以及未見但實用的規則多處理機系統的可偵錯度。其中,hypercubes、enhanced hypercubes、twisted cubes、crossed cubes、Möbius cubes、cube-connected cycles、tori和star graphs。 接下來,本論文考慮循序偵錯策略。我們推導出有用的循序偵錯系統拓樸性質。根據這些拓樸性質,設計出弦圖(chordal graphs)在兩個不同偵錯模式下的偵錯演算法。 最後,本論文考慮(t, k)-偵錯策略。我們成功地為matching composition networks(由賴寶蓮等提出)和非規則多處理機系統(irregular multiprocessor systems)設計出(t, k)-偵錯演算法。同時,我們也計算出一個包含N個多處理機之matching composition networks的(t, k)-可偵錯度下限(lower bound):在 PMC 模式和MM* 模式下都是 (Ω(Nloglog N / log N), log N)。當 k=1時,(Ω(Nloglog N / log N), 1) 即是matching composition networks的循序可偵錯度的下限。根據這些結果,我們可以得到hypercubes、twisted cubes、crossed cubes、Möbius cubes和grids的(t, k)-可偵錯度下限和循序可偵錯度的下限以及(t, k)-偵錯演算法和循序偵錯演算法。 | zh_TW |
dc.description.abstract | Abstract
System-level diagnosis is a process of identifying faulty processors in a system by conducting tests on various processors and interpreting the test results. A natural application of system-level diagnosis is the diagnosis of multiprocessor systems. Recently, it has been considered with renewed interest in the wafer-scale VLSI testing. There are three important issues in system-level diagnosis: characterization, diagnosiabilities and designing diagnosis algorithms. In the dissertation, we consider diagnosabilities and designing diagnosis algorithms for several classes of systems under two diagnosis models (the PMC model and the MM* model) and two classes of diagnosis strategies: one class includes one-step diagnosis, sequential diagnosis and (t,k)-diagnosis; the other includes precise diagnosis and pessimistic diagnosis. Under one-step diagnosis strategy, one-step diagnosabilities of regular multiprocessor systems for two diagnosis models (i.e., the PMC and comparison models) and two diagnosis strategies (i.e., the precise and pessimistic diagnosis strategies) were considered. Many well-known and unknown but potentially useful multiprocessor systems were computed. These include hypercubes, enhanced hypercubes, twisted cubes, crossed cubes, Möbius cubes, cube-connected cycles, tori, star graphs, and many others. Some of these are established in several previous papers, and many are new. Our results were obtained as a consequence of four sufficient conditions. The four sufficient conditions can derive diagnosabilities for a class of regular systems. Under sequential diagnosis strategy, topological properties for sequentially diagnosable systems under the PMC model and the MM* model were shown. Further, an efficient sequential diagnosis algorithms for chordal networks under the PMC model and the MM* model were also given. Under (t,k)-diagnosis strategy, (t,k)-diagnosis algorithms for matching composition networks introduced by Lai { et al.}, and irregular systems under the PMC model and MM* model were proposed. The diagnosabilities were also computed as follows: a matching composition network with N vertices is (Ω(Nloglog N log N}), log N)-diagnosable under the PMC model and (Ω(Nloglog N log N}), log N)-diagnosable under the MM* model, where N > 2^5. When k=1, a lower bound of Ω(Nloglog N log N}) is derived for the sequential diagnosability of matching composition networks. Applying our result, a lower bound of the (t,k)-diagnosabilities of hypercubes, crossed cubes,twisted cubes, Möbius cubes and grids under the PMC model and the MM* model can all be obtained. And, a lower bound of the sequential diagnosabilities of these interconnection networks can be obtained, also. | en |
dc.description.provenance | Made available in DSpace on 2021-06-13T08:07:40Z (GMT). No. of bitstreams: 1 ntu-94-D89922006-1.pdf: 684525 bytes, checksum: a005e86322438ed7f300b1dbd03e1e33 (MD5) Previous issue date: 2005 | en |
dc.description.tableofcontents | Contents
1 Introduction 1 1.1 Diagnosis models 4 1.2 Diagnosis strategies . . . 5 1.2.1 One-step diagnosis 5 1.2.2 Sequential diagnosis 6 1.2.3 (t, k)-diagnosis 6 1.3 Previous work . . . 7 1.3.1 One-step diagnosis 7 1.3.2 Sequential diagnosis 8 1.3.3 (t, k)-diagnosis 8 1.4 Preliminaries 9 1.5 Thesis organization and contribution 10 2 One-step diagnosabilities of regular networks 13 2.1 Precise diagnosis 13 2.1.1 The PMC model 15 2.1.2 The MM* model 15 2.2 Pessimistic diagnosis 19 2.2.1 The PMC model 22 2.2.2 The MM* model 23 2.3 Applications . . . 26 3 Sequential diagnosis algorithms for chordal graphs 31 3.1 Precise diagnosis under the PMC model 31 3.1.1 A diagnosis algorithms 34 3.2 Precise diagnosis under the MM* model 36 3.2.1 A diagnosis algorithm 48 4 (t, k)-diagnosis of matching composition networks under PMC model 51 4.1 A diagnosis algorithm . . . 51 4.2 Diagnosabilities 53 5 (t, k)-diagnosis of matching composition networks under MM* model 61 5.1 A diagnosis algorithm . . . 61 5.2 Diagnosabilities 67 6 (t, k)-diagnosis for irregular systems 73 6.1 An identifiable fault-free aggregate 75 6.2 A diagnosis algorithm . . . 78 6.3 Diagnosabilities 80 6.4 Application 81 7 Discussion and conclusion 85 7.1 Summary 85 7.2 Further research 86 List of Tables 1.1 Previous results with respect to one-step diagnosabilities 9 1.2 Previous work on diagnosabilities and diagnosis algorithms 11 1.3 Our research on diagnosis problems 12 2.1 Properties of multiprocessor systems 29 2.2 Diagnosabilities of multiprocessor systems 29 6.1 The value of 83 7.1 Our results on one-step diagnosabilities . . .86 7.2 Some further research topics for system-level diagnosis 87 List of Figures 2.1 Relation among the sets in the proof of Lemma 2.1.1 15 2.2 The graph G8. . .16 2.3 The graph Gn,n. . .16 2.4 |F1 F2| £ 2 and |F2 F1| £ 2 imply s £ 4. . .18 2.5 G is isomorphic to G8. 19 2.6 The graph G5, where zij stands for z{i,j}. 20 2.7 Relation among N (w1), N (w2), N ({p1, p2}) and F3 25 2.8 Relation among N (u), N (F3) Ç F1 Ç F2 and F4 for Case 3. 26 3.1 Cs in Gp(s). . .34 3.2 A cycle C in Gm(s). 40 3.3 (wi, wj ) Î E (G) and {Xi, Xi+1} Ç {Xj , Xj+1} = Æ. . 42 3.4 (wi, wj ) Î E (G) and Xj = Xi+1. . .42 3.5 (wi, xk ) Î E (G). 42 3.6 C and P (X, Y ). 43 3.7 House. . . 43 3.8 H1 and H2. 44 3.9 House and {{X2, X3}, {X3, X4}, {X4, X5}} Ç E (G) = Æ 44 3.10 Adjacency between Xp, Xq and Xi if Y Î Ns0 (Xi). . 47 3.11 Adjacency between Xp, Xq , Xi and Xj 47 4.1 Proof of Lemma 4.2.5. 58 5.1 A fault-free aggregate. 63 6.1 A fault-free aggregate 76 | |
dc.language.iso | en | |
dc.title | 多處理機系統之系統偵錯 | zh_TW |
dc.title | system-level diagnosis of multiprocessor systems | en |
dc.type | Thesis | |
dc.date.schoolyear | 93-2 | |
dc.description.degree | 博士 | |
dc.contributor.coadvisor | 張鎮華 | |
dc.contributor.oralexamcommittee | 張進福,譚建民,徐力行,王有禮,劉邦鋒 | |
dc.subject.keyword | 多處理機系統,系統偵錯,超方體,容錯, | zh_TW |
dc.subject.keyword | diagnosis,multiprocessor systems,hypercubes, PMC model, | en |
dc.relation.page | 97 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2005-07-21 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-94-1.pdf 目前未授權公開取用 | 668.48 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。