跳到主要內容

臺灣博碩士論文加值系統

(3.95.131.146) 您好!臺灣時間:2021/07/29 01:34
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:鄧偉豪
研究生(外文):Wei-HaoDeng
論文名稱:於比較診斷模式下(n,k)-star Graph 的拓樸性質與條件偵錯度
論文名稱(外文):Topological Properties and Conditional Diagnosability of(n,k)-star Graph Under the Comparison Diagnosis Model
指導教授:謝孫源
指導教授(外文):Sun-Yuan Hsieh
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:英文
論文頁數:52
中文關鍵詞:可偵錯度(nk)星圖多處理機系统強連通比較偵錯模式條件偵錯度
外文關鍵詞:Diagnosability(nk)-star graphMultiprocessor SystemsSuper ConnectedComparison Diagnosis ModelConditional Diagnosability
相關次數:
  • 被引用被引用:0
  • 點閱點閱:136
  • 評分評分:
  • 下載下載:2
  • 收藏至我的研究室書目清單書目收藏:0
令Sn為維度n的星圖(n-star graph)的縮寫,還有一個強化版本的星圖,稱為(n,k)星圖((n,k)-star graph),可縮寫成Sn,k, W.K.Chiang在1995年時提出此(n,k)-星圖的結構。在最近幾年,由於多處理器系統(multiprocessor system)快速的發展,一個系統內的處理器數量快速增加,導致多處理器系統的偵錯(diagnosis)變為極重要的一個議題。Lai介紹了一個新的偵錯理念,稱為條件偵錯度(conditional diagnosability),在多處理器系統中,條件式偵錯相較於傳統的偵錯方式表現的更好,本篇論文即證明了在比較偵錯模式(comparison diagnosis model)下的(n,k)-星圖的條件偵錯度為n+2k-5,其中n ≥ 5, k ≥ 3,n – k ≥ 2。
Let Sn be the n-star graph with degree n, and there is an enhanced version of Sn, called (n,k)-star graph, denoted by Sn,k. The (n,k)-star graph was proposed in 1995 by W.K. Chiang et al. In recent years, diagnosis has been one of the most important issue as the size of multiprocessor system grows rapidly.
Conditional diagnosability is a new measure of diagnosability introduced by Lai et al. It is a better method to measure the diagnosability of regular interconnection networks. This thesis shows that the conditional diagnosability of (n,k)-star graph is n+2k-5, for n ≥ 5, k ≥ 3,n – k ≥ 2 under the comparison diagnosis model.

Contents

1 Introduction 1
1.1 The (n,k)-Star Graph................................3
1.2 Fault Tolerance.....................................9
1.3 Fault Diagnosis....................................13

2 Preliminaries 16
2.1 Basic Defnitions and Notation......................16
2.2 Comparison Diagnosis Model.........................18
2.3 Diagnosability of Systems..........................20

3 Properties of (n,k)-Star Graph 23
3.1 Basic Properties...................................23
3.2 Properties of the Fault Tolerant...................26

4 Conditional Diagnosability of (n,k)-Star Graph 35
4.1 Upper Bound of tc(Sn,k)............................36
4.2 Lower Bound of tc(Sn,k)............................37
4.2.1 Lower Bound of tc(Sn,1)(Complete Graph)..........38
4.2.2 Lower Bound of tc(Sn,2)..........................38
4.2.3 Lower Bound of tc(Sn,k)..........................40

5 Conclusion 43

