(3.237.178.91) 您好!臺灣時間:2021/03/07 14:50
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:王俊清
研究生(外文):Wang, Chun Ching
論文名稱:叢集格網環境上平行資料切割之理論分析
論文名稱(外文):Theoretical Analysis of Parallel Data Decomposition on Cluster Grid
指導教授:許慶賢
指導教授(外文):Hsu, Ching Hsien
學位類別:碩士
校院名稱:中華大學
系所名稱:資訊工程學系(所)
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:英文
論文頁數:30
中文關鍵詞:多叢集系統格網計算資料重新分配資料切割
外文關鍵詞:Cluster Griddata redistributiondata partitionreduce communication cost
相關次數:
  • 被引用被引用:0
  • 點閱點閱:98
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:13
  • 收藏至我的研究室書目清單書目收藏:0
隨著個人電腦及網路設備在效能上的不斷突破,以及運用大量個人電腦所組合而成的叢集式(Cluster)運算環境的相關軟硬體技術研究不斷的推陳出新,使得叢集式運散環境的實際應用日漸普及;而在實際環境的應用上,隨著計算能力需求的增加及資源的整合運用考量,格網(Grid)便因此應運而生。不同於Cluster,格網運算主要是透過公用的網際網路(Internet),將分散於各地的運算節點,集結成一個具有大量運算能力的系統。在網格環境中,網路的封包交換能力是很重要的一環,在程式執行的過程中有可能發生資料的切割、資料的交換,而這些資料必須透過網際網路傳送到其他的運算節點上,因此,有效的降低外部資料交換,對提升格網運作的效率而言,是一個很重要的研究方向。在傳統的平行電腦與分散式記憶體環境之下,常使用處理器映對(Logical processor mapping)、通訊排程(Communication Scheduling) 、資料切割(Data Partitioning)、資料重新分配(Data Redistribution)等的技術來有效降低處理器交換資料區塊的必要性;而在網格環境中,我們簡略的將資料區塊的傳遞區分為外部交換資料及內部交換資料,由於在同一Cluster內的資料交換,不須要跨越公用的網際網路,所以相對於外部資料的交換,會有較佳的傳送速率,也因此,有效的降低外部資料交換,在格網應用的研究上佔有相當重要的份量。 我們提出了一個演算法,能在有條件的狀況之下,可以達成絕佳的資料區塊切割方式,讓資料不需透過外部交換,完全的保留在區域環境內運算;另外,我們也針對整個格網環境中的運算節點數與資料切割區塊數,做了一些理論上的分析,希望透過這些分析所得的結論跟建議,可以運用在實際的平行運算環境上,用以有效降低通訊時間的成本,提升格網運算的整體效能。
With the development of cheap personal computers and high-speed network devices, clusters have become the trend in the design of high performance computing environments. As the researches of relative hardware and software technology of Cluster and Grid are constantly improving, the application of Cluster is growing popular. Due to information progress and increasing calculation capacity required by all kinds of applications; the calculation needed by these applications have also extended to cross-network calculation. Through the Internet, which connects several Clusters, the mass calculation platform is combined into Cluster Grid. Data partition and exchange which are delivered by network may happen during the executing program and in Cluster Grid environment. Network speed and communication localization therefore are important factors in programming efficiency. In traditional parallel computer and scatter memory environment, logical processor mapping, communication scheduling, data partitioning, data redistribution are often used to reduce the load of processor exchanging data. But in Cluster Grid environment, data delivery of cross-network has not been taken into consideration. The data, delivered in Cluster Grid environment, can be roughly categorized as external exchange and internal exchange. Since internal exchange data in the same cluster need no cross-networking, so the data transmission speed is better and it close to more efficient. In this thesis, we propose a new mathematical method, as a result, that under conditional circumstances, it achieves excellent data partitioning and maintains data calculation in local environment. In addition, we also conduct some theoretical analysis on the amounts of computing nodes under entire Cluster Grid environment and amounts of date partition in the hope that through the analysis, the results could be applied to practical parallel environment and further to reduce communication cost.
1. Introduction ...............................................................1 1.1 Motivation.............................................................1 1.2 Objectives.............................................................2 1.3 Thesis organization....................................................3 2. Related Work................................................................4 3. Data Distribution on Cluster Grid...........................................6 3.1 Identical Cluster Grid Model...........................................6 3.2 Non-identical Cluster Grid Model.......................................7 4. Localized Data Mapping......................................................9 4.1 Motivating Example.....................................................9 4.2 A General Mapping Function for Identical Cluster Grid.................10 4.3 Node Replacement Algorithm for General Cluster Grid...................14 5. Theoretical Analysis.......................................................17 5.1 Interior Communication Upper-Bound....................................17 5.2 External Communication Lower-Bound....................................18 5.3 The Optimal Data Decomposition........................................20 5.4 Communication Patterns Influenced by gcd(P,K).........................21 5.5 Lower-Bound Influenced by gcd(P,K)....................................23 5.6 Lower-Bound Influenced by Clusters' Heterogeneity.....................24 5.6.1 The feature of gcd(P,K) = 1.....................................26 5.6.2 The feature of gcd(P,K) = K > 1.................................26 6. Conclusions and Future Work................................................28 References....................................................................29
1. Taiwan UniGrid, http://unigrid.nchc.org.tw 2. O. Beaumont, A. Legrand and Y. Robert, ”Optimal algorithms for scheduling divisible workloads on heterogeneous systems,” Proceedings of the 12th IEEE Heterogeneous Computing Workshop, 2003 3. Henri E. Bal, Aske Plaat, Mirjam G. Bakker, Peter Dozy, and Rutger F.H. Hofman, “Optimizing Parallel Applications for Wide-Area Clusters,” Proceedings of the 12th International Parallel Processing Symposium IPPS'98, pp 784-790, 1998 4. M. Faerman, A. Birnbaum, H. Casanova and F. Berman, “Resource Allocation for Steerable Parallel Parameter Searches,” Proceedings of GRID’02, 2002 5. J. Blythe, E. Deelman, Y. Gil, C. Kesselman, A. Agarwal, G. Mehta and K. Vahi, “The role of planning in grid computing,” Proceedings of ICAPS’03, 2003 6. J. Dawson and P. Strazdins, “Optimizing User-Level Communication Patterns on the Fujitsu AP3000,” Proceedings of the 1st IEEE International Workshop on Cluster Computing, pp. 105-111, 1999 7. I. Foster, “Building an open Grid,” Proceedings of the second IEEE international symposium on Network Computing and Applications, 2003 8. I. Foster and C. Kessclman, “The Grid: Blueprint for a New Computing Infrastructure,” Morgan Kaufmann, ISBN 1-55860-475-8, 1999 9. I. Foster and C. Kessclman, “Globus: A metacomputing infrastructure toolkit,” Intl. J. Supercomputer Applications, vol. 11, no. 2, pp. 115-128, 1997 10. James Frey, Todd Tannenbaum, M. Livny, I. Foster and S. Tuccke, “Condor-G: A Computation Management Agent for Multi-Institutional Grids,” Journal of Cluster Computing, vol. 5, pp. 237 – 246, 2002 11. Ching-Hsien Hsu, Guan-Hao Lin, Kuan-Ching Li, Chao-Tung Yang, “Localization Techniques for Cluster-Based Data Grid,” ICA3PP 6th Conf., pp.83-92, 2005 12. Saeri Lee, Hyun-Gyoo Yook, Mi-Soon Koo and Myong-Soon Park, “Processor reordering algorithms toward efficient GEN_BLOCK redistribution,” Proceedings of the 2001 ACM symposium on Applied computing, 2001 13. M. Guo and I. Nakata, “A Framework for Efficient Data Redistribution on Distributed Memory Multicomputers,” The Journal of Supercomputing, vol.20, no.3, pp. 243-265, 2001 14. Florin Isaila and Walter F. Tichy, “Mapping Functions and Data Redistribution for Parallel Files,” Proceedings of IPDPS 2002 Workshop on Parallel and Distributed Scientific and Engineering Computing with Applications, Fort Lauderdale, April 2002 15. Jens Koonp and Eduard Mehofer, “Distribution assignment placement: Effective optimization of redistribution costs,” IEEE TPDS, vol. 13, no. 6, June 2002 16. E. T. Kalns and L. M. Ni, “Processor mapping techniques toward efficient data redistribution,” IEEE TPDS, vol. 6, no. 12, pp. 1234-1247, 1995 17. Do-Hyeon Kim and Kyung-Woo Kang, “Design and Implementation of Integrated Information System for Monitoring Resources in Grid Computing,” Computer Supported Cooperative Work in Design, 10th Conf., pp. 1-6, 2006 18. Y. W. Lim, P. B. Bhat and V. K. Parsanna, “Efficient algorithm for block-cyclic redistribution of arrays,” Algorithmica, vol. 24, no. 3-4, pp. 298-330, 1999 19. Liang Peng, M. Koh, Jie Song, S. See, “Grid Service Monitoring for Grid Market Framework,” IEEE ICON 14th Conf., vol. 1, pp. 1-6, 2006 20. Aske Plaat, Henri E. Bal, and Rutger F.H. Hofman, “Sensitivity of Parallel Applications to Large Differences in Bandwidth and Latency in Two-Layer Interconnects,” Proceedings of the 5th IEEE High Performance Computer Architecture HPCA'99, pp. 244-253, 1999 21. Xiao Qin and Hong Jiang, “Dynamic, Reliability-driven Scheduling of Parallel Real-time Jobs in Heterogeneous Systems,” Proceedings of the 30th ICPP, Valencia, Spain, 2001 22. S. Ranaweera and Dharma P. Agrawal, “Scheduling of Periodic Time Critical Applications for Pipelined Execution on Heterogeneous Systems,” Proceedings of the 30th ICPP, Valencia, Spain, 2001 23. A. Smyk, M. Tudruj, L. Masko, “Open MP Extension for Multithreaded Computing with Dynamic SMP Processor Clusters with Communication on the Fly,” PAR ELEC, pp. 83-88, 2006 24. D.P. Spooner, S.A. Jarvis, J. Caoy, S. Saini and G.R. Nudd, “Local Grid Scheduling Techniques using Performance Prediction,” IEE Proc. Computers and Digital Techniques, 150(2): 87-96, 2003 25. M. Tudruj and L. Masko, “Fast Matrix Multiplication in Dynamic SMP Clusters with Communication on the Fly in Systems on Chip Technology,” PAR ELEC, pp. 77-82, 2006 26. Ming Zhu, Wentong Cai and Bu-Sung Lee, “Key Message Algorithm: A Communication Optimization Algorithm in Cluster-Based Parallel Computing,” Proceedings of the 1st IEEE International Workshop on Cluster Computing, 1999
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