跳到主要內容

臺灣博碩士論文加值系統

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

詳目顯示

: 
twitterline
研究生:涂莉芳
研究生(外文):TU LI-FANG
論文名稱:以維度交換演算法為基礎在具有故障連結線的超立方體多元處理機上做動態負載平衡之研究
論文名稱(外文):A Study of Dynamic Load Balancing in Hypercube Multiprocessors with Link Failures Based on the Dimension Exchange Method
指導教授:洪西進洪西進引用關係高宗萬高宗萬引用關係
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:電機工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2001
畢業學年度:89
語文別:中文
論文頁數:56
中文關鍵詞:動態負載平衡超立方體維度交換方法故障連結線廣播前端和累積
外文關鍵詞:dynamic load balancinghypercubedimension exchange methodfaulty linksbroadcastingprefix sum
相關次數:
  • 被引用被引用:0
  • 點閱點閱:319
  • 評分評分:
  • 下載下載:8
  • 收藏至我的研究室書目清單書目收藏:0
為了要解決因為無法預先估算負載量而使得負載分佈不均勻的問題,動態負載平衡就平行系統的使用效率而言是非常必要的。而針對超立方體系統架構來說,先前已有研究論文提出一種維度交換方法。唯此種方法並不能真正完全平衡系統的負載,該演算法僅能保證最後的最大負載量差值將被限制在log N以下,也就是超立方體的維度大小。在本篇論文中,我們將提出一種新的方法,以將此最大負載量差值縮減至1,並同時提出一種新的動態負載平衡演算法以解決超立方體多元處理機系統中連結線的容錯問題。由於其減少了負載不均勻的現象而使得處理時間縮減,故進而可大大地提昇系統的執行效率。
Dynamic load balancing (DLB) is essential for the efficient use of highly parallel systems when solving non-uniform problems with unpredictable load estimates. Dimension Exchange Method (DEM) has been proposed for the hypercube topology, but it does not fully balance the load-the algorithm only guarantees that the final load difference will be bounded by logN, the dimension of the hypercube. Then we propose a new method which reduces the maximum difference to 1. And we also propose a new dynamic load balancing algorithm for hypercube multicomputers with faulty links. Therefore, we can improve the speedup which results from reduced processing time, which in turn results from reduced nonuniformity.
中文摘要.............................................Ⅰ
英文摘要.............................................Ⅱ
誌謝.................................................Ⅲ
圖表索引.............................................Ⅵ
第一章 緒論...........................................1
1.1 研究動機........................................1
1.2 文獻探討........................................2
1.3 論文方法........................................5
1.4 論文架構 ......................................10
第二章 維度交換方法的介紹 ...........................12
2.1 維度交換基本概念 ..............................12
2.2 維度交換演算法(DEM) ...........................14
2.3 維度交換方法可能的最壞情況.....................16
2.4 維度交換演算法之時間複雜度分析 ................21
第三章 研究方法 .....................................22
3.1 研究方法說明 ..................................22
3.2 我們的維度平衡演算法 ..........................23
3.3 維度平衡方法舉例說明 ..........................25
3.4 維度平衡演算法之時間複雜度分析 ................28
第四章 正確性分析....................................29
4.1 維度平衡研究 ..................................29
4.2 圖例分析 ......................................32
第五章 連結線容錯問題探討............................36
5.1 連結線容錯處理說明 ............................36
5.2 連結線容錯之維度平衡演算法 ....................37
5.3 連結線容錯之維度平衡方法舉例說明 ..............41
5.4 連結線容錯之維度平衡演算法的正確性分析 ........44
5.5 連結線容錯之維度平衡演算法時間複雜度分析 ......46
第六章 結論 .........................................51
參考文獻 ...........................................53
作者簡介 ...........................................57
【1】D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods. Englewood Cliffs, N.J.: Prentice-Hall, 1989.
【2】F. C. H. Lin and R. M. Keller, “The gradient model load balancing method,” IEEE Trans. on Software Eng., vol.13, no.1, Jan. 1987, pp.32-38.
【3】G. Cybenko, “Dynamic load balancing for distributed memory multiprocessors,” Journal of Parallel and Distributed Computing, vol.7, Oct. 1989, pp.279-301.
【4】G. Cybenko and T. G. Allen, “Parallel algorithms for classification and clustering,” Proc. SPIE CAAASP, 1987.
【5】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 multiprocessors,” Parallel and Distributed Processing, 1999. 13th International and 10th Symposium on Parallel and Distributed Processing, 1999. 1999 IPPS/SPDP. Proceedings, 1999, pp.708-712.
【6】J.W. Mao and C.B. Yang, “Prefix computation on faulty hypercubes,” Computer, Communication, Control and Power Engineering. Proceedings, TENCON’93., 1993 IEEE Region 10 Conference on Part: 10000, vol.1, 1993, pp.142-145.
【7】K. G. Shin and Y. Chang, “Load sharing in distributed real-time system with state-change broadcasts,” IEEE Trans. on Comput., vol.38, no.8, Aug. 1989, pp.1124-1142.
【8】K. M. Dragon and J. L. Gustafson, “A low-cost hypercube load balance algorithm,” in Proc. Fourth Conf. Hypercubes, Concurrent Comput. and Appl., 1989, pp.583-590.
【9】K. Nam, J. Seo, S. Lee, and J. Kim. “Synchronous load balancing in hypercube multicomputers with faulty nodes,” Journal of Parallel and Distributed Computing, vol.58, 1999, pp.26-43.
【10】M. H. Willebeek-LeMair and A. P. Reeves, “A general dynamic load balancing model for parallel computers,” Tech. Rep. EE-CEG-89-1, Cornell School of Electrical Engineering, 1989.
【11】M. H. Willebeek-LeMair and A. P. Reeves. “Strategies for dynamic load balancing on highly parallel computers,” IEEE Trans. on Parallel and Distributed Systems. vol.4, no.9, Sept. 1993, pp.979-993.
【12】M. Hailperin, “Load balancing for massivelly-parallel soft-real-time systems,” in Proc. 2nd Symp. Frontiers of Massively Parallel Computation, 1988, pp.159-163.
【13】M. J. Berger, S. Bokhari, “A partioning strategy for non-uniform problems on multiprocessors,” IEEE Trans. on Comput., C-36, vol.5, May 1987, pp.570-580.
【14】M. Wu and W. Shu, “A load-balancing algorithm for n-cubes,” in Proc. 1996 International Conference on Parallel Processing. IEEE Computer Society, 1996, pp.148-155.
【15】M.Y. Wu, and W. Shu, “The direct dimension exchange method for load blancing in k-ary n-cubes,” Parallel and Distributed Processing, 1996., Eighth IEEE Symposium on, 1996, pp.366-369.
【16】N. G. Shivaratri and P. Krueger, “Load distributing for locally distributed systems,” IEEE Comput., Dec. 1992, pp.33-44.
【17】S. Park and B. Bose, “Broadcasting in hypercubes with link/node failures,” Frontiers of Massively Parallel Computation, 1992.,Fourth Symposium on the, 1992, pp.286-290.
【18】Y. C. Chang and K. G. Shin, “Load sharing in hypercube-connected multicomputers in the presence of node failures,” IEEE Trans. on Comput., vol.45, no.10, Oct. 1996, pp.1203-1211.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top