跳到主要內容

臺灣博碩士論文加值系統

(44.213.63.130) 您好!臺灣時間:2023/02/03 15:58
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:藍朝陽
研究生(外文):Chao-Yang Lan
論文名稱:不規則資料重排之通訊排程技術
論文名稱(外文):On Improving Scheduling Stability for Irregular Data Redistribution On Improving Scheduling Stability for Irregular Data Redistribution Based on Local Message Reduction
指導教授:許慶賢
指導教授(外文):Ching-Hsien Hsu
學位類別:碩士
校院名稱:中華大學
系所名稱:資訊工程學系碩士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:中文
論文頁數:28
中文關鍵詞:異質性訊息排程LMR資料重新配置HPF2GEN_BLOCK
外文關鍵詞:Message SchedulingLMRData RedistributionHPF2GEN_BLOCK.
相關次數:
  • 被引用被引用:0
  • 點閱點閱:108
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
分散式記憶體電腦叢集系統的龐大運算能力已普遍用來解決大型科學運算的問題。在資料平行化程式技術日益成熟,資料重新分配的研究議題從規則的延伸到不規則的,由同質性系統轉移到上的異質性系統。High Performance Fortran Version 2 (HPF2) 提供 GEN_BLOCK (generalized block)配置方式來因應不規則的分配方式。在最近幾年,有著名三篇論文提出在電腦叢集環境的資料重新分配演算法。本篇論文提出一個可改善這三個演算法的技術。資料重新分配的技術改善計算節點在程式執行期間彼此交換資料的成本。在過去所探討的演算法都僅針對資料大小給予同等比例的成本進行資料傳輸排程,忽略傳輸速度的因素可能導致排程演算法的理論分析與實際執行結果無法全然呼應。本論文考慮計算節點內傳輸與其他節點透過網路有著不同傳輸速度進行改善。將傳輸速度的差異適當的對應到傳輸成本上時,在實驗中可以發現,排成演算法得到了明顯的改善。實驗結果也證明本篇論文所提出來的演算法是可以套用在不同的資料重新配置演算法中。
Large-scale scientific problems have been solved on distributed memory multi-computers with powerful computing ability. As the parallel system techniques growing up, the regular data redistribution issues are extended to irregular issues, researches on homogeneous systems are extended to heterogeneous systems. High Performance Fortran Version 2 (HPF2) provides GEN_BLOCK (generalized block) format to map onto irregular mapping function. Recently, three irregular data redistribution algorithms on cluster were proposed. In this thesis, a technique is proposed to improve the irregular data redistribution algorithms. The redistribution techniques reduce the cost of data communication when executing programs. In the past, the theoretical cost of communication is proportion to data size. The factor of transmitting rates is ignored, thus the experiments may be different from theoretical results. In this thesis, the proposed technique considers the transmitting rate in a node is different from that between node and node. After considering the difference and proposing a new cost model, the proposed technique helps scheduling better results. The improvements on irregular data redistribution algorithms are shown in experiments. The experiments show the proposed technique improves all scheduling algorithms.
Chinese Abstract I
Abstract II
Acknowledgements III
Table of Contents IV
List of Figures V
1 Introduction 1
2 Related Work 4
3 Implementations of Irregular Data Redistribution 6
3.1 Coloring Scheduling Mechanism 6
3.2 List Scheduling Algorithm 8
3.3 Divide-and-Conquer Scheduling Algorithm 9
4 GEN_BLOCK Array Redistribution Scheduling Algorithm 11
4.1 Preliminary 11
4.2 Local Message Reduction 14
5 Communication Scheduling 17
5.1 Simulation Comparison 17
5.2 Experimental Results 23
6 Conclusions and Future Work 25
References 26
[1]G. Bandera and E.L. Zapata, “Sparse Matrix Block-Cyclic Redistribution,” Proceeding of IEEE Int'l. Parallel Processing Symposium (IPPS'99), San Juan, Puerto Rico, April 1999.
[2]Frederic Desprez, Jack Dongarra and Antoine Petitet, “Scheduling Block-Cyclic Data redistribution,” IEEE Trans. on PDS, vol. 9, no. 2, pp. 192-205, Feb. 1998.
[3]Minyi Guo and I. Nakata, “A Framework for Efficient Array Redistribution on Distributed Memory Multicomputers,” The Journal of Supercomputing, vol. 20, no. 3, pp. 243-265, 2001.
[4]Minyi Guo, I. Nakata and Y. Yamashita, “Contention-Free Communication Scheduling for Array Redistribution,” Parallel Computing, vol. 26, no.8, pp. 1325-1343, 2000.
[5]Minyi Guo, I. Nakata and Y. Yamashita, “An Efficient Data Distribution Technique for Distributed Memory Parallel Computers,” JSPP'97, pp.189-196, 1997.
[6]Minyi Guo, Yi Pan and Zhen Liu, “Symbolic Communication Set Generation for Irregular Parallel Applications,” The Journal of Supercomputing, vol. 25, pp. 199-214, 2003.
[7]C.-H Hsu, S.-W Bai, Y.-C Chung and C.-S Yang, “A Generalized Basic-Cycle Calculation Method for Efficient Array Redistribution,” IEEE TPDS, vol. 11, no. 12, pp. 1201-1216, Dec. 2000.
[8]C.-H Hsu, Dong-Lin Yang, Yeh-Ching Chung and Chyi-Ren Dow, “A Generalized Processor Mapping Technique for Array Redistribution,” IEEE Transactions on Parallel and Distributed Systems, vol. 12, vol. 7, pp. 743-757, July 2001.
[9]Edgar T. Kalns, and Lionel M. Ni, “Processor Mapping Technique Toward Efficient Data Redistribution,” IEEE Trans. on PDS, vol. 6, no. 12, December 1995.
[10]S. D. Kaushik, C. H. Huang, J. Ramanujam and P. Sadayappan, “Multiphase data redistribution: Modeling and evaluation,” Proceeding of IPPS’95, pp. 441-445, 1995.
[11]Shih-Chang Chen, Ching-Hsien Hsu, Chao-Yang Lan, Chao-Tung Yang and Kuan-Ching Li, "Efficient Communication Scheduling Methods for Irregular Array Redistribution in Parallelizing Compilers," Lecture Notes in Computer Science, Vol. 3606, pp. 216-225, Springer-Verlag, Sep. 2005. (PaCT’05).
[12]S. Lee, H. Yook, M. Koo and M. Park, “Processor reordering algorithms toward efficient GEN_BLOCK redistribution,” Proceedings of the ACM symposium on Applied computing, 2001.
[13]Y. W. Lim, Prashanth B. Bhat and Viktor and K. Prasanna, “Efficient Algorithms for Block-Cyclic Redistribution of Arrays,” Algorithmica, vol. 24, no. 3-4, pp. 298-330, 1999.
[14]Antoine P. Petitet and Jack J. Dongarra, “Algorithmic Redistribution Methods for Block-Cyclic Decompositions,” IEEE Trans. on PDS, vol. 10, no. 12, pp. 1201-1216, Dec. 1999.
[15]L. Prylli and B. Touranchean, “Fast runtime block cyclic data redistribution on multiprocessors,” Journal of Parallel and Distributed Computing, vol. 45, pp. 63-72, Aug. 1997.
[16]Neungsoo Park, Viktor K. Prasanna and Cauligi S. Raghavendra, “Efficient Algorithms for Block-Cyclic Data redistribution Between Processor Sets,” IEEE Transactions on Parallel and Distributed Systems, vol. 10, No. 12, pp.1217-1240, Dec. 1999.
[17]S. Ramaswamy, B. Simons, and P. Banerjee, “Optimization for Efficient Data redistribution on Distributed Memory Multicomputers,” Journal of Parallel and Distributed Computing, vol. 38, pp. 217-228, 1996.
[18]Akiyoshi Wakatani and Michael Wolfe, “Optimization of Data redistribution for Distributed Memory Multicomputers,” short communication, Parallel Computing, vol. 21, no. 9, pp. 1485-1490, September 1995.
[19]Hui Wang, Minyi Guo and Wenxi Chen, “An Efficient Algorithm for Irregular Redistribution in Parallelizing Compilers,” Proceedings of 2003 International Symposium on Parallel and Distributed Processing with Applications, LNCS 2745, 2003.
[20]Hui Wang, Minyi Guo and Daming Wei, "Divide-and-conquer Algorithm for Irregular Redistributions in Parallelizing Compilers”, The Journal of Supercomputing, vol. 29, no. 2, 2004.
[21]Hui Wang, Minyi Guo and Daming Wei, “Message Scheduling for Irregular Data Redistribution in Parallelizing Compilers,” IEICE Transactions on Information and Sysmtes, Vol. E89-D, No. 2, pp. 418--424, February, 2006.
[22]H.-G. Yook and Myung-Soon Park, “Scheduling GEN_BLOCK Array Redistribution,” Proceedings of the IASTED International Conference Parallel and Distributed Computing and Systems, November, 1999.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top