跳到主要內容

臺灣博碩士論文加值系統

(18.97.14.82) 您好!臺灣時間:2025/02/15 02:11
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:張道統
研究生(外文):Dao-Tong Chang
論文名稱:方格網狀多處理機系統之最短路徑容錯繞線研究
論文名稱(外文):A Study of Shortest-Path Fault Tolerant Routing in 2D Meshes
指導教授:邱舉明邱舉明引用關係
指導教授(外文):Ge-Ming Chiu
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:電機工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1999
畢業學年度:87
語文別:中文
論文頁數:41
中文關鍵詞:矩形損壞阻隔線容錯方格網狀繞線
外文關鍵詞:fault-tolerantblock faultsmeshrouting
相關次數:
  • 被引用被引用:0
  • 點閱點閱:564
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在此論文中,我們主要針對二維方格網狀多處理機系統(mesh),存在矩形損壞區塊之情形,提出訊息由起始節點到目的節點擁有最短路徑之充份必要條件。首先我們根據損壞區塊之相對位置定義一最短路徑阻隔線,利用此最短路徑阻隔線、起始節點座標與目的節點座標三資訊之相對關係提出擁有最短路徑之充份必要條件。再者,利用前述之相關特性此條件提出一容錯繞線演算法,根據此繞線方法,個別節點只需擁有有限的損壞資訊,利用這有限的損壞資訊,該繞線方法會將訊息盡可能以最短之路徑送達其目的節點,而若無最短路徑時也能夠以較短之路徑送達目的節點。

In this thesis the issues of fault-tolerant routing in mesh networks with block faults are studied. We first introduce the concept of shortest-path blocking lines so as to capture the effects of the faults on a pair of source-destination nodes. Basically, a shortest-path blocking line is a combination of line segments that together may prohibit any shortest path to cross over. This concept is then used to present a necessary and sufficient condition for the existence of a shortest path between the source and the destination nodes. Based on the properties developed previously, we then propose a fault-tolerant routing algorithm for faulty meshes. The algorithm would first collect some limited fault information. Using this information, any intermediate node would try to route a message via a shortest path whenever possible.

第一章 序論 1
1.1論文架構 3
第二章 相關研究 4
第三章 最短路徑阻隔線 7
3.1 系統模型 8
3.2 最短路徑阻隔線10
第四章 容錯繞線演算法19
4.1 損壞資訊之散發20
4.2 繞線演算法 27
第五章 結論與未來工作38
5.1 結論 38
5.2 未來工作 39

[1] W. J. Dally and C. L. Seitz. Deadlock-free message routing in multi-processor interconnection networks. IEEE Transactions.on Computers,C-36(5):547-553,1987.
[2] Rajendra V. Boppana and Suresh Chalasani. Fault-Tolerant Wormhole Routing Algorithm for Mesh Networks. IEEE Transactions on Computers. VOL. 44, NO.7,JULY 1995
[3] Younes M. Boura and Chita R. Das. Fault-tolerant Routing in Mesh Networks. 1995 International Conference on Parallel Processing.
[4] A. A. Chien and J. H. Kim. Plannar-adaptive routing. Low-cost adaptive networks for multiprocessors. In Proc. 19th Ann. Int. Symp. on Computer Architecture, pages 268-277,1992.
[5] Ran Libeskind-Hadas and Eli Brandt. Origin-Based fault-tolerant routing in the mesh. In Proc. First IEEE Symposium on High-Performance Computer Architecture,page 102-111,1995.
[6] C.C.Su and K.G. Shin. Adaptive fault-tolerant deadlock-free routing in meshes and hypercubes. IEEE transactions On Computers. 45,(6),June 1996,672-683
[7] Intel Corporation. A Touchstone DELTA System Description. 1991.
[8] Jie Wu, Fault-tolerant Adaptive and Minimal Routing in Mesh-connected Multicomputers Using Extended Safety levels. in Proc. 1998 18th Int. Conf. On Distributed Computing Systems. 428-435.
[9] Anjan K.V. and Timothy Mark Pinkston. An Efficient,Fully Adaptive Deadlock Recovery Scheme:DISHA. in the 22nd Ann. Int. Symp. On Computer Architecture.201-210,1995
[10] P. Lopez.,J.M. Martinez,J. Duato. A very Efficient Distributed Deadlock Detection Mechanism for wormhole Networks. In Proc. 1998 of 4th Int. Symp. on High Performance Computer Architecture.
[11] J.M. Martinez,P. Lopez.,J. Duato. Impact of Buffer Size on the Efficiency of Deadlock Detection . In Proc. 1999 of 5th Int. Symp. on High Performance Computer Architecture.
[12] J.Kim,Z. Liu, and A.Chien. Compressionless Routing: A Framework for Adaptive and Fault-tolerant Routing . in proc. Of the 21st Int. Symp. on Computer Architecture, IEEE Computer Society,pages 289-300, April 1994.
[13] Douglas S. Reeves, Edward F. Gehinger, and Anil Chandirmani. Adaptive Routing and Deadlock Recovery:A Simulation Study. In Proc. of the 4th Conf. On Hypercube Concurrent Computers and Applications, March 1989.
[14] D. H. Linder and J. C. Harden. An Adaptive and Fault-Tolerant Wormhole Routing Strategy for k-ary n-cubes. IEEE Transactions on Computers,40:2-12,1991.
[15] P.H. Sui and S.D. Wang. An improved algorithm for foult-tolerant wormhole routing in meshes. IEEE Transactions. On Computers, 46(9):1040-1042. September 1997.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top