博碩士論文 87325025 詳細資訊




以作者查詢圖書館館藏 以作者查詢臺灣博碩士 以作者查詢全國書目 勘誤回報 、線上人數:9 、訪客IP:3.133.154.114
姓名 簡銘宣(Ming-shian Jian)  查詢紙本館藏   畢業系所 資訊工程學系
論文名稱 在高維Tori/Meshes蟲洞繞徑網路上具負載平衡之多點群播
(Multi-Node Multicast in Three and Higher Dimensional Wormhole Tori and Meshes with Load Balance)
相關論文
★ 在網路上提供單色影像傳輸的認證及所有權驗證之協定★ 無線行動隨建即連網路的媒介存取: 一個具動態頻道分配的 MAC 協定
★ 在個人通訊系統下銷售員移動模型之位置追蹤方法★ 在Linux環境下設計及實作具位置知覺的無線行動隨建即用網路之繞徑協定
★ 以動態方法解決在無線行動隨建即連網路環境下之廣播風暴問題★ 一個適用於熱門視訊服務之遞迴頻率分割廣播策略
★ 在雙階層無線ATM網路下細胞部署與路徑預留的策略★ 使用Java語言製作一個行動資料系統
★ 在數位影像上資料隱藏技術之探討★ 在Linux環境下設計及實作一個隨意行動無線網路的繞徑最佳化協定
★ 在無線隨意行動網路下設計多重路徑之具有服務品質的繞徑協定★ 在 Linux 環境下設計並實作具蜂巢式無線基地台之 IEEE 802.11 區域網路
★ 數位影像上高資料隱藏率的方法探討★ 一個適用於熱門視訊廣播的無隙縫階梯式資料排程與頻道配置策略
★ 無線隨意網路上的一個隨選式具服務品質及鍊結狀態之多重路徑繞徑協定★ 環形藍芽網路:一個藍芽通訊網路的新拓樸及其繞徑協定
檔案 [Endnote RIS 格式]    [Bibtex 格式]    [相關文章]   [文章引用]   [完整記錄]   [館藏目錄]   [檢視]  [下載]
  1. 本電子論文使用權限為同意立即開放。
  2. 已達開放權限電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
  3. 請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。