Bibliography 46
[1] S. B. Akers, B. Krishnamurthy, D. Harel, The star graph: an attractive alternative to the n-cube, in Proceedings of the International Conference on Parallel
Processing, pp.393-400, 1987.
[2] C. Balbuena, M. Cera, A. Dianez, P. Garcia-Vazquez, and X. Marcote, On the restricted connectivity and superconnectivity in graphs with given girth, Discrete
Mathematics, vol. 307, issue 6, pp. 659-667, 2007.
[3] D. Bauer, F. Boesch, C. Suffel, and R. Tindell, Connectivity extremal problems and the design of reliable probabilistic networks in The theory and application of
graphs, pp.89-98, 1981.
[4] 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 in IEEE
Transactions on Conputers, vol. 53, no. 12, pp.1582-1590, 2004.
[5] E. Cheng, M. J. Lipman, Increasing the connectivity of the star graphs in Networks, pp. 165-169, 2002.
[6] G.Y. Chang, G.J. Chang, and G.H. Chen, Diagnosabilities of Regular Networks
in IEEE Transaction Parallel and Distributed Systems, vol. 16, no. 4 , pp. 314-323,
2005.
[7] N. W. Chang and S. Y. Hsieh, Conditional diagnosability of augmented cubes under the PMC model, IEEE Transactions on Dependable and Secure Computing,
http://doi.ieeecomputersociety.org/10.1109/TDSC.2010.59.

[8] Y. C. Chen and J. J. M. Tan, Restricted connectivity for three families of interconnection networks, Applied Mathematics and Computation, vol. 188, issue 2,
pp. 1848-1855, 2007.
[9] W.K. Chiang, R.J. Chen, The (n,k)-star graph : A generalized star graph in Information Processing Letters, pp. 259-264,1995.
[10] W.K. Chiang, R.J. Chen, Topological properties of the (n,k)-star graph, in International Journal of Foundations of Computer Science, Vol. 9, No. 2, pp.
235-248, 1998.
[11] Y.-Y. Chen, D.-R. Duh, T.-L. Ye, and J.-S. Fu, Weak-vertex-pancyclicity of (n,k)-star graphs, in Theoretical Computer Science, Vol. 396, pp. 191-199, 2008.
[12] E. P. Duarte JR, R. P. Ziwich, and L. C. P. Albini, A Survey of Comparison-Based System-Level Diagnosis, ACM Computing Surveys, vol. 43, no. 3, article
22, pp. 1-56, 2011.
[13] J. Fabrega and M. A. Fiol, Extraconnectivity of graphs with large girth, Discrete Mathematics, vol. 127, pp. 163-170, 1994.
[14] J. Fabrega and M. A. Fiol, On the extraconnectivity of graphs , Discrete Mathematics, vol. 155, pp. 49-57, 1996.
[15] J. Fan, Diagnosability of crossed cubes under the two strategies, Chinese Journal of Computers, vol. 21, issue 5, pp. 456-462, 1998.
[16] J. Fan, Diagnosability of the Mobius cubes, IEEE Transactions on Parallel and Distributed Systems, vol. 9, issue 9, pp. 923-928, 1998.
[17] J. Fan, Diagnosability of Crossed Cubes under the Comparison Diagnosis Model in IEEE Transsation Parallel and Distributed Systems, vol. 13, no. 7, pp. 687-692,
2002.

[18] F. Harary, Conditional connectivity, Networks, vol. 13, issue 3, pp. 347-357,
1983.
[19] W. S. Hong and S. Y. Hsieh, Strong diagnosability and conditional diagnosability of augmented cubes under the comparison diagnosis model, IEEE Transactions
on Reliability, accepted.
[20] S. Y. Hsieh and Y. S. Chen, Strongly diagnosable systems under the comparison diagnosis model, IEEE Transactions on Computers, vol. 57, issue 12, pp. 1720-
1725, 2008.
[21] S.Y. Hsieh, Y.S. Chen, Strongly Diagnosable Product Networks Under the Comparison Diagnosis Model in IEEE Transactions on Computers, vol. 57, no. 6, pp.
721-732, 2008.
[22] S.Y. Hsieh, T.Y. Chuang, The Strong Diagnosability of Regular Networks and Product Networks under the PMC Model in IEEE Transactions on Parallel and Distributed Systems, vol. 20, no. 3, pp. 367-378, 2009.
[23] S.Y. Hsieh, C.Y. Tsai, Extra Connectivity and Conditional Diagnosability of Folded Hypercubes ,accepted
[24] S.Y. Hsieh, C.Y. Kao, Computing the Conditional Diagnosability of k-ary n-Cube Under the Comparison Diagnosis Model ,accepted
[25] S.Y. Hsieh, T.Y. Lin, Computing the Conditional Diagnosability of k-ary n-Cube Under the PMC Model ,accepted
[26] H. Hsu, Y. Hsieh, J. Tan, and L. Hsu, Fault hamiltonicity and fault hamiltonian connectivity of the (n,k)-star graphs in Networks, Vol. 42, No. 4, pp. 189-201,
2003.

