 |
|
|
|
以作者查詢圖書館館藏 、以作者查詢臺灣博碩士 、以作者查詢全國書目 、勘誤回報 、線上人數：43 、訪客IP：3.144.46.90
姓名 林超(Chao Lin) 查詢紙本館藏 畢業系所 資訊工程學系 論文名稱 非同質網路資訊廣播傳送演算法
(Efficient Broadcast in Heterogeneous Networks of Workstations with Multiple Send and Receive Speeds)相關論文 檔案 [Endnote RIS 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
[檢視]
- 本電子論文使用權限為同意立即開放。
- 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
- 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。
摘要(中) 非同質網路(Heterogeneous Networks of Workstation)是指連接網路的工作站或電腦具有不同的速度, 其中包括CPU, Memory, I/O 介面,網路卡,及資訊接收或傳送速度等.相反的, 同質性網路(Homogeneous Networks of Workstation)其所連接的工作站或電腦有相同的速度, 實際上目前的區域路其switch及Hub 所連接的 電腦及 工作站 速度不同,皆屬非同質網路.
在Internet網路上, 無論是Switch 或 Hub, 可連接許多不同類型的電腦; 這些電腦有不同的傳送與接受資料速度, 功能比美超級電腦的Cluster 網路, 因連接電腦速度的不同,整個系統效益大受影響,例如資料的廣播傳送速度乃深受此因素的影響.本篇論文研究主體是在各類型的非同質性網路上提高資料傳送的速度. 共分兩類廣播(Broadcast)演算法,其一在無網路分割之情形,設計出三種不同廣播(Broadcast)演算法, 此三種演算法皆是無碰撞( Without Contention),演算法, 複雜度nlog(n).
其二是將網路分割成不同的兩個子網路, 個別選取兩個不同的Source,接著兩個網路從Source 將資料平行傳送到他所屬子網路, 以上兩種皆可大大提升網路傳送效益摘要(英) In an Heterogeneous Networks of Workstations (HNOW), many different speed types of workstations can have distinct send and receive overhead. Previous research has shown that finding an optimal routing scheme in an HNOW is not easy [16,2], because properly arranging all workstations in the scheduling tree is difficult. Therefore, this investigation focuses mainly on enhancing the performance of an HNOW by properly arranging fastest nodes into the internal nodes of upper levels in the scheduling tree and using two sub-networks to broadcasting an HNOW. This dissertation is organized into two parts. In the first part, three efficient contention-free algorithms for broadcasting on heterogeneous networks of workstations (HNOW) are presented. In the second part, we present broadcast algorithms using two sub-networks.
Fastest node first is fundamental in designing an efficient algorithm. Three schemes called EBS,VBBS, and VBBSWF are presented in the first part. All of these three schemes can be executed in O(nlog(n)) time, where n is the number of workstations. They are all contention-free when broadcasting in an HNOW. Based on the simulation result, the proposed schemes outperform the broadcast with minimal steps [17] and the scheduling tree [31] generated by dynamic programming in an HNOW.
Furthermore, we also present efficient algorithms for broadcasting on heterogeneous networks of workstations by two partitioned sub-networks. Previous research presented that routing by two sub-networks in a NOW can significantly increase system’s performance [20]. We propose two schemes TWO-EBS and TWO-VBBS for broadcasting in an HNOW.
These two schemes divide an HNOW into two sub-networks that are routed concurrently, and simultaneously combine EBS and VBBS to broadcast in an HNOW. Based on simulation results, TWO-VBBS outperforms EBS,VBBS, VBBSWF[19], the postorder recursive doubling[17] , and the optimal scheduling tree [31] generated by dynamic programming in an HNOW.關鍵字(中) ★ 自動網路
★ 擴張樹
★ 最佳化排程樹
★ 非同質網路
★ 封包接續傳送
★ 單一傳送關鍵字(英) ★ heterogeneous network of workstation
★ unicast- based broadcast
★ postorder recursive doubling algorithm
★ autonet
★ wormhole routing
★ network partitioning
★ up*/down* routing
★ myrinet論文目次 1 Introduction 1
2 PART I
Three Broadcasting Strategies on an HNOW 5
2.1 Preliminaries and Related Works ..................………….. 5
2.1.1 Preliminaries ...........................…………………….. 5
2.1.2 Related Works ............................ ………………….. 10
2.2 Exchange Broadcasting Scheme, EBS .................... …… …12
2.2.1 Basic Idea .............................. ………………………12
2.3 The EBS Algorithm ............................. …………………….13
2.3.1 EBS Examples ........................... …………………….13
2.3.2 Contention-Free Routing and the Number of Routing
Steps in EBS 14
2.4 Variable Bucket-Based Broadcasting Scheme, VBBS . . . 15
2.4.1 Definition of a Bucket ........................ ………… …15
2.4.2 Communication-Independent, Communication-Dependent, and Communication-Disjoint Buckets ........................... 16
2.4.3 Examples............................... …………………………17
2.5 The VBBS Algorithm ............................ ……………………18
2.5.1 VBBS Examples .......................... ………………… 19
2.5.2 Contention-Free Routing in VBBS . . . . . . . . . . . . 20
2.5.3 Number of Routing Steps in VBBS . . . . . . . . . . . . . . . . 22
2.6 Variable Bucket-Based Broadcasting Scheme with All Fastest Nodes, VBB-SWF...................................………………………………... 23
2.6.1 The VBBSWF Algorithm………………………………..24
2.6.2 VBBSWF Examples ......................... ……………………25
2.6.3 Contention-Free Routing and the Number of Routing Steps in VBB-SWF .............................…………………………... 26
3 Analysis, Simulation Results, and Comparison 29
3.1 Performance Analysis........................……………... . 29
3.2 Complexity Analysis ……………............................. 30
3.2.1 EBS Complexity .......................…………… . . 30
3.2. 2 VBBS Complexity ....................…………...... 31
3.2.3 VBBSWF Complexity ........................ …….. 31
3.3 Simulation Results ........................…………… …. 32
3.3.1 Network Size ............................. ……… …..33
3.3.2 Speed Types ...........................…………….. 33
3.3.3 Density..............................……………….. 36
3.3.4 Flits Size ............................... ……………. . 36
3.3.5 Number of the Slowest Workstations . . . . . .. 38
3.3.6 Distribution of the Slowest Workstations . .. 38
3.4 Comparison.................................. …………………… 39
3.4.1 Comparison with CFOOT ...................... … …39
3.4.2 Comparison Examples with CFOOT . . . . . . . . 40
3.4.3 Comparison with OSPF ....................... ………41
4 PART II
Two Sub-Networks Broadcasting Algorithm 43
4.1 A General Broadcasting Model in Two Partitioned Networks . . . . . . 43
4.1.1 Switch-Reduced HNOW.....................…………………… 43
4.2 Three Phases of the General Broadcasting Scheme . . . . . . . . . . . . ….. 45
4.3 How To Construct DCN Algorithm .................……………………….. 45
4.3.1 How to Divide an HNOW into Two Sub-Networks . . . . . . . . . 45
4.3.2 DCN Construction Algorithm .................……………………. 46
4.3.3 Example of the DCN Construction Algorithm . . . . . . . . …. . . 48
4.3.4 Effects and Characteristics of Sub-Trees Rearrangement . . . . . 50
4.3.5 Why DCNs Have No Contention in the Time of Exchanging Messages .............................…………………………………. 50
4.4 Number of Steps to Exchange Messages in DCNs . . . . . . . . . . . …… . . 51
4.4.1 Postorder ID in Roots of Odd-Numbered of Sub-Trees . . . . . . . 51
4.4.2 Number of Steps to Exchange messages in DCNs . . . …... . . . . 51
4.5 Broadcasting on an HNOW Using TWO-VBBS . . . . . ... . . . . ………. 54
4.5.1An Example of TWO-VBBS Comparing to EBS, VBBS, and TWO-EBS................................……………………………… 54
4.6 Broadcasting on a Partially Connected HNOW. . . . . . . . . . . . . . . . …….58
4.6.1 Compact Spanning Tree ....................... ………………………. 58
4.6.2 Algorithm to Obtain a Compact Spanning Tree . . . . . . . . . . . .58
5 Performance Analysis, Simulation Results, and Comparison 61
5.1 Simulation Results and Comparison ..............……………………… 62
5.1.1 Network Size .........................………………………..…….. 63
5.1.2 Speed Types ............................. ……………………………..63
5.1.3 Density..............................………………….. ………………. 64
5.1.4 Number of the Slowest Workstations . . . . . . ……………. . 64
5.1.5 Distribution of the Slowest Workstations . . . .. ……………. 66
5.1.6 Partially Connected HNOWS .................…… …………….. 67
5.2 Comparison……………………………………………. ……… 67
6. Conclusion……………………………………………………………… 71
Appendix A......................……………………………........……………………………………… 76參考文獻 [1] T. E. Anderson, D. E. Culler, and D. A. Patterson.A case for NOW (Networks of Workstations). IEEE micro, 1995.
[2] M. Banikazemi, V. Moorthy, and D. Panda.Efficient collective communication on heterogeneous networks of workstations. In International Conference on Parallel Processing, pages 460–467, 1998.
[3] M. Banikazemi, J. Sampathkumar, S. Prabhu, D. Panda, and P. Sadayappan. Communi-cation modeling of heterogeneous networks of workstations for performance characterization of collective operations. In Heterogeneous Computing Workshop, 1999. (HCW ’99) Proceedings. Eighth , 1999, pages 125–133, 1999.
[4] O. Beaumont, V. Boudet, F. Rastello, and Y. Robert.Matrix multiplication on heterogeneous platforms. IEEE Transactions on Parallel and Distributed Systems, pages 1033–1051, Oct. 2001.
[5] N. J. Boden and D. C. et al. Myrinet: A gigabit-per-second local area network.IEEE Micro, 15(1):62–76, 1995.
[6] A. Clematis, G. Dodero, and V. Gianuzzi.A resource management tool for heterogeneous networks. In Parallel and Distributed Processing, Proceedings of the Seventh Euromicro Workshop, pages 367–373, 1999.
[7] W. J. Dally and C. L. Seitz. The torus routing chip. Journal of Parallel and Distributed Computing, 1(3):187–196, 1986.
[8] J. Flich, P. Lopez, M. P. Malumbers, and J. Duato. Improving the performance of regu-lar networks with source souting. In International Conference on Parallel Processing, Jan. 2000.
[9] R. Horst.Servernet deadlock avoidance and fractahefral topologies. In Proc. Int’l Parallel Processing Symp, Apr. 1996.
[10] C. Huitema. Routing in the Internet, 2nd Edition. Prentice-Hall, Inc., 2000.
[11] S. L. Johnsson and C.-T. Ho. Optimal broadcasting and personalized communication in hypercubes. IEEE Trans. on Computers, pages 1249–1268, Sept. 1999.
[12] J. P. Jones, B. Nitzberg, and B. Hederson.Workload management: more than just job scheduling. In Proceedings of the 3rd IEEE International Conference on Cluster Computing, 2001.
[13] R. Kesavan, K. Bondalapati, and D. K. Panda. Multicast on irregular switched-based networks with wormhole routing. In Int’l Symp. on High Performance Computer Architecture, Feb. 1997.
[14] R. Kesavan and D. K. Panda. Multiple multicast with minimized node contention on wormhole k-ary n-cube networks. IEEE Transaction on Parallel and Distributed Systems, pages 371–393, Apr. 1999.
[15] R. Kesavan and D. K. Panda. Efficient multicast on irregular switch-based cut-through networks with up-down routing. IEEE Transaction on Parallel and Distributed Systems, pages 808–828, Aug. 2001.
[16] R. Libeskind-Hadas and J. Hartline.Efficient multicast in heterogeneous networks of workstations. In Parallel Processing, 2000. Proceedings. 2000 International Workshops on , 2000, pages 403–410, 2000.
[17] R. Libeskind-Hadas, D. Mazzoni, and R. Rajagopalan.Optimal contension-free unicast-based multicasting in switched-based networks of workstations. In Merged IPPS/SPDP Conf., pages 358–364, 1998.
[18] R. Libeskind-Hadas, D. Mazzoni, and R. Rajagopalan.Tree-based multicasting in wormhole-routed irregular topologies. In Merged IPPS/SPDP Conf., pages 244–249, 1998.
[19] C. Lin. Efficient Contention-Free Broadcast in Heterogeneous Network of Worstation with Multiple Send and Recive Speeds. In 8th IEEE International Simposium on Com-puter and communication, pages 1277–1284, 2003.
[20] C. Lin, Y.-C. Tseng, and J.-P. Sheu. Efficient single node broadcast in switched-based network of workstations with network partitioning. In Proceedings Tenth International Conference on Computer Communications and Networks, pages 68–73, 2001.
[21] P. K. Mckinley, H. Xu, A.-H. Esfahanian, and L. Ni.Unicast-based multicast com-munication in wormhole routed networks. IEEE Trans. on Paral. and Distrib. Sys, 5(12):1252–1265, 1994.
[22] L. M. Ni and P. Mckinley.A survey of wormhole routing techiniques in directed net-work. IEEE Computers, 26(2):62–76, 1993.
[23] Olalysne and J. Duato. Fast dynamic reconfiguration in irregular networks. In Interna-tional Conference on Parallel Processing, pages 449–458, 2000.
[24] F.-J. Q. J.-L. S. Rafael Casado, Aurelio Bermudez and J. Duato. Performance evalua-tion of dynamic reconfiguration in high-speed local area networks. In Six International Symposium on High-performance Computer Architecture, 2000.
[25] R. Rastogi, Y. Breitbart, M. Garofalakis, and A. Kumar. Optimal configuration of OSPF aggregates. IEEE/ACM Transactions on Networking, pages 181–194, Apr. 2003.
[26] A. Rosenberg. Sharing partitionable workloads in heterogeneous nows: Greedier is not better. In Proceedings of the 3rd IEEE International Conference on Cluster Computing, 2001.
[27] J.-J. W. S.-H. Yeh and P. Liu. Scheduling multiple multicast for heterogeneous network of workstations with non-blocking message-passing. In 2000 International Workshop on Parallel Processing, 2000.
[28] M. Schroeder et al. Autonet: A high-speed, self-configuring local area network using point-to-point links. IEEE J. on Selected Areas in Communications, 9(8):1318–1335, Oct. 1991.
[29] F. Silla and J. Duato.High performance routing in networks of workstations with irregular topology. IEEE Transaction on Parallel and Distributed Systems, pages 699– 719, July 2000.
[30] F. Silla, J. Duato, A. Sivasubramaniam, and C. Das. Virtual channel multiplexing in networks of workstations with irregular topology. In Int’l Conf. On High Performance Computing, pages 147–154, 1998.
[31] A. Singhal, M. Banikazemi, P. Sadayappan, and D. Panda.Efficient multicast algo-rithms for switch-based irregular heterogeneous networks of workstations. In Parallel and Distributed Processing Symposium., Proceedings 15th International, 2001.
[32] Y.-C. Tseng, S. Gupta, and D. Panda.All-to-all personalized communication in a wormhole-routed torus . IEEE Transaction on Parallel and Distributed Systems, pages 498–505, May 1996.
[33] Y.-C. Tseng, T.-H. Lin, S. Gupta, and D. Panda.Optimal complete exchange on wormhole-routed 2D/3D torus networks: a diagonal-propagation approach . IEEE Transaction on Parallel and Distributed Systems, pages 380–389, Apr. 1997.
[34] Y.-C. Tseng, D. K. panda, and T.-H. Lai. A trip-based multicasting model in wormhole-routed networks with virtual channels . IEEE Transaction on Parallel and Distributed Systems, pages 138–150, Feb. 1996.
[35] Y.-C. Tseng and J.-P. Sheu.Toward optimal broadcast in star graph using multiple spanning trees. IEEE Transaction on Parallel on Computers, pages 593–599, May 1997.
[36] Y.-C. Tseng, S.-Y.Wang, and C.-W. Ho. Efficient single-node broadcasting in wormhole-routed multicomputers: A network-partioning approach. In IEEE Trans. on Paral. and Distrib. Sys, Jan. 1999.
[37] C.-M. Wang and C.-Y. Ku.A Near-Optimal broadcast broadcasting algorithm in all-port wormhole-routed hypercubes. In Proceedings Acm International Conference on Supercomputing, pages 147–153, 1995.
[38] S.-Y. Wang, Y.-C. Tseng, and C.-W. Ho.Efficient multicast in wormhole-routed 2D mesh/torus multicomputers: a network-partitioning approach. In Frontiers of Massively Parallel Computing, pages 42–49, 1996.
[39] L. Xiao, S. Chen, and X. Zhang. Dynamic cluster resource allocations for jobs with known and unknown memory demands. IEEE Transactions on Parallel and Distributed Systems, pages 223–240, Mar. 2002.
[40] L. Xiao, X. Zhang, and Y. Qu. Effective load sharing on heterogeneous networks of workstations. In Parallel and Distributed Processing Symposium, 2000. IPDPS 2000. Proceedings. 14th International, 2000, pages 431–438, 2000.指導教授 許健平(Jang-Ping Sheu) 審核日期 2005-5-12 推文 plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
網路書籤 Google bookmarks
del.icio.us
hemidemi
facebook
twitter
google
reddit