(3.231.230.175) 您好!臺灣時間:2021/04/16 01:18
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:李政宏
論文名稱:CCC平行電腦架構下之完美負載平衡與容錯最佳傳繞設計
論文名稱(外文):Perfect Load Balancing and Fault-Tolerant Optimal Message Routing on Cube-Connected-Cycles Parallel Computers
指導教授:呂紹偉詹景裕詹景裕引用關係
指導教授(外文):Shao-Wei LeuGene Eu Jan
學位類別:博士
校院名稱:國立臺灣海洋大學
系所名稱:電機工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:英文
論文頁數:32
中文關鍵詞:CCC負載平衡容錯傳繞維度交換演算法最短路徑
外文關鍵詞:cube-connected-cyclesperfect load balancefault-tolerant routingdimension exchange methodshortest path
相關次數:
  • 被引用被引用:0
  • 點閱點閱:278
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:13
  • 收藏至我的研究室書目清單書目收藏:0
本論文針對CCC平行電腦架構提出完美負載平衡與最佳容錯傳繞的演算法。CCC架構是一種具規律性的圖形,其結構具有對稱性、規律性、容錯能力以及固定分支度的特質。在平行電腦架構下,當接收到多個任務時必須盡可能平均分配給所有處理節點或電腦進行處理,否則容易造成某些處理節點負載較大,而其餘節點卻處於閒置狀態。由此延伸出兩個重要議題,即負載平衡與容錯傳繞。對於hypercube架構而言,負載平衡演算法大多是基於維度交換演算法,使其每個電腦間所承受的負載量能夠相差最小。我們將基於維度交換的負載平衡演算法運用至CCC架構,為CCC架構提出一個完美負載平衡演算法,使得在CCC架構內的每個處理器節點間的負載差異最多為1,甚至在每個subcube內,處理器節點間的負載差異也是最多為1。負載平衡之外,我們也考慮處理器節點間的訊息傳遞問題。我們提出一個適用於CCC架構的可容錯最佳傳繞演算法,此演算法可以在有多重節點或鏈結失誤但仍存在至少一條路徑的條件下找出起始節點和目的節點之間的最短路徑。此方法是基於放射以及回溯的觀念,保證能找到最短路徑,對處理節點間的訊息流量也只有些微的影響。對於一個包含N個處理器節點的CCC架構而言,此演算法的時間複雜度為 。
A cube-connected-cycles (CCC) is a regular graph, suitable for constructing the interconnection network of parallel or multicomputer/multiprocessor systems. The CCC topology possesses the features of symmetry, regularity, fault tolerance, and fixed degree of the network. This dissertation focuses on two important issues with the CCC-based parallel computers: load balancing and fault-tolerant routing. We propose a simple algorithm to distribute task loads evenly throughout the CCC network. Our algorithm achieves perfect load balance over P processing nodes with a balancing error of at most 1 and the worst-case time complexity of MlogP , where M is the maximum load assigned to each node initially. More importantly, perfect load balance is achieved over the subcubes as well, i.e., once a cube is balanced, if the cube is decomposed into two subcubes by the lowest bit of node addresses, then the difference between the numbers of the total tasks assigned to these subcubes is also at most 1. Besides load balancing, we also consider message exchange among the processors/computers. We propose an optimal routing method which guarantees to find a shortest path between the source and the destination nodes within a faulty CCC-based architecture if such a path exists. The proposed method is based on the concepts of radiation and backtracking and is able to find the shortest path with little impact on the load of the network. The time complexity of our routing methodology is logN , where N is the number of nodes in the CCC architecture.
摘要…………………………………………………………………………..………Ⅰ
Abstract………………………………………………………………………………Ⅱ
List of Figures………………………………………………………………..………Ⅲ
List of Tables…………………………………………………..…………………..…Ⅳ
Notation…………………………………………………………………………...….Ⅴ
CHAPTER 1. INTRODUCTION…….………………………….……………………1
1.1 Research Motivation……...………………………………………..………...1
1.2 Interconnection Networks, Routing, and Load Balancing……..……………2
1.2.1 Hypercube Topology………….……………………………………….2
1.2.2 Fault-Tolerant Routing………………………………………………...3
1.2.3 Load Balancing………………………………………………………..4
1.3 Related Works………………………………………………………………5
1.3.1 Perfect Load Balancing………………………………………………..5
1.3.2 Fault-Tolerant Routing………………………………………………...6
1.4 Dissertation Outline....…………………………..……..………………..……7
CHAPTER 2. PERFECT LOAD BALANCING...……………………....……...….…8
2.1 Definitions and Background………………………………………………….8
2.1.1 The CCC Interconnection Networks…………………………….….....8
2.1.2 Token Distribution Problem………………………………...………..9
2.1.3 Perfect Load Balance………………………………………………..…9
2.1.4 Dimension Exchange Method on Hypercubes…………………….…11
2.1.5 Regular Distributions……………………………………………...…12
2.1.6 The Perfect Load Balancing Algorithm on Hypercubes…………..…14
2.2 The Proposed Algorithm………………………………………………...….14
2.3 Performance Analysis…………...…………………………….…………….16
CHAPTER 3. OPTIMAL FAULT-TOLERANT ROUTING.…….……….…………17
3.1 Fault-Tolerant Routing Algorithm………………………………….……….17
3.1.1 Radiation Phase………………………………………..……………..18
3.1.2 Backtracking Phase………………………………….…...…………..19
3.1.3 Summary……………………………………………………………..19
3.1.4 Routing Algorithm……………………………………………………20
3.2 Illustration of the Proposed Routing Algorithm…………………………….21
3.3 Performance Analysis………………………………………...….………….27
CHAPTER 4. CONCLUSIONS AND FUTURE DEVELOPMENT.......…………...29
References…………………………………...……………………………...………..30
Publication List………………………………...…………………………………….33