摘要(中) 在多處理器網路中,互相間有許多的理由需要通訊,例如資料的通訊或事件的同步。集體通訊的例子,例如有廣播或群播。應用包括parallel unmerial algorithms, graph algorithm, image process algorithm, cache coherence, 及 barrier synchronization。
蟲洞繞徑是一個在內連接網路的轉換技術,它具有低通訊延遲及在沒有競爭情形下對於繞徑距離不敏感的特性。
本篇論文討論多維度多點群播問題使用蟲洞繞徑、維度順序繞徑、單埠模型在多維的torus及meah網路。由任意數目的起始點送群播的訊息到任意數目的目的地端點。問題的挑戰點在於也許存在於一連串的碰撞當起始目的點的數目很大或有hot-spot現象時(起始點或是目的地點集中在一個小區域時),為了解決這個問題我們應用了兩個策略:網路分割及負載平衡。我們先將網路分成許多的子網路,並將群播的訊息傳送到各子網路以達到交通負載的平衡。
本篇論文是對於原先的2D Tori/meshes 上群播的擴充,我們將之推展到高維度tori/meshes。我們提出將torus/mesh網路切割成一些的子網路,這些子網路仍然是一個torus/mesh的結構。若現在做一個多點群播,第一步先將群播訊息在每一子網路上傳播,希望將所有的交通流量均勻的分配到各子網路。然後每一個子網路執行相同數目的群播訊息。根據之前的經驗,藉由以上的步驟可以得到效能上很大的改進。在本篇論文中,我們將提出幾種網路切割方式在torus/mesh上。透過廣泛的模擬,我們證明在許多種的情形下,我們所提出的網路切割在與u-torus/u-mesh等方法比較時,會有較好的效能。此外在出現有hot-spot現象時,就是有起始點或目的點集中在一小區域時,我們所提出平衡負載,在這種現象將扮演更重要的角色。
摘要(英) This thesis considers the multi-node multicast problem in a multi-dimensional wormhole-routed torus/mesh, where there are an arbitrary number of source nodes each intending to multicast a message to an arbitrary set of destinations. This problem requires a large amount of bandwidth, and thus typically incurs heavy contention and congestion. Evenly balancing the traffic load around the network is a critical issue to achieve good performance. We show how to use a network-partitioning approach to achieve this goal. Simulation results show significant improvement over existing results in 3D tori and meshes. This work is an extension of our earlier work from 2D tori/meshes to
higher dimensional ones.
關鍵字(中) ★ 平行處理
★ 群播
★ 網格
★ 負載平衡
★ 內部連接網路
★ 聚集通訊
★ 環面體
★ 蟲洞繞徑
關鍵字(英) ★ multicast
★ mesh
★ load balance
★ interconnection network
★ collective communication
★ parallel processing
★ torus
★ wormhole routing
論文目次 1 Introduction ..............................................1
2 Preliminaries ..............................................4
2.1 Network Model .........................................4
2.2 Subnetworks of a Wormhole Network ....................5
2.3 A General Model for Multi-NodeMulticasts .............6
3 Subnetworks of a 3D Torus/Mesh ............................9
3.1 DDN's and DCN's in a 3D Torus ........................9
3.2 DDN's and DCN's in a 3D Mesh ........................16
4 Multi-Node Multicast in a 3D Torus ........................17
4.1 Phase 1: Balancing TraÆc among DDNs ..................17
4.2 Phase 2: Multicasting in DDNs ........................18
4.3 Phase 3: Multicasting in DCNs ........................19
4.4 Simulation and Performance Comparison ................19
5 Multi-Node Multicast in a 3D Mesh ........................25
5.1 Phase 2: Modied Multicasting in DDNs ..............25
5.2 Simulation and Performance Comparison ................25
6 Subnetworks of Higher Dimensional Tori/Meshes ............29
7 Conclusions ..............................................31
參考文獻 [1] Intel Corporation. A Touchstone DELTA system description, 1990.
[2] Cray Research Inc. CRAY T3E scalable parallel processing system, 1995.
[3] N. Agrawal and C. P. Ravikumar. An euler path based technique for deadlock-free
mutlicasting. In Int'l Conf. on Parallel Processing, pages 378{383, 1997.
[4] W. C. Athas and C. L. Seitz. Multicomputers: Message passing concurrent com-
puters. IEEE Computers, pages 9{25, Aug. 1988.
[5] H. D. Cheng, Y. Y. Tang, and C. Y. Suen. Parallel image transformation and its
VLSI implementation. Pattern Recognition, 23(10):113{129, 1990.
[6] J. Choi, J. J. Dongarra, R. Pozo, and D. W. Walker. ScaLAPACK: A scalable
linear algebra library for distributed memory concurrent computers. In Symp. on
Frontiers of Massively Parallel Computation, pages 120{127, 1992.
[7] L. D. Coster, N. Dewulf, and C.-T. Ho. EÆcient multi-packet multicast algo-
rithms on meshes with wormhole and dimension-ordered routing. In Int'l Conf.
on Parallel Processing, volume 3, pages 137{141, 1995.
[8] W. J. Dally and C. L. Seitz. The torus routing chip. J. of Distributed Computing,
1(3):187{196, 1986.
[9] B. Duzett and R. Buck. An overview of the nCUBE 3 supercomputer. In Symp.
on Frontiers of Massively Parallel Computation, pages 458{464, 1992.
[10] C. T. Ho and M. T. Raghunath. EÆcient communication primitives on hypercubes.
Journal of Concurrency: Practice and Experience, 4(6):427{457, Sep 1992.
[11] R. Kesavan and D. Panda. Multiple multicast with minimize node contention
on wormhole k-ary n-cube networks. IEEE Trans. on Paral. and Distrib. Sys.,
10(4):371{393, April 1999.
[12] R. E. Lessler and J. L. Schwazmeier. CRAY T3D: A new dimension for Cray
Reasearch. In COMPCON, pages 176{182, 1993.
[13] K. Li and R. Chaefer. A hypercube shared virtual memory. In Int'l Conf. on
Parallel Processing, volume 1, pages 125{132, 1989.
[14] X. Lin, P. K. McKinley, and L. M. Ni. Deadlock-free multicast wormhole routing in
2D mesh multicomputers. IEEE Trans. on Paral. and Distrib. Sys., 5(8):793{804,
Aug. 1994.
[15] P. K. Mckinley, H. Xu, A.-H. Esfahanian, and L. M. Ni. Unicast-based multicast
communication in wormhole-routed networks. IEEE Trans. on Paral. and Distrib.
Sys., 5(12):1252{1265, Dec. 1994.
[16] L. M. Ni and P. K. McKinley. Asurvey of wormhole routing techniques in directed
network. IEEE Computers, 26(2):62{76, Feb. 1993.
[17] P. R. Nuth and W. J. Dally. The J-machine network. In IEEE Int'l Conf. on
Computer Design: VLSI in Computer and Processors, pages420{423, 1992.
[18] D. F. Robinson, P. K.Mckinley, and B. H. C. Cheng. Optimal multicast commu-
nication in wormhole-routed torus networks. IEEE Trans. on Paral. and Distrib.
Sys., 6(10):1029{1042, Oct. 1995.
[19] H. D. Schwetman. Using csim to model complex systems. In Proceedings of the
1988 Winter Simulation Conference, pages 246{253, 1988.
[20] G. D. Stamoulis and J. N. Tsitsiklis. EÆcient routing schemes for multiple broad-
casts in hypercubes. IEEE Trans. on Paral. and Distrib. Sys., 4(7):725{739, July
1993.
[21] Y.-C. Tseng, M.-H. Yang, and T.-Y. Juang. An euler-path-based multicasting
model for wormhole-routed networks with multi-destination capability. In Int'l
Conf. on Parallel Processing, pages 366{373, 1998.
[22] S.-Y. Wang, Y.-C. Tseng, C.-S. Shiu, and J.-P. Sheu. Balancing traÆc load for
multi-node multicast in a wormhole 2d torus/mesh. In Int'l Parallel and Dis-
tributed Processing Symp., 2000.
[23] H. Xu, P. K. McKinley, and L. M. Ni. EÆcient implementation of barrier syn-
chronization in wormhole-routed hypercubes multicomputers. J. of Parallel and
Distrib. Comput., 16:172{184, 1992.
指導教授 曾煜棋(Yu-Chee Tseng) 審核日期 2000-6-29
推文 facebook   plurk   twitter   funp   google   live   udn   HD   myshare   reddit   netvibes   friend   youpush   delicious   baidu   
網路書籤 Google bookmarks   del.icio.us   hemidemi   myshare   

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡  - 隱私權政策聲明