[27] 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.
[28] G. H. Hsu, C. F. Chiang, L. M. Shih,and J. J. M. Tan, Conditional diagnosability of hypercube under the comparison diagnosis model, Journal of Systems
Architecture, vol. 55, issue 2, pp. 140-146, 2009.
[29] A. Kavianpour, Sequential diagnosability of star graphs, Computers and Electrical Engineering, vol. 22, issue 1, pp. 37-44, 1996.
[30] A. Kavianpour and K. H. Kim, Diagnosability of hypercubes under the pessimistic one-step diagnosis strategy, IEEE Transactions on Computers, vol. 40,
issue 2, pp. 232-237, 1991.
[31] A. Kavianpour and K. H. Kim, A comparative evaluation of four basic system-level diagnosis strategies for hypercubes, IEEE Transactions on Reliability, vol.
41, issue 1, pp. 26-37, 1992.
[32] S. Latifi, M. Hegde, and M. Naraghi-Pour, Conditional connectivity measures for large multiprocessor systems, IEEE Transactions on Computers, vol. 43, no. 2,
pp. 218-222, 1994.
[33] C. W. Lee and S. Y.Hsieh, Determining the diagnosability of (1,2)-matching composition networks and its applications, in IEEE Transactions on Dependable
and Secure Computing, vol. 8, issue 3, pp. 353-362, 2011.
[34] C. W. Lee and S. Y.Hsieh, Diagnosability of two-matching composition networks under the MM* model, IEEE Transactions on Dependable and Secure Computing,
vol. 8, issue 2, pp. 246-255, 2011.
[35] C.K. Lin, Jimmy J. M. Tan, L.H. Hsu, E. Cheng, and L. Liptak, Conditional Diagnosability of Cayley Graphs Generated by Transposition Trees Under the
Comparison Diagnosis Model in Interconnection Networks, vol. 9, pp. 83-97, 2008.

[36] J. Li, M. Chen, Y. Xiang, and S. Yao, Optimum broadcasting algorithms in (n,k)-star graphs using spanning trees in IFIP International Federation for Information
Processing, pp. 220-230, 2007.
[37] P.L. Lai, Jimmy J.M. Tan,C.H. Tsai and L.H. Hsu, The diagnosability of the matching composition network under the comparison diagnosis model in IEEE
Transactions on Conputers,vol.53, pp. 1064-1069, 2004.
[38] P.L. Lai, Jimmy J.M. Tan, Chien-Ping Chang, and Lih-Hsing Hsu, Conditional Diagnosability Measures for Large Multiprocessor Systems in IEEE Transactions
on Conputers,vol.54, no.2, pp. 165-175, 2005.
[39] M. J. Ma, G. Z. Liu, and J. M. Xu, The super connectivity of augmented cubes,Information Processing Letters, vol. 106, issue 2, pp. 59-63, 2008.
[40] J. Maeng and M. Malek, A comparison connection assignment for self-diagnosis of multiprocessors systems, in Proceedings of the 11th International Symposium
on Fault-Tolerant Computing, pp. 173-175, 1981.
[41] M. Malek, A comparison connection assignment for diagnosis of multiprocessors systems, in Proceedings of the 7th International Symposium on Computer Architecture, pp. 31-36, 1980.
[42] F. P. Preparata, G. Metze, and R.T. Chien, On the connection assignment problem of diagnosis systems, IEEE Transactions on Electronic Computers, vol. 16,
issue 12, pp. 848-854, 1967.
[43] A. Sengupta, A. Dahbura, On self-diagnosable multiprocessor systems:diagnosis by comparison approach in IEEE Transactions on Conputers, pp. 1386-
1396,1992.
[44] J. J. Sheu, W. T. Huang, and C. H. Chen, Strong diagnosability of regular networks under the comparison model, Information Processing Letters, vol. 106,
pp. 19-25, 2008.

