跳到主要內容

臺灣博碩士論文加值系統

(34.204.169.230) 您好!臺灣時間:2024/02/28 07:51
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:王能中
研究生(外文):Wang, Nen-Chung
論文名稱:在具蟲洞繞路星狀圖連結網路上設計多點傳輸演算法
論文名稱(外文):Multicast Algorithms in Wormhole-Routed Star Graph Interconnection Networks
指導教授:朱治平朱治平引用關係
指導教授(外文):Chu Chih-Ping
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1998
畢業學年度:86
語文別:中文
論文頁數:55
中文關鍵詞:平行處理連結網路星狀圖多點傳輸蟲洞繞路
外文關鍵詞:parallel processinginterconnection networkstar graphmulticastwormhole routing
相關次數:
  • 被引用被引用:0
  • 點閱點閱:142
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
平行處理技術因可支援高效能的計算而日益重要。所以以網路連結的大量
平行處理電腦,在以高速計算為主的應用上對平行處理技術的需求也日益
增加。多點傳輸(multicast)是連結網路的一種重要的通訊機制,目前被
廣泛的應用在平行處理的領域中。星狀圖(star)網路由於與超維立方(
hypercube)網路相較,各節點具低分支度(degree)及較短的節點間最大距
離,被認為比普受歡迎的超維立方網路更具潛力。在這篇論文,我們以蟲
洞繞路為傳輸方式,首先針對星狀圖網路導出植基於漢米爾頓路徑之節點
標號計算公式,繼而提出以漢米爾頓路徑為基底之四種有效的、且均不會
產生死結(deadlock)的多點傳輸方案。第一個方案是雙路徑(dual-path)
傳輸,雙路徑傳輸包含兩個路徑(往高標號節點及往低標號節點),其傳輸
之下一節點為目前訊息所在節點所有相鄰節點中標號最接近下一未拜訪目
的節點者。第二個方案是捷徑點基底雙路徑(shortcut-node-based dual-
path)傳輸,捷徑點基底雙路徑傳輸方法類似雙路徑傳輸,但儘可能尋找
訊息繞路捷徑節點,以降低傳輸路徑之長度。第三個方案是多路徑(
multipath)傳輸,多路徑傳輸是一種多重之雙路徑傳輸策略,包含原始節
點至暫存節點傳輸階段及暫存節點至目的節點傳輸階段。第四個方案是接
近分群(proximity grouping)傳輸,接近分群傳輸也是一種多重之雙路徑
傳輸策略,但在原始及目標節點之分割(partition)上考慮到空間局部位
置(spatial locality)之關係,以降低傳輸路徑之長度。接近分群傳輸包
含原始節點至領導節點傳輸階段及領導節點至目的節點傳輸階段。最後,
我們亦針對這四種方案作多點傳輸模擬實驗,證實本論文所提出之多點傳
輸方法確實能夠顯著改進以單點傳輸為基底及傳統的漢米爾頓路徑的繞路
方法之效能。

Parallel processing technique has become important because it
supports high-performance computation. So, massively parallel
processing computers connected by a variety of interconnection
networks are increasingly demanded for high-performance
computation-based applications. Multicast, an important
communication mechanism, is frequently used in many applications
of parallel computing. The star graph interconnection network,
when compared with the hypercube network, which has superior
features including low degree and small diameter, has been
recognized to be an attractive alternative to the popular
hypercube network. In this thesis, we first derive a node
labeling formula based on a hamiltonian path and then propose
four efficient multicast routing schemes in wormhole-routed star
networks with multidestination capability. All of the four
proposed schemes are path-based and deadlock-free. The first
scheme, dual-path routing, includes two independent paths
(toward high label nodes and low label nodes). To this approach,
the next traversed node is the one with nearest label to that of
the next unvisited target node of all its neighboring nodes. The
second one, shortcut-node-based dual-path routing, is similar to
dual-path scheme except that the routing tries to find a
shortcut node to route the message as soon as possible to reduce
the length of transmission path. The third one, multipath
routing, is a multiple dual-path routing strategy that includes
source-to-relay and relay-to-destination phases. The last
scheme, proximity grouping routing, is also a multiple dual-path
routing strategy except that in the partitioning step of source
and destination nodes the relation of spatial locality of nodes
is also taken into account to reduce the length of transmission
paths. The proximity grouping routing includes source-to-leader
and leader-to-destination phases. Finally, the experimental
results are given to show that the performance based on unicast-
based and traditional hamiltonian-path routing schemes can be
improved significantly by our four proposed routing schemes.

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