臺灣博碩士論文加值系統

在分散式大型主機上，連結網路一直扮演很重要的角色；連結網路上面有許多重要的問題被大家討論著，而診斷的問題就是其中之一，在本論文中，我們討論n維度的雙扭立方體動態診斷的問題，並在有最多壞n個點的前提下，提出一個方法在三回合內診斷完成。在前兩回合中，每一點測試一個鄰居，並接受一個鄰居測試，依據這些測試結果，再針對未能決定狀態的點，進行第三回合測試數數。由於動態診斷最至少要三回合，所以我們的方法在回合數的設計上為最佳數。2005年Okashita、Araki和Shibata提出一個四回合動態診斷方法，另外他們的測試次數也明顯比我們的方法多。

An interconnection network plays a critical role of a multi-computer. The diagnosis problem is one of the important issues in interconnection networks. In this paper, We discuss a problem of adaptive diagnosis in the n-dimensional twisted cubes, and propose a method to solve the problem in at most three test rounds, provided that the number of faulty vertices is at most n for n ≥ 5. Each vertex is tested by another once in the first two rounds. However, some vertices could not be identified to be fault-free or faulty according to the test results. Then, the unidentified vertices will be tested once again in the third round. The method is optimal for at most three rounds since the adaptive diagnosis needs at least three rounds to complete.

書名頁
授權書
論文口試委員審定書
中文摘要
英文摘要
誌謝
目錄
表目錄
圖目錄
1 緒論
1.1 動機
1.2 先前相關研究及結果
1.3 論文架構
2 文獻探討
2.1 基本定義及名詞
2.2 診斷模型與診斷分類
3 雙扭立方體結構與超立方體結構之間的建構關係
3.1 雙扭立方體之結構
3.2 雙扭立方體與超立方體結構之間的建構關係
4 動態診斷之架構4.1 基礎測試
4.2 進階測試一
4.3 TQ 5
4.4 TQ 7
4.5 進階測試二
5 研究比較與實作
5.1 研究比較
5.2 實作
6 結論
參考文獻

[1] T. Araki, “ Optimal adaptive fault diagnosis of cubic Hamiltonian graphs ” , Proceedings of the 7th International Symposium on Parallel Architectures, Al-gorithms and Networks, pp. 162-167, May 2004.
[2] J. A. Bondy and U. S. R. Murty, “ Graph theory with applications ” , North Holland, New York, 1980.
[3] P. M. Blecher, “ On a logical problem ” , 1 Discrete Mathematics, vol. 43, pp. 107 – 110, 1983.
[4] S. Fujita and T. Araki, “ Three-round adaptive diagnosis in binary n-cubes ” , Lecture Notes in Computer Science, vol. 3341, pp. 442-451, Dec 2004.
[5] C. Feng, L. N. Bhuyan, and F. Lombardi, “ Adaptive system-level diagnosis for Hypercube multiprocessors ” , 1 IEEE Transactions on Computers, vol.45, no.10, pp.1157 – 1170, Oct. 1996.
[6] S. L. Hakimi and A. T. Amin, “ Characterization of connection assignment of diagnosable systems ” , IEEE Transactions on Computers, vol. C-23(1), 86-88, 1974.
[7] F. Harary, J. P. Hayes, and H. J. Wu. “ A survey of the theory of the Hypercube graphs ” , Computer Mathematics with Applications, vol. 15, No. 4, pp. 277-289, 1988.
[8] P. A. J. Hilbers and M. R. J. Koopman and J. L. A. van de Snepscheut, “ The twisted cube ” , Lecture Notes in Computer Science, vol. 258, pp. 152-159, Jun 1987.
[9] L. H. Hsu and C. K. Lin, “ Graph theory and interconnection network ” , CRC Press, 2008.
[10] S. L. Hakimi and K. Nakajima, “ On adaptive system diagnosis ” , IEEE Trans-actions on Computers, vol. C-33(3), 234-240, 1984.
[11] K. Nakajima, “ A new approach to system diagnosis ” , Proceedings of the 19th Annual Allerton Conference on Communications, Control and Computing, pp. 697-706, Sept 1981.
[12] A. Okashita, T. Araki, and Y. Shibata, “ An optimal adaptive diagnosis of but-tery networks ” , 1 The Institute of Electronics,Information and Communica-tion Engineers Transactions Fundamentals, vol. E86-A, no. 5, pp. 1008 – 1018, May 2003.
[13] A. Okashita, T. Araki, and Y. Shibata, “ Adaptive diagnosis of variants of the Hypercube ” , 1 The Institute of Electronics, Information and Communication Engineers, vol. E88 – A, no. 3, Mar 2005.
[14] F. P. Preparata, G. Metze, and R. T. Chien, “ On the connection assignment problem of daiganosable systems ” , IEEE Transactions Electronic Computers, vol. EC-16(6), pp. 848-854, 1967.
[15] C. Savage, “ A survey of combinatorial gray codes ” , 1 Society for Industrial and Applied Mathematics, vol. 39, no. 4, pp. 605-629, Dec 1997.