Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/19600
標題: 一個為格網資源拓樸網目化之方形覆蓋方法
A Square Coverage Method for Meshlization of the Grid Resource Topology
作者: 李聖文
Li, Sheng-Wen
關鍵字: grid computing;格網運算;mesh network topology;heuristic algorithm;網目拓樸;啟發式演算法
出版社: 資訊科學與工程學系所
引用: 1. Baker, M., R. Buyya, and D. Laforenza, Grids and grid technologies for wide-area distributed computing. Software: Practice and Experience, 2002. 32(15): p. 1437-1466. 2. Bolc, L. and J. Cytowski, Search methods for artificial intelligence. 1992: Academic Press. 3. Pearl, J., Heuristics: intelligent search strategies for computer problem solving. 1984. 4. Minoli, D., A networking approach to grid computing. 2005: Wiley-Interscience. 5. Schloegel, K., G. Karypis, and V. Kumar, Graph Partitioning for High Performance Scientific Simulations. Chapter 18, Sourcebook of Parallel Computing, Dongarra J, Foster I, Fox G et al. 2003, New York: Morgan Kaufmann Publishers. 6. Chen, J. and V. Taylor, Mesh partitioning for efficient use of distributed systems. 2002. 7. Walshaw, C. and M. Cross, Multilevel mesh partitioning for heterogeneous communication networks. Future generation computer systems, 2001. 17(5): p. 601-623. 8. Pellegrini, F. and J. Roman, Scotch: A software package for static mapping by dual recursive bipartitioning of process and architecture graphs. Lecture Notes in Computer Science, 1996. 1067: p. 493-498. 9. Kumar, S., S.K. Das, and R. Biswas. Graph partitioning for parallel applications in heterogeneous Grid environments. in Parallel and Distributed Processing Symposium., Proceedings International, IPDPS 2002, Abstracts and CD-ROM. 2002. 10. Huang, S., E. Aubanel, and V. Bhavsar, PaGrid: A Mesh Partitioner for Computational Grids. Journal of Grid Computing, 2006. 4(1): p. 71-88. 11. Miller, G., et al., Automatic mesh partitioning, Graph Theory and Sparse Matrix Computation (A. George, JR Gilbert, and JWH Liu, eds.). 1993, Springer-Verlag. 12. Pothen, A., H. Simon, and K. Liou, Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Applic., 1990. 11(3): p. 430-452. 13. Pothen, A., et al. Towards a fast implementation of spectral nested dissection. 1992. 14. Hendrickson, B. and R. Leland, An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM Journal on Scientific Computing, 1995. 16(2): p. 452-469. 15. Heath, M. and P. Raghavan, A Cartesian parallel nested dissection algorithm. TechnicalReport 92-1772, Department of Computer Science, University of Illinois, Urbana, IL, 1992. SIAM Journal on Matrix Analysis and Applications, 1994. 16. Raghavan, P., Line and plane separators. Tech. rep. UIUCDCS-R-93-1794, Department of Computer Science, University of Illinois, Urbana, IL61801, February 1993. 17. Miller, G., S. Teng, and S. Vavasis. A unified geometric approach to graph separators. 1991. 18. Nour-Omid, B., A. Raefsky, and G. Lyzenga, Solving finite element equations on concurrent computers. Parallel computations and their impact on mechanics, 1987: p. 209-227. 19. Bui, T. and C. Jones. A heuristic for reducing fill in sparse matrix factorization. 1993. 20. Cheng, C. and Y. Wei, An improved two-way partitioning algorithm with stable performance [VLSI]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991. 10(12): p. 1502-1511. 21. Hagen, L. and A. Kahng. Fast spectral methods for ratio cut partitioning and clustering. 1991. 22. Hagen, L. and A. Kahng. A new approach to effective circuit clustering. 1992: IEEE Computer Society Press Los Alamitos, CA, USA. 23. Hendrickson, B. and R. Leland. A multilevel algorithm for partitioning graphs. 1995: Citeseer. 24. Garbers, J., H. Promel, and A. Steger. Finding clusters in VLSI circuits. 1990. 25. Mansour, N., et al. Graph contraction for physical optimization methods: a quality-cost tradeoff for mapping data on parallel computers. 1993: ACM New York, NY, USA. 26. Huang, S., E. Aubanel, and V. Bhavsar, Mesh partitioners for computational grids: A comparison. Lecture Notes in Computer Science, 2003: p. 60-68. 27. Wanschoor, R. and E. Aubanel. Partitioning and mapping of mesh-based applications onto computational grids. in Grid Computing, 2004. Proceedings. Fifth IEEE/ACM International Workshop on. 2004. 28. Globus Alliance, http://www/globus.org. 29. Sun Grid Solution-Sun N1 Grid Engine6, http://www.sun.com/software/gridware. 30. National Sciense Foundation Middleware Initiative(NMI), http://www.nsf-middleware.org. 31. Grid Computing and Distributed Systems(GRIDS) Laboratory-Gridbus Middleware, http://www.gridbus.org. 32. Uei-Ren Chen, Jyun Ming Chen, Chien-Hsun Wang, and Woei Lin, Aggregative Resource Topology Generator on Internet-scale Computational Grids, Journal of Information Technology and Applications, Vol. 1, No. 4, March 2007, pp. 239-248. 33. Uei-Ren Chen, Chien-Hsun Wang, and Woei Lin, Average Schedule Length and Resource Selection Policies on Computational Grids, Lecture Notes in Computer Science, Vol. 3947, May 2006, pp.63-72. 34. Waxman, B., Routing of multipoint connections. IEEE journal on selected areas in communications, 1988. 6(9): p. 1617-1622. 35. GT-ITM Project-Modeling Topology of Large Internetworks, http://www.cc.gatech.edu/projects/gtitm/. 36. The Cooperative Association for Internet Data Analysis(CAIDA), http://www.caida.org. 37. Medina, A., et al. BRITE: An approach to universal topology generation. 2001. 38. Johnson, D., et al., Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing, 1974. 3: p. 299. 39. Wu, X., PaGridL User Guide, 2007, http://www.cs.unb.ca/research-groups/gcrp.
摘要: 
格網運算具有多樣性的資源可滿足使用者不同服務需求。由於運算密集(computing-intensive)及通訊密集(communication-intensive)問題則有各自考量的因素來進行資源選擇,所以對於資源選擇策略有所區別。平行處理問題還必須要經由排程方法來將子任務分派至運算格網的運算節點上。然而在一般網路上,資源選擇及工作排程所指派的運算節點座落在網路中不同位置,如何將散亂且能力不均等的運算節點轉換的與交連網路(interconnection network)架構一樣有效率是一個重要問題。
本篇論文主要研究目在於提出一個ISPA演算法來將格網資源拓樸虛擬地轉換至規則的網目拓樸(mesh topology),格網資源拓樸的資源被重新組織於虛擬網目(virtual mesh)之中。我們的演算法中主要分為兩部份,利用排列策略先將大部分的虛擬節點進行指派給運算節點,再使用依附策略將剩餘虛擬節點進行依附。經由彈性的依附策略選擇,虛擬網目上可以呈現不同分配運算能力(通訊能力)狀態。ISPA演算法解決運算導向(通訊導向)的問題。
根據實驗結果得到以下結論,排列策略影響在於區塊排列程序中基本區塊排列方式的多寡,而依附策略影響整體虛擬網目中虛擬節點運算能力變異數及虛擬連結平均通訊能力。在經由適當的資源選擇下,運算導向的依附策略所得到的虛擬節點運算能力變異數小於等於其他依附策略。通訊導向的依附策略所得到的虛擬連結平均通訊能力大於等於其他依附策略。本篇論文所提出的演算法在處理通訊導向問題時,經由適當的排列策略與依附策略選擇下能比PaGrid分割器減少2~7%的通訊量而獲得較好的表現。由於排列程序的演算法複雜度較高,為未來可改進的方向。

