(3.238.98.214) 您好!臺灣時間:2021/05/08 11:51
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:沈子皓
研究生(外文):Tzu-Hao Shen
論文名稱:異質叢集系統中廣播及合併排程之最佳化
論文名稱(外文):Broadcast and Reduction Scheduling Optimization for Heterogeneous Systems
指導教授:劉邦鋒
指導教授(外文):Pangfeng Liu
學位類別:碩士
校院名稱:國立中正大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2001
畢業學年度:89
語文別:英文
論文頁數:38
中文關鍵詞:廣播合併
外文關鍵詞:HNOWFNFSNFbroadcastreductionheuristic
相關次數:
  • 被引用被引用:0
  • 點閱點閱:143
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
網路工作站相對於平行計算用的超級電腦來說算是一種相當有效率而且又便宜的選擇。因為這些市面上可買得的處理器越來越便宜而且效能越來越好,所以我們可以以有限的預算來組成一個提供高效能運算的個人電腦或者是工作站叢集。然而在叢集之內的處理器速度快慢可能不同,而這一項的異質性使得去設計一個有效率的集合通訊變得複雜。我們提出了一個演算法稱為 FNF(速度越快的點先送),他可以有效率的去搜尋最佳的廣播排程方式,以及大幅度縮減了搜尋的時間。
雖然這種方法很好,但是我們並不保證在一般的狀況之下他找出來的結果就是最好的,然而我們可以證明 FNF 找出來的結果並不會比最好的慢兩倍以上。
我們根據理論結果發展出了一個探索法來幫忙搜尋廣播最佳排程結果。
同時我們也提出了另一個演算法稱為 SNF(速度越慢的點先送),跟 FNF 一樣,我們利用他來搜尋最佳的合併排程,同樣的我們也發展出了一套探索法來搜尋最佳的合併排程。跟最笨的方法作比較,利用探索法搜尋的結果比起一般的方式足足快了500倍之多。

Network of workstation (NOW) is a cost-effective alternative to
massively parallel supercomputers. As commercially available
off-the-shelf processors become cheaper and faster, it is now
possible to build a PC or workstation cluster that provides high
computing power within a limited budget. However, a cluster may
consist of different types of processors and this heterogeneity
within a cluster complicates the design of efficient collective
communication protocols. This dissertation shows that a simple
heuristic called {fastest-node-first}
(FNF) is very effective in reducing broadcast
time for heterogeneous cluster systems. Despite the fact that FNF
heuristic fails to give the optimal broadcast time for a general
heterogeneous network of workstation, we prove that FNF always
gives the optimal broadcast time in several special cases of
clusters. Based on these special case results, we show that FNF
is an approximation algorithm that guarantees a competitive ratio
of 2. From these theoretical results we also derive techniques to
speed up the branch-and-bound search for the optimal broadcast
schedule in HNOW. Also we show that a simple algorithm called {
slowest-node-first} (SNF) is a very efficient reduction protocol
for heterogeneous clusters. First, we show that SNF is actually an
approximation algorithm with competitive ratio two. In addition,
we show that SNF does give the optimal reduction time when the
cluster consists of two types of processors, and the communication
speed ratio between them is at least two. Finally we apply these
theoretical results to branch-and-bound search and show that they
can reduce the search time by a factor of 500.

1 Introduction 4
2 Communication Model 7
2.1 Broadcast Problem Description . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Reduction Problem Description . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Scheduling Techniques 11
3.1 Fastest-Node-First Scheduling for Broadcast . . . . . . . . . . . . . . . . . 11
3.2 Slowest-Node-First for Reduction . . . . . . . . . . . . . . . . . . . . . . . 12
3.2.1 Sender Dependency and Destination Assignment . . . . . . . . . . . 13
3.3 Slowest-Node-First Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4 Theoretical Results 16
4.1 Main Results for the Broadcast Problem . . . . . . . . . . . . . . . . . . . 16
4.1.1 Fastest Nodes First . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.1.2 Special Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.1.3 Competitive Ratio Analysis . . . . . . . . . . . . . . . . . . . . . . 21
4.1.4 Broadcast for Specified Source . . . . . . . . . . . . . . . . . . . . . 22
4.2 Main Results for Reduction Problem . . . . . . . . . . . . . . . . . . . . . 24
4.2.1 Competitive Ratio . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2.2 Two Types of Processors Case . . . . . . . . . . . . . . . . . . . . . 26
5 Heuristic Search 29
5.1 FNF Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.2 SNF Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
6 Conclusion 33