[45] M. Wan and Z. Zhang, A kind of conditional vertex connectivity of star graphs, Applied Mathematics Letters, vol. 22, issue 2, pp. 264-267, 2009.
[46] D. Wang, Diagnosability of Enhanced Hypercubes in IEEE Transactions on Conputers, vol. 43, no. 9, pp. 1054-1061, 1994.
[47] D. Wang, Diagnosability of Hypercubes and Enhanced Hypercubes Under the Comparison Diagnosis Model in IEEE Transactions on Conputers, vol. 48, no.
12, pp. 1369-1374, 1999.
[48] D. B. West, Introduction to Graph Theory, Prentice Hall Publishers, 2001.
[49] H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math.,
vol. 54, pp. 150-168, 1932.
[50] J. M. Xu, M. LÄu, M. J. Ma, and A. Hellwig, Super connectivity of line graphs, Information Processing Letters, vol. 94, issue 4, pp. 191-195, 2005.
[51] 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, issue 11, pp. 875-879, 2009.
[52] J. M. Xu, J. W. Wang, and W. W. Wang, On super and restricted connectivity of some interconnection networks, Ars Combinatoria, vol. 94, 2010.
[53] J. M. Xu, Q. Zhu, and M. Xu, Fault-tolerant analysis of a class of networks,Information Processing Letters, vol. 103, issue 6, pp. 222-226, 2007.
[54] M. Xu, X. Hu, Songpu. Shang, The Conditional Diagnosability of Shu²e-Cubesin Jounal of system science and complexity, vol 23, pp. 81-90, 2010.
[55] X. Yang,D.J. Evans and G. M. Megson, On the maximal connected component of a hypercube with faulty vertices III, Int J Comput Math pp. 27-37, 2006.

[56] W. H. Yang and J. X. Meng, Extraconnectivity of hypercubes, Applied Mathematics Letters, vol. 22, issue 6, pp. 887-891, 2009.
[57] S. Zhou, The conditional diagnosability of MÄobius cubes under the comparison model, Proceedings of the 2009 IEEE International Conference on Information
and Automation, pp. 96-100, 2009.
[58] S. Zhou, The conditional diagnosability of locally twisted cubes, Proceedings of 2009 4th International Conference on Computer Science and Education, pp.
221-226, 2009.
[59] S. Zhou, The conditional diagnosability of twisted cubes under the comparison model, 2009 IEEE International Symposium on Parallel and Distributed Process-
ing with Applications, pp. 696-701, 2009.
[60] Q. Zhu, S.Y. Liu , M. Xu , On conditional diagnosability of the folded hypercubes inInformation Sciences vol 178, pp. 1069-1077, 2008
[61] Q. Zhu, On conditional diagnosability and reliability of the BC networks in The Journal of Supercomputing vol 45, no.2, pp. 173-184, 2008
[62] S. Zhou, L. Chen, Fault Tolerance of (n,k)-Star Graphs in The 5th International Conference on Computer Science and Educations 2010.
[63] S. Zhou, W. Xiao, Conditional diagnosability of alternating group networks in Information Processing Letters, pp. 403-409, 2010.
[64] S. Zhou, W. Xiao, The Conditional diagnosability of crossed cube under the comparison model in International Journal of Computer Mathematis, pp. 3387-
3396, 2010.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