1. NCHU Institution Repository
  2. 電機資訊學院
  3. 資訊科學與工程學系所
Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/19837
標題: 計算格網之資源選擇策略與拓樸轉換法
Resource Selection and Topology Transformation on Computational Grids
作者: 陳威仁 
Chen, Uei-Ren 
關鍵字: 格網運算;異質性;計算格網;格網資源拓樸;資源選擇;資源拓樸轉換法;虛擬網目
出版社: 資訊科學與工程學系所
引用: [1] I. Foster and C. Kesselman, Eds., The Grid: Blueprint for a New ComputingInfrastructure, 1st ed. San Francisco, CA, USA: Morgan-Kaufman, July 1998. [2] W. Gentzsch, “Grid computing, a vendor's vision,” in CCGRID '02: Proceed-ings of the 2nd IEEE/ACM International Symposium on Cluster Computingand the Grid, 2002, p. 290. [3] A. Iamnitchi, I. Foster, and D. Nurmi, “A peer-to-peer approach to resourcelocation in grid environments,” in Proceedings of the 11th IEEE InternationalSymposium on High Performance Distributed Computing, August 2002. [4] R. D. Schlichting, A. A. Chien, C. Kesselman, K. Marzullo, J. Plank, and S. K.Shrivastava, “Dependability and the grid: Issues and challenges,” in DSN '02:Proceedings of the 2002 International Conference on Dependable Systems andNetworks, 2002, pp. 263-266. [5] Grid Computing Info Centre (GRID Infoware). [Online]. Available: http://www.gridcomputing.com [6] Globus Alliance. [Online]. Available: http://www.globus.org [7] I. Foster, C. Kesselman, and S. Tuecke, “The anatomy of the grid: Enablingscalable virtual organizations,” Lecture Notes in Computer Science, vol. 2150,2001. [8] R. Buyya, “Grid economy and gridbus toolkit for service-oriented grid comput-ing,” in The 3rd IEEE/ACM. International Symposium on Cluster Computingand the Grid(CCGrid 2003), 2003. [9] Academia Sinica Grid Computing(ASGC) TWGrid. [Online]. Available:http://twgrid.org/ [10] J. Coomer and C. Chaubal, Introduction to the Cluster GridV Part 1.Grid Computing Sun Blueprints Online, August 2002. [Online]. Available:http://www.sun.com/blueprints/0802/816-7444-10.pdf [11] J. Dongarra, I. Foster, G. Fox, W. Gropp, K. Kennedy, L. Torczon, andA. White, Eds., Sourcebook of parallel computing. Morgan Kaufmann Publish-ers Inc., 2003. [12] A. Grama, A. Gupta, G. Karypis, and V. Kumar, Eds., Introduction to ParallelComputing, 2nd ed. Pearson Education Limited, 2003. [13] J. J. Modi, Parallel Algorithms and Matrix Computation. Clarendon Press,1988. [14] G. M. Karniadakis and R. M. Kirby, Parallel Scientific Computing in C++ andMPI. Cambridge University Press, 2003. [15] R. Miller and Q. F. Stout, Parallel algorithms for regular architectures: meshesand pyramids. Cambridge, MA, USA: MIT Press, 1996. [16] A. Gupta and V. Kumar, “The scalability of fft on parallel computers,” IEEETransactions on Parallel and Distributed Systems, vol. 4, pp. 922-932, 1993. [17] D. Nassimi and S. Sahni, “Bitonic sort on a mesh-connected parallel computer,”IEEE Transactions on Computers, vol. 28, pp. 2-7, 1979. [18] A. M. Bruaset and A. Tveito, Numerical Solution of Partial Differential Equa-tions on Parallel Computers (Lecture Notes in Computational Science and En-gineering). Secaucus, NJ, USA: Springer-Verlag New York, Inc., 2006. [19] M. A. Azgomi and R. Entezari-Maleki, “Task scheduling modelling and relia-bility evaluation of grid services using coloured petri nets,” Future GenerationComputer Systems, vol. 26, pp. 1141-1150, October 2010. [20] G. Falzon and M. Li, “Enhancing list scheduling heuristics for dependent jobscheduling in grid computing environments,” The Journal of Supercomputing,pp. 1-27, 2010. [21] S. K. Garg, R. Buyya, and H. J. Siegel, “Time and cost trade-off manage-ment for scheduling parallel applications on utility grids,” Future GenerationComputer Systems, vol. 26, pp. 1344-1355, October 2010. [22] S. Parsa and R. Entezari-Maleki, “Task dispatching approach to reduce thenumber of waiting tasks in grid environments,” The Journal of Supercomputing,pp. 1-17, 2010. [23] Sun Grid Solution - Sun N1 Grid Engine 6. [Online]. Available:http://www.sun.com/software/gridware [24] National Science Foundation Middleware Initiative (NMI). [Online]. Available:http://www.nsf-middleware.org [25] Grid Computing and Distributed Systems (GRIDS) Laboratory - GridbusMiddleware. [Online]. Available: http://www.gridbus.org [26] Dr. Rajkumar Buyya's Internet Home. [Online]. Available: http://www.buyya.Com [27] R. Buyya and M. M. Murshed, “Gridsim: a toolkit for the modeling and simu-lation of distributed resource management and scheduling for grid computing.”Concurrency and Computation: Practice and Experience, vol. 14, no. 13-15, pp.1175-1220, 2002. [28] H. J. Song, X. Liu, D. Jakobsen, R. Bhagwan, X. Zhang, K. Taura, and A. A.Chien, “The microgrid: a scientific tool for modeling computational grids,” inProceedings of the IEEE Supercomputing, Dallas, Texas, USA, November 2000. [29] D. Lu and P. A. Dinda, “Gridg: Generating realistic computational grids,”SIGMETRICS Performance Evaluation Review, vol. 30, no. 4, pp. 33-40, 2003. [30] ——, “Synthesizing realistic computational grids,” in Proceedings of the 2003ACM/IEEE conference on Supercomputing. Washington, DC, USA: IEEEComputer Society, 2003. [31] LINPACK Benchmark Programs and Reports. [Online]. Available: http://www.netlib.org/benchmark [32] Integrated Performance Analysis of Computer System (IPACS) -Benchmarks for distributed computer systems. [Online]. Available:http://www.ipacs-benchmark.org [33] R. C. Teixeira and O. C. M. B. Duarte, “Evaluating the impact of the com-munication system on distributed virtual environments,” Multimedia Tools andApplications, vol. 19, no. 3, pp. 259-278, March 2003. [34] GT-ITM Project - Modeling Topology of Large Internetworks. [Online].Available: http://www.cc.gatech.edu/projects/gtitm/ [35] B. M.Waxman, “Routing of multipoint connections,” IEEE Journal on SelectedAreas in Communications, vol. 6, no. 9, pp. 1617-1622, December 1988. [36] E. W. Zegura, K. L. Calvert, and M. J. Donahoo., “A quantitative compari-son of graph-based models for internet topology,” IEEE/ACM Transactions onNetworking, vol. 5, no. 6, pp. 770-783, December 1997. [37] The Cooperative Association for Internet Data Analysis (CAIDA). [Online].Available: http://www.caida.org [38] A. Medina, A. Lakhina, I. Matta, and J. Byers, “Brite: An approach to uni-versal topology generation,” in Proceedings of the International Workshop onModeling, Analysis and Simulation of Computer and Telecommunications Sys-tems, no. 2001-003, Auguest 2001. [39] M. Faloutsos, P. Faloutsos, and C. Faloutsos, “On power-law relationships ofthe internet topology,” in Proceedings of the conference on Applications, tech-nologies, architectures, and protocols for computer communication. New York,NY, USA: ACM Press, 1999, pp. 251-262. [40] G. Siganos, M. Faloutsos, P. Faloutsos, and C. Faloutsos, “Power laws and theas-level internet topology,” IEEE/ACM Transactions on Networking, vol. 11,no. 4, pp. 514-524, August 2003. [41] M. Ma, J. Wu, S. Li, D. Chen, and Z. Hu, “A grid-distance based scheduling forgrid resource management,” in Proceedings of the Eighth International Confer-ence on High-Performance Computing in Asia-Pacific Region, Beijing, China,2005, pp. 576-581. [42] J. D. Ullman, “Np-complete scheduling problems,” Journal of Computing Sys-tem Science, vol. 10, no. 3, pp. 384-393, 1975. [43] T. L. Adam, K. M. Chandy, and J. R. Dickson, “A comparison of list schedulesfor parallel processing systems,” Commun. ACM, vol. 17, no. 12, pp. 685-690,1974. [44] H. Arikawa, K. Fujikawa, and H. Sunahara, “A node selection mechanism basedon the node usage pattern on campus grid,” in IEEE Pacific Rim Conferenceon Communications, Computers and Signal Processing, 2003. [45] S. Goteti and J. Subhlok, “Communication pattern based node selection forshared networks,” in Proceedings of the Autonomic Computing Workshop, 2003. [46] C. Liu, L. Yang, I. Foster, and D. Angulo, “Design and evaluation of a resourceselection framework for grid applications,” in Proceedings of the 11th IEEEInternational Symposium on High Performance Distributed Computing HPDC-11, 2002. [47] H. Lee, K. Chung, S. Chin, J. Lee, D. Lee, S. Park, and H. Yu, “A resourcemanagement and fault tolerance services in grid computing,” Journal of Paralleland Distributed Computing, vol. 65, no. 11, pp. 1305-1317, 2005. [48] W. Zhang, B. Fang, H. He, H. Zhang, and M. Hu, “Multisite resource selectionand scheduling algorithm on computational grid,” in Proceedings of the 18thInternational Parallel and Distributed Processing Symposium, 2004. [49] P. Z. Kolano, “Surfer: An extensible pull-based framework for resource selec-tion and ranking,” in Fourth IEEE/ACM International Symposium on ClusterComputing and the Grid(CCGrid'04), April 2004. [50] H. Meyerhenke, B. Monien, and T. Sauerwald, “A new diffusion-based multi-level algorithm for computing graph partitions,” Journal of Parallel and Dis-tributed Computing, vol. 69, pp. 750-761, September 2009. [51] A. Rama Mohan Rao, “Parallel mesh-partitioning algorithms for generatingshape optimised partitions using evolutionary computing,” Advances in Engi-neering Software, vol. 40, pp. 141-157, February 2009. [52] I. Ababneh, S. Bani-Mohammad, and M. Ould-Khaoua, “An adaptive jobscheduling scheme for mesh-connected multicomputers,” The Journal of Su-percomputing, vol. 53, pp. 5-25, July 2010.[53] J. Chen and V. E. Taylor, “Mesh partitioning for efficient use of distributed sys-tems,” IEEE Transactions on Parallel and Distributed Systems, vol. 13, no. 1,pp. 67-79, 2002. [54] C. Walshaw and M. Cross, “Multilevel mesh partitioning for heterogeneouscommunication networks,” Future Generation Computer Systems, vol. 17, no. 5,pp. 601-623, 2001. [55] F. Pellegrini and J. Roman, “Scotch: A software package for static mapping bydual recursive bipartitioning of process and architecture graphs,” Lecture Notesin Computer Science, vol. 1067, pp. 493-498, 2006. [56] S. Huang, E. Aubanel, and V. C. Bhavsar, “Pagrid: A mesh partitioner forcomputational grids,” Journal of Grid Computing, vol. 4, no. 1, pp. 71-88,2006. [57] E. G. Coffman, M. R. Garey, and D. S. Johnson, “Approximation algorithmsfor bin packing: a survey,” Approximation algorithms for NP-hard problems,pp. 46-93, 1997. [58] J. Y.-T. Leung, T. W. Tam, and C. S. Wong, “Packing squares into a square,”Journal of Parallel and Distributed Computing, vol. 10, pp. 271 - 275, 1990. [59] Top 500 Supercomputer Sites - Top 500 List. [Online]. Available:http://www.top500.org [60] U. R. Chen, C. H. Wang, and W. Lin, “Average schedule length and resourceselection policies on computational grid,” Lecture Notes in Computer Science,vol. 3947, pp. 63-72, May 2006. [61] Cisco Systems, Inc. [Online]. Available: http://www.cisco.com [62] R. V. Hogg and E. A. Tanis, Probability and Statistical Inference, Fourth Edi-tion. Macmillan, 1993. [63] J. A. Bondy and U. R. Murty, Eds., Graph Theory with Applications. AmericanElsevier Publishing Co., Inc, 1976. [64] ITR, Internet Traffic Report, http://www.internettrafficreport.com/, 2009.[Online]. Available: http://www.internettrafficreport.com/ [65] V. Ahuja, Design and Analysis of Computer Communication Networks. NewYork, NY, USA: McGraw-Hill, Inc., 1982. [66] K. Li, “Job scheduling for grid computing on metacomputers,” in Proceedingsof the 19th IEEE International Parallel and Distributed Processing Symposium,2005. [67] O. Sinnen and L. Sousa, “Communication contention in task scheduling,” IEEETransactions on Parallel and Distributed Systems, vol. 16, no. 6, pp. 503-515,June 2005. [68] GT-ITM project. [Online]. Available: http://www.cc.gatech.edu/projects/gtitm/ [69] Lloyd Allison's DAG Generator. [Online]. Available: http://www.csse.monash.edu.au/∼lloyd/tildeAlgDS/Graph/DAG/ [70] A. V. Aho, R. Sethi, and J. D. Ullman, Compilers: principles, techniques, andtools. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1986. [71] J. Pearl, Heuristics: intelligent search strategies for computer problem solving.Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1984. [72] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction toAlgorithms, Second Edition. The MIT Press, September 2001.
摘要: 
格網運算(grid computing)是未來分散式電腦運算的發展趨勢，因為它透過網路的連結，整合許多異質性(heterogeneous)的計算資源、設備與資料庫，可提供使用者強大的運算能量與資料處理能力。此論文在計算格網(computational grid)領域中提供有用的計算資源的使用與管理技術，論文討論的主題包括以下三個部分：