[1] Message Passing Interface Forum. Mar 1994.
[2] T. Anderson, D. Culler, and D. Patterson. A case for networks of workstations (now).
In IEEE Micro, Feb 1995.
[3] M. Banikazemi, V. Moorthy, and D.K. Panda. Efficient collective communication
on heterogeneous networks of workstations. In Proceedings of International Parallel
Processing Conference, 1998.
[4] A. Bar-Noy, S. Guha, J. Naor, and Schieber B. Multicast in heterogeneous networks.
In Proceedings of the 13th Annual ACM Symposium on theory of computing, 1998.
[5] A. Bar-Noy and S. Kipnis. Designing broadcast algorithms in the postal model for
message-passing systems. Mathematical Systems Theory, 27(5), 1994.
[6] P.B. Bhat, C.S. Raghavendra, and V.K. Prasanna. Efficient collective communication
in distributed heterogeneous systems. In Proceedings of the International Conference
on Distributed Computing Systems, 1999.
[7] M. Dinneen, M. Fellows, and V. Faber. Algebraic construction of efficient networks.
Applied Algebra, Algebraic Algorithms, and Error Correcting codes, 9(LNCS 539),
1991.
[8] J. Bruck et al. Efficient message passing interface(mpi) for parallel computing on
clusters of workstations. Journal of Parallel and Distributed Computing, Jan 1997.
[9] M. R. Garey and D. S. Johnson. Computer and Intractability: A guide to the theory
of NP-Completeness. W. H. Freeman, 1979.
[10] L. Gargang and U. Vaccaro. On the construction of minimal broadcast networks.
Network, 19, 1989.
[11] M. Grigni and D. Peleg. Tight bounds on minimum broadcast networks. SIAM J.
Discrete Math., 4, 1991.
[12] W. Gropp, E. Lusk, N. Doss, and A. Skjellum. A high-performance, portable im-plementation
of the mpi: a message passing interface standard. Technical report,
Argonne National Laboratory and Mississippi State University.
[13] S. M. Hedetniemi, S. T. Hedetniem, and A. L. Liestman. A survey of gossiping and
broadcasting in communication networks. Networks., 18, 1991.
[14] R. Karp, A. Sahay, E. Santos, and K. E. Schauser. Optimal broadcast and summation
in the logp model. In Proceedings of 5th Ann. Symposium on Parallel Algorithms and
Architectures, 1993.
[15] R. Kesavan, K. Bondalapati, and D. Panda. Multicast on irregular switch-based
networks with wormhole routing. In Proceedings of International Symposium on high
performance computer architecture, 1997.
[16] A. L. Liestman and J. G. Peters. Broadcast networks of bounded degree. SIAM J.
Discrete Math., 1, 1988.
[17] P. Liu and T. shen. Broadcast scheduling optimization for heterogeneous cluster sys-tems.
In the 12th Annual ACM Symposium on Parallel Architectures and Algorithms,
2000.
[18] P. Liu and D. Wang. Reduction optimization in heterogeneous cluster environments.
In Proceedings of the International Parallel and Distributed Processing Symposium,
2000.
[19] D. Richards and A. L. Liestman. Generalization of broadcast and gossiping. Net-works,
18, 1988.
[20] J.A. Ventura and X. Weng. A new method for constructing minimal broadcast
networks. Networks, 23, 1993.
[21] D. B. West. A class of solutions to the gossip problem. Discrete Math., 39, 1992.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