1. S. E. Akl, Parallel Computation Models and Methods, Prentice Hall, 1997.
2. B. S. Chlebus, J. D. P. Rolim, and G. Slutzki. “Distributing tokens on a hypercube without error accumulation,” in Proceedings of the IPPS, pp. 573–578, 1996.
3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, the MIT press, 2001.
4. G. Cybenko, “Dynamic load balancing for distributed memory multiprocessors,” Journal of Parallel and Distributed Computing, No. 7, pp. 279–301, 1989.
5. S. P. Dandamudi, Hierarchical Hypercube Multicomputer Interconnection Networks, Ellis Horwood, 1991.
6. J. Dauto, S. Yalamanchili, and L. M. Ni, Interconnection Networks: An Engineering Approach, Morgan Kaufmann, San Francisco, 2003.
7. J.-F. Fang, C.-M. Lee, E.-Y. Yen, R.-X. Chen, and Y.-C. Feng, “Novel broadcasting schemes on cube-connected cycles,” in Proceedings of IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, pp. 629–632, 2005.
8. F. Meyer auf der Heide, B. Osterdiekhoff, and R. Wanka, “Strongly adaptive token distribution,” in Proceedings of the 20th International Colloquium on Automata, Languages, and Programming, pp. 398–409, 1993.
9. G. Fox et al., “Fortran D language specification,” Technical Report COMP TR90-141. Dept. of Computer Science, Rice University, December 1990.
10. P. T. Gaughan and S. Yalamanchili, “Adaptive routing protocols for hypercube interconnection networks,” IEEE Computer, pp. 12–23, 1993.
11. High Performance Fortran Forum. High Performance Fortran Language Specification. Scientific Programming, 2 (1–2): 1–170, 1993.
12. L. H. Hsu and C. K. Lin, Graph Theory and Interconnection Networks, CRC Press, 2009.
13. K. Hwang, Advanced Computer Architecture; Parallelism, Scalability, Programmability, McGraw-Hill, 1993.
14. J. E. Jang, “An optimal fault-tolerant broadcasting algorithm for a cube-connected cycles multiprocessor,” in Proceedings of International Conference on Databases, Parallel Architectures and Their Application, pp. 206–215, 1990.
15. J. JâJâ and K. W. Ryu, “Load balancing and routing on the hypercube and related networks,” Journal of Parallel and Distributed Computing, No. 14, pp. 431–435, 1992.
16. F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, San Mateo, California: Morgan Kaufmann, 1992.
17. G. E. Jan and Y.-S. Hwang, “An efficient algorithm for perfect load balancing on hypercube multiprocessors,” The Journal of Supercomputing, Vol. 25, No. 1, May 2003.
18. G. E. Jan, S.-W. Leu, C.-H. Li, and Xiaoshe Dong, “Perfect load balancing on Cube-Connected Cycles multiprocessors,” WSEAS Transactions on Computer Research, No 1, Vol. 1, pp. 13–18, November 2006.
19. G. E. Jan and M.-B. Lin, “Effective load balancing on highly parallel multicomputers based on superconcentrators,” in Proceedings of the International Conference on Parallel and Distributed Systems, pp. 216–221, 1994.
20. G. E. Jan, S.-W. Leu and C.-H. Li, “On the Array Embeddings and Layout of Quadtrees and Pyramids,” Journal of Information Science and Engineering, Vol. 20, No. 1, pp. 127–141, January 2004.
21. Gene Eu Jan, C.-H. Li, Y.-Y. Chen, and S.-W. Leu, “A Fault-Tolerant Optimal Message Routing Methodology for Cube Connected-Cycles Parallel Computers,” Journal of Marine Science and Technology. (accepted)
22. G. E. Jan and M.-B. Lin, “Concentration, Load Balancing, Partial Permutation Routing and Superconcentration on Cube-Connected Cycles Parallel Computers,” Journal of Parallel and Distributed Computing, No. 65, pp. 1471–1482, September 2005.
23. C.-H. Li, S.-W. Leu and G. E. Jan, “A Mesh-Connected Tree Based Hybrid Peer-to-Peer Network,” in Proceedings of IEEE TENCON 2007, pp. 1–4, 2007.
24. D. S. Meliksetian and C. Y. R. Chen, “Optimal routing algorithm and the diameter of the cube-connected cycles,” IEEE Transactions on Parallel and Distributed Systems, Vol. 4, No. 10, pp. 1172–1178, 1993.
25. B. Parhami, Introduction to Parallel Processing: Algorithms and Architectures, 1999.
26. C. G. Plaxton, “Load balancing, selection and sorting on the hypercube,” in Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, pp. 64–73, 1989.
27. F. Preparata and J. Vuillemin, “The cube-connected cycles: a versatile network for parallel computation,” Communications of the ACM, Vol. 24, No. 5, pp. 300–309, May 1981.
28. S. Raghavendra, C. S. Chalasani, and R. V. Boppmana, “Improved algorithms for load balancing in circuit switching hypercubes,” in Proceedings of the 5th International Parallel Processing Symposium, pp. 537–542, 1991.
29. S. Ranka and S. Sahni, Hypercube Algorithms with Applications to Image Processing and Pattern Recognition, Springer Verlag, 1990.
30. S. Ranka, Y. Won, and S. Sahni, “Programming a hypercube multicomputer,” IEEE Software, pp. 69–77, 1988.
31. H. Rim, J.-W. Jang, and S. Kim, “An efficient dynamic load balancing using the dimension exchange method for balancing of quantized loads on hypercube multiprocessor,” in Proceedings of 13th International Parallel Processing Symposium, pp. 708–712, 1999.
32. I. D. Scherson, and A. S. Youssef, Interconnection Networks for High-Performance Parallel Computers, IEEE Computer Society Press, 1994.
33. B. A. Shirazi, A. R. Hurson, and K. M. Kavi, Scheduling and Load Balancing in Parallel and Distributed Systems, IEEE Computer Society Press, 1995.
34. A. Singh, “Load balancing routing in interconnection networks,” Ph.D. Dissertation. Dept. of Electrical Engineering, Stanford University, March 2005.
35. J. Song, Z. Hou, and Y. Shi, “An optimal multicast algorithm for cube-connected cycles,” Journal of Computer Science and Technology, Vol. 15, No. 6, pp. 572–583, 2000.
36. A. S. Tanenbaum and D. J. Wetherall, Computer Networks, Prentice Hall, 2010.
37. A. Varma and C. S. Raghavendra, Interconnection Networks for Multiprocessors and Multicomputers Theory and Practice, IEEE Computer Society Press, 1994.
38. J. Woo and S. Sahni, “Load balancing on a hypercube,” in Proceedings of the 5th International Parallel Processing Symposium, pp. 525–530, 1991.
39. C.-L. Wu, and T.-Y. Feng, Tutorial: Interconnection Networks for Parallel and Distributed Processing, IEEE Computer Society Press, 1984.
40. C. Xu and Francis C. M. Lau, Load Balancing in Parallel Computers Theory and Practice, Kluwer Academic Publishers, 1996.
41. J. Xu, Topological Structure and Analysis of Interconnection Networks, Kluwer Academic Publishers, 2001.
42. C. Yao, K. Li, K. Lin, and Y. Shen, “Load balancing on the exchanged hypercube,” in Proceedings of 2009 Fourth ChinaGrid Annual Conference, pp. 32–35, 2009.
43. A. Y. Zomaya, Parallel and Distributed Computing Handbook, McGraw-Hill, 1996.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