首先，為了模擬計算格網，作者定義了格網資源拓樸的模型(grid resource topology)，並探討如何將其真實化的議題，以便讓格網資源拓樸能具備現實資源的特性。

第二個主題是研究討論計算格網的資源選擇(resource selection)之策略。探討選擇資源的數量與運算問題模型平行度的限制關係，以及討論不同性質的格網運算問題模型，例如：計算導向(computation-intensive)與通訊導向(communication-intensive)問題。作者以實驗模擬在不同類型的格網環境中，比較這些問題模型所使用資源選擇策略的運算效能。

第三，此論文提出的計算格網之資源拓樸轉換法(resource topology transformation)可有效地將格網資源拓樸轉換成一個虛擬網目(virtual mesh)，此虛擬網目可結合傳統平行處理的演算法與計算格網的能力，以便在計算格網上使用以網目架構為基礎的平行演算法來解決科學計算問題。

最後，針對這三個研究主題，此論文所提供的相關技術與實驗結果，可作為研究計算格網領域的學者們重要的參考依據，而且這些技術將有助於其在計算格網上建立一個解決問題的環境。

Grid computing represents a new paradigm in distributed computing, integrating the heterogeneous computers, networks, databases, scientific instruments, and other resources managed by multiple organizations. Grid technology can provide massive computing power to support applications requiring large-scale computation or data analysis.

This dissertation addresses three major topics related to computational grids. The first topic deals with the characterization of grid resources. The author defines a grid resource model and establishes a workflow to depict the grid resource topology, using a number of probabilistic and statistical techniques. These techniques are then used to approximate the characteristics of grid resources in the real world.

The second topic deals with the selection of resources on computational grids. The author proposes several fundamental policies for grid resource selection and evaluates them according to their performance in scheduling DAG-like problem models. The experiments produces two significant results: the useful number of selected grid resources is strongly bounded by the implicit parallelism of tasks in the problem models; and the scheduling length can be reduced by considering both of computational and communicational costs to solve problems on computational grids.

Thirdly, the author proposes a heuristic transformation algorithm for structuring a set of grid resources in arbitrary topology to form a virtual mesh. The transformation of the virtual mesh enables efficient mapping as well as multiple parallel mesh-structured computations using a given set of grid resources.

Finally, the techniques associated with the three research topics presented in this dissertation provide a solid base from which to construct a problem-solving environment on computational grids.
URI: http://hdl.handle.net/11455/19837
Appears in Collections:資訊科學與工程學系所

Show full item record
 
TAIR Related Article

Google ScholarTM

Check


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