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

詳目顯示:::

: 
twitterline
研究生:陳均溢
研究生(外文):Chun-I Chen
論文名稱:利用資料分割來縮短不規則資料重新分配的傳輸時間
論文名稱(外文):Irregular Redistribution Scheduling by Partitioning Messages
指導教授:俞征武俞征武引用關係
指導教授(外文):Chang Wu Yu
學位類別:碩士
校院名稱:中華大學
系所名稱:資訊工程學系碩士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2005
畢業學年度:93
語文別:英文
論文頁數:31
中文關鍵詞:資料重新分配排程邊著色二分圖multi-graphs
外文關鍵詞:data redistributionschedulingedge coloringbipartite graphsmulti-graphs
相關次數:
  • 被引用被引用:0
  • 點閱點閱:101
  • 評分評分:
  • 下載下載:8
  • 收藏至我的研究室書目清單書目收藏:0
許多複雜的科學計算必須仰賴多電腦系統來完成。分散式記憶體的環境下,動態的資料重新分配時讓資料減少搬動與改善演算法效能一直是研究的課題。

規則的資料分配有BLOCK、CYCLIC與BLOCK-CYCLIC(c)三種。不規則的資料分配可以依照使用者的需求分配每台電腦不等的資料量。

資料重新分配所需的成本(時間)分為四種: 計算索引的成本、計算排程的成本、資料的包裝/解包裝的成本與傳送的成本。以往的研究都是在降低前三種成本。然而在不規則的資料重新分配中,同一排程步驟裡,資料量最大的資料,決定此排程步驟的傳送時間。我們提出的演算法,可以將大的資料量切割成許多份,安排在不同的排程步驟來傳送。我們的演算法可以在最小的排程步驟下降低整個排程的時間。當平行運算的電腦越多或最小排程步驟的值(∆)越大或電腦分配到的資料量適當,可以讓傳送的時間降低52%以上。我們的演算法可以運用在任何的資料重新分配上,降低傳送的時間。
Dynamic data redistribution enhances data locality and improves algorithm performance for numerous scientific problems on distributed memory multi-computers systems. Regular data distribution typically employs BLOCK, CYCLIC, or BLOCK-CYCLIC(c) to specify array decomposition. Conversely, an irregular distribution specifies an uneven array distribution based on user-defined functions.

Performing data redistribution consists of four costs: index computational cost, schedule computational cost, message packing/unpacking cost, and data transfer cost. Previous results focus on reducing the former three costs. However, in irregular redistribution, messages with varying sizes are transmitted in the same communication step. Therefore, the largest sized messages in the same communication step dominate the data transfer time required for this communication step. This work presents an efficient algorithm to partition large messages into multiple small ones and schedules them by using the minimum number of steps without communication contention and, in doing so, reducing the overall redistribution time. When the number of processors or the maximum degree of the redistribution graph increases or the selected size of messages is medium, the proposed algorithm can significantly reduce the overall redistribution time to 52%. Moreover, the proposed algorithm can be applied to arbitrary data redistribution while slightly increasing the communication scheduling time.
1. INTRODUCTION 1

2. DEFINITIONS AND NOTATIONS 3

3. GRAPH MODEL AND RELATED WORK 5
3.1 Graph model 5
3.2 Related work 8

4. IRREGULAR REDISTRIBUTION SCHEDULING 10
4.1 Motivation 10
4.2. Selection step 12
4.3 Scheduling step 14
4.4 Partition step 16

5. SIMULATION RESULTS 19

6. CONCLUSIONS AND REMARKS 25

REFERENCES 26

APPENDIX 30
[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] 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.
[4] 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.
[5] Minyi Guo, “Communication Generation for Irregular Codes,” The Journal of Supercomputing, vol. 25, no. 3, pp. 199-214, 2003.
[6] 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.
[7] Minyi Guo, I. Nakata and Y. Yamashita, “Contention-Free Communication Scheduling for Array Redistribution,” Parallel Computing, vol. 26, no.8, pp. 1325-1343, 2000.
[8] Minyi Guo, I. Nakata and Y. Yamashita, “An Efficient Data Distribution Technique for Distributed Memory Parallel Computers,” JSPP'97, pp.189-196, 1997.
[9] 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.
[10] Edgar T. Kalns, and Lionel M. Ni, “Processor Mapping Technique Toward Efficient Data Redistribution,” IEEE Trans. on PDS, vol. 6, no. 12, December 1995.
[11] 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.
[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] 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.
[15] 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.
[16] 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.
[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 Daming Wei, "Divide-and-conquer Algorithm for Irregular Redistributions in Parallelizing Compilers”, The Journal of Supercomputing, vol. 29, no. 2, 2004.
[20] 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.
[21] 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.
[22] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan, London, 1976.
[23] R. Cole and J. Hopcroft, “On edge-coloring bipartite graphs,” SIAM J. Comput. vol. 11, pp. 540-546, 1982.
[24] C. W. Yu and G. H. Chen, “Efficient parallel algorithms for doubly convex-bipartite graphs,” Theoretical Computer Science, vol. 147, pp. 249-265, 1995.
[25] P. Eades, B. D. McKay, and N. C. Wormald, “On an edge crossing problem,” Proc. 9th Australian Computer Science Conference, Australian National University, 1986, pp. 327-334.
[26] N. Tomii, Y. Kambayashi, and Y. Shuzo, “On planarization algorithms of 2-level graphs,” Papers of tech. group on electronic computers, IECEJ, EC77-38, pp. 1-12, 1977.
[27] C. W. Yu, 'On the complexity of the maximum biplanar subgraph problem,' Information Science, vol. 129, pp. 239-250, 2000.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文