Please use this identifier to cite or link to this item:
DC FieldValueLanguage
dc.contributor.authorLi, Sheng-Wenen_US
dc.identifier.citation1. 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/ 29. Sun Grid Solution-Sun N1 Grid Engine6, 30. National Sciense Foundation Middleware Initiative(NMI), 31. Grid Computing and Distributed Systems(GRIDS) Laboratory-Gridbus Middleware, 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, 36. The Cooperative Association for Internet Data Analysis(CAIDA), 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,
dc.description.abstract格網運算具有多樣性的資源可滿足使用者不同服務需求。由於運算密集(computing-intensive)及通訊密集(communication-intensive)問題則有各自考量的因素來進行資源選擇,所以對於資源選擇策略有所區別。平行處理問題還必須要經由排程方法來將子任務分派至運算格網的運算節點上。然而在一般網路上,資源選擇及工作排程所指派的運算節點座落在網路中不同位置,如何將散亂且能力不均等的運算節點轉換的與交連網路(interconnection network)架構一樣有效率是一個重要問題。 本篇論文主要研究目在於提出一個ISPA演算法來將格網資源拓樸虛擬地轉換至規則的網目拓樸(mesh topology),格網資源拓樸的資源被重新組織於虛擬網目(virtual mesh)之中。我們的演算法中主要分為兩部份,利用排列策略先將大部分的虛擬節點進行指派給運算節點,再使用依附策略將剩餘虛擬節點進行依附。經由彈性的依附策略選擇,虛擬網目上可以呈現不同分配運算能力(通訊能力)狀態。ISPA演算法解決運算導向(通訊導向)的問題。 根據實驗結果得到以下結論,排列策略影響在於區塊排列程序中基本區塊排列方式的多寡,而依附策略影響整體虛擬網目中虛擬節點運算能力變異數及虛擬連結平均通訊能力。在經由適當的資源選擇下,運算導向的依附策略所得到的虛擬節點運算能力變異數小於等於其他依附策略。通訊導向的依附策略所得到的虛擬連結平均通訊能力大於等於其他依附策略。本篇論文所提出的演算法在處理通訊導向問題時,經由適當的排列策略與依附策略選擇下能比PaGrid分割器減少2~7%的通訊量而獲得較好的表現。由於排列程序的演算法複雜度較高,為未來可改進的方向。zh_TW
dc.description.abstractGrid 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.en_US
dc.description.tableofcontents誌謝 i 摘要 ii Abstract iii 目錄 iv 圖目錄 vi 表目錄 viii 第一章 簡介 1 1.1 研究動機 1 1.2 章節組織 2 第二章 背景知識與相關研究 3 2.1 啟發式搜尋法(Heuristic search method) 3 2.2 網目拓樸(Mesh topology) 4 2.3 網目分割(Mesh partition) 4 2.3.1 分割器分類 5 2.3.2 PaGrid分割器 6 2.4 格網環境工具 6 2.5 比較格式轉換 7 第三章 ISPA演算法架構 9 3.1 初始程序(Initial process) 10 3.1.1 虛擬網目與覆蓋區塊定義 10 3.1.2 格網資源拓樸定義 13 3.1.3 分配區塊行為 17 3.2 縮小程序(Shrinking process) 18 3.2.1 門檻值定義 18 3.2.2 縮小區塊行為 18 3.3 排列程序(Permuting process) 22 3.3.1 樹狀搜尋樹與評估值定義 22 3.3.2 覆蓋排列區塊行為 23 3.4 依附程序(Attaching process) 28 3.4.1 條件值定義 28 3.4.2 依附虛擬節點行為 28 第四章 效能討論與比較 35 4.1 效能參數介紹 35 4.1.1 PaGrid輸入參數 35 4.1.2 效能參數定義 38 4.2 模擬結果 40 4.2.1 ISPA效能討論 40 4.2.2 ISPA與PaGrid效能比較 56 參考文獻 65zh_TW
dc.subjectgrid computingen_US
dc.subjectmesh network topologyen_US
dc.subjectheuristic algorithmen_US
dc.titleA Square Coverage Method for Meshlization of the Grid Resource Topologyen_US
dc.typeThesis and Dissertationzh_TW
item.openairetypeThesis and Dissertation-
item.fulltextno fulltext-
Appears in Collections:資訊科學與工程學系所
Show simple item record

Google ScholarTM


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