Grid computing deals with deploying various computing and network resources for meeting diverse users demands. Each grid-computing problem, either computing-intensive or communication-intensive, has its own requirements in selecting resources. Paralleling a grid-computing problem starts with dividing the problem into several pieces, called subtasks, and allocating grid resources to them. Then computing nodes in different locations are configured in some topology. And this is determined through resource selection and job scheduling. The key to successful resource selection and job scheduling lies in balancing the load of both computation on nodes with different computing power, and communication on the underlying interconnection network that supports the topology. This is a critical issue that has attracted a lot of research attention in the grid-computing area.
In this thesis, we propose the ISPA algorithm to transform a network resource topology of grid into a regular mesh topology. The grid computing resources are organized to form a virtual mesh. The proposed ISPA algorithm consists of two major phases. In the first phase, the majority of the virtual nodes are assigned to some computing nodes by a permuting process. In the second phase, the remaining virtual nodes are assigned through an attaching process. With flexible and versatile choices in attaching nodes, the ISPA algorithm can exert different ways of distributing resources to solve the computing-oriented and communication-oriented problems effectively.
Based on simulation results, we come to the following conclusions. The permuting policy plays an import role in determining the number basic blocks of permutation. The attaching policy has influence on the variance of computational ability of virtual nodes and the average communication ability of virtual links. We find that the computation-oriented policies allow the ISPA algorithm to achieve lower variance of computational ability of virtual nodes than the other policies. We also find that the communication-oriented policies enable the ISPA algorithm to attain higher communication ability of virtual links than the other policies for attaching processes. In respect to dealing with communication-oriented problems, the proposed algorithm shows a significant reduction in communications by 2~7%, compared with the PaGrid. However, the permuting process in ours proposed algorithm requires a high complexity in computation. And this deservers further attention of future research.
URI: http://hdl.handle.net/11455/19600
其他識別: U0005-1307200914375000
Appears in Collections:資訊科學與工程學系所

Show full item record
 

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.