現在科技發達，許多國家、單位都在發展超級電腦，但由於超級電腦的處理器數量龐大，平時要如何快速、準確、有效的去診斷出故障的處理器是一項重要的問題。在由大量處理器所組成的系統中，我們並沒有辦法保證所有處理器都能隨時處於正常運作的狀態。他們隨時有可能會發生故障，但因為數量眾多，以至於我們無法立即得知哪一些處理器出問題。在這樣的情況之下，就更需要錯誤診斷的技術，錯誤診斷研究也逐年在挑戰診斷的最大值。

本論文以階層式交叉立方體(Hierarchical cross cube 以HCC 表示)網路為模擬對象，提出一個平行演算法，之前對於階層式交叉立方體的研究做到了可以在2(𝑘 + 𝑛)的壞點數量下完成3回合的診斷。而本篇提出的演算法，只要壞點數量不超過2𝑘+𝑛−2×⌊(−2+√(4+2𝑛+4))/2⌋個，其中2𝑘+𝑛−2代表切割出來的迴圈數，⌊(−2+√(4+2𝑛+4))/2⌋代表每個迴圈最大容許錯誤數量，透過這套演算法我們就可以在8回合測試內，得知其圖形上所有的錯點。

此研究也使用CUDA 進行診斷模擬，對於不同維度的階層式交叉立方體進行測試，
我們也分析模擬數據，以進一步反應此診斷演算法的實用性。

Today, many countries or units are developing about supercomputers, it includes a huge number of processors, so how to diagnose faulty processors quickly, correctly and effectively is a very important issue.

In a system which consisting of large number of processors, there is no way to ensure that all processors always work correctly. It might be broken any time, but we could not know how many processors are broken.

In such a case, some people proposes many difference algorithms
to diagnose all faulty processes, and we try to challenge a lager
number of diagnosability. In this thesis, we propose an algorithm on hierarchical cross cube networks. For this algorithm, we implement the related parallel programs and simulate it on the CUDA platform.

With our algorithm, all faulty processors can be identified as long as the number of faulty processors is less or equal than 2𝑘+𝑛−2×⌊(−2+√(4+2𝑛+4))/2⌋,2𝑘+𝑛−2 represents the number of cycles we cut out, and ⌊(−2+√(4+2𝑛+4))/2⌋ represents the maximum allowable number of errors per cycle.

The diagnosability gets a big improvement compared to the past research results.

Therefore, our algorithm is very effective and this research is very valuable.

書名頁 ii
授權書 iii
誌謝 iv
中文摘要 v
英文摘要 vi
第1章 簡介 1
1.1 論文架構 2
第2章 圖形理論基礎 3
2.1 基本定義與名詞 3
2.2 超立方體網路結構 7
2.3 交叉立方體網路結構 9
2.4 階層式交叉立方體 10
2.5 漢彌爾頓迴圈 13
2.6 交替迴圈 14
第3章 診斷模式與重要特性 17
3.1 診斷模式與基礎測試 17
3.2 比較型診斷之重要特性 18
3.3 故障點數的估算 22
3.4 基礎測試 23
3.5 進階測試 23
第4章 診斷演算法 31
4.1 演算法架構 31
第5章 實驗平台 33
5.1 GPU 平行計算平台 33
第6章 實驗數據 39
6.1 模擬數據 39
第7章 結論 45
參考文獻 47

[1] T. Araki, "Optimal adaptive fault diagnosis of cubic Hamiltonian graphs,"Proc. 7th Int. Symp. Parallel Arch.,Algor. Netw., pp.162-167, 2004.
[2] J.A. Bondy and U.S.R. Murty, “Graph theory with Applications,” North Holland, New York, 1980.
[3] C.P. Chang, P.L. Lai, J.J.M. Tan, L. H. Hsu, “Diagnosability of t-connected networks and product networks under the comparison diagnosis model,”IEEE Trans. Comput., vol. 53, no. 12, pp. 1582-1590, 2004.
[4] N.W. Chang and S. Y. Hsieh, “Conditional Diagnosability of Augmented Cubes under the PMC Model,”IEEE Transactions on Dependable and Secure Computing, vol. 9, no. 1, pp. 46-60, 2012.
[5] K. Efe, “A variation on the hypercube with lower diameter,”IEEE Transactions Computers, vol. 40, pp. 1312-1316, Nov 1991.
[6] K. Efe, “The crossed cube architecture for parallel computing,”IEEE Trans. Parallel and Distrubuted Systems, vo.l3, no.5, pp.442-451, 2004.
[7] 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.
[8] F. Harary, J. P. Hayes, and H.J.Wu. “A survey of the theory of the hypercube graphs,” Computer Mathematics with Applications, vol.15, pp.277-289, 1988.
[9] W.S. Hong and S.Y. Hsieh, “Strong Diagnosability and Conditional Diagnosability of Augmented Cubes Under the Comparison Diagnosis Model,” IEEE Yransactions on Reliability, vol 61, no.1, pp140-148,2012.
[10] S.Y. Hsieh, C.Y. Tsai and C.A. Chen, “Strong Diagnosability and Conditional Diagnosability of Multiprocessor Systems and Folded Hypercubes,” vol62, no.7, pp1472-1477, 2013.
[11] J.M. Kumar, L. M. Patnaik, “Extended hypercube: a hierarchical interconnection network of hypercubes,”IEEE Transacions on Parallel and Distributed Systems, vol. 3, pp. 45-47, 1992.
[12] E. Kranakis and A. Pelc, “Better adaptive diagnosis of hypercubes,” IEEE Transactions on Computers, vol. 49,no.10, pp.1013-1020, 2000.
[13] P.L. Lai,J.J.M.Tan,C.H.Tsai,L.H.Hsu, “The diagnosability of matching composition network under the comparison diagnosis model,”IEEE Transactions on Computers, vol.53, no.8,pp.1064-1069,2004.
[14] P.L. Lai, H.C.Hsu, C.H.Tsai, and I.A.Stewart, “A class of hierarchical graphs as topologies for interconnection networks,” Theoretical Computer Science, vol. 411, issues 31-33, pp. 2,912-2,924, 2010.
[15] P.L. Lai, “A Systematic Algorithm for Identifying Faults on Hypercube-Like Networks Under the Comparison Model,” IEEE Transactions on Reliability, vol.61,on2,pp452-459,2012.
[16] P.L. Lai, “Adaptive diagnosis for torus systems under the comparison model,”International Journal of Computer Mathematics, vol. 89, no. 2, pp. 146-159, 2012.
[17] P.L. Lai, “Adaptive system-level diagnosis for hypercube multiprocessors using a comparison model,” Information Sciences, 252: 118-131, 2013.
[18] P.L. Lai,M.Y Chiu,C.H.Tsai, “Three Round Adaptive Diagnosis in Hierarchical Multiprocessor Systems,” IEEE Transactions on Reliability, vol. 62, no. 3, pp. 608-617, Sep 2013.
[19] M. Malek, “A comparison connection assignment for diagnosis of multiprocessor systems,” in Proc. 11th nternational Symposium. Computer Architecture, pp3 31-35, 1980.
[20] J. Maeng and M. Malek, “A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor Systems,”in Proc. 11th International Symposium on Fault-Tolerant Computing, Portland, 1981, pp. 173-175.
[21] K. Nakajima, “A new approach to system diagnosis,” Proceeding of the 19th Allerton Conference on Communications, Control, and Computing, pp. 697-706, 1981.
[22] Y. Saad and M.H. Schultz. “Topological properties of hypercubes,”IEEE Transactions Computers, vol. 37, pp. 867-872, jul 1988.
[23] S.M. Sun, “A simulation of adaptive diagnosis in hierarchical crossed cubes,”National Dong Hwa University. 2015.
[24] J. Wu and K. Huang, “The Balanced Hypercube: A Cube-Based System for Fault-Tolerant Applications,” IEEE Trans. Computers, vol. 46, no.4, pp. 484-490, 1997.
[25] K.C. Wu, “A study of adaptive diagnosis for large faults in hypercubes under the comparionb model,” National Dong Hwa University. 2015.
[26] S.Q. Zheng, S. Latifi, “Optimal simulation of linear multiprocessor architectures on multiply-twisted cube using generalized Gray Codes,”IEEE Transtions Parallel abd Distributed Systems, vol. 7, no. 6, pp. 612-619, 1996.
[27] 維基百科CUDA “https://zh.wikipedia.org/wiki/CUDA”