臺灣博碩士論文加值系統

格網運算是分散式平行運算中一個新的研究課題.格網運算平台試著去整合網路上大量分散且異質的運算及資料儲存資源,以形成一個虛擬的超級電腦. 因而此超級電腦的運算效能與所整合的資源個別的運算能力及資源間的網路傳輸狀況有很大的關係.既使是同一個程式在不同的時候執行,其使用的資源配置也可能有很大的不同,進而影響到其執行的效能.雖然現今有許多針對各種不同平行運算平台的資源配置方式及演算法被提出.然而,由於各資源的運算能力及網路傳輸狀況的高度動態變化的特性,這些資源配置演算法必須作進一步的修正以符合格網運算平台的需要.在這篇論文中,我們提出運用模擬的方式來幫助資源的管理,並且探討使用這種模擬方法的效率和可行性.為了達到此目的,我們設計並且實作了一個可延伸的計算及排程系統,使一個平行的程式能以相同的排程方法,在此系統中以實際或模擬的模式執行,進而分析其執行效能.此外,新的排程演算法也可以在此系統上發展與研究.為了驗證我們所提方法的實用性,我們使用Grid-NPB中不同的benchmark做為對象,探討這些benchmark在不同的環境下的執行結果.雖然更廣泛的實驗仍需進行,不過初期的實驗結果顯示,在許多情況下我們的方法對平行程式的效能提升能提供有效的幫助.

Grid computing is emerging as a new parallel and distributed computing discipline that attempts to bring world-wide computing resources into a gigantic virtual supercomputing machine. Unlike traditional platforms, the capabilities and power of these computing resources as well as the communication speed between them vary dramatically. As a result, different runs of the same grid program may perform differently, and proper resource allocation and management becomes crucial to make effective use of the resources involved. Today many resource allocation approaches have been proposed and put to use in various grid computing platforms, each employs different kind of heuristics. However, because of the high variation of the performance characteristics of the underlying resources, making proper resource allocation decisions is by no means trivial.
In this thesis we propose to use simulation techniques as a means to help resource management, and investigate the effectiveness and feasibility of our proposal. In particular, we design and implement an extensible framework for distributed computing and scheduling, where parallel programs can execute in both real-time and simulation modes using the same scheduling policy. Moreover, new scheduling algorithms can be developed and their performance studied. To assess the usefulness of our approach, we investigate the impact of several scheduling algorithms on different classes of problems using the Grid-NPB benchmarks. Although more extensive experiments are needed, initial experiment results show that our approach can be significant under certain circumstances

List of Figures........................................................................................- 5 -
1. Introduction........................................................................................- 7 -
2. Background and Related Work..........................................................- 8 -
3. The Task Scheduling Framework......................................................- 11 -
3.1 A Service-Oriented Architecture.............................................- 11 -
3.2 Framework Overview..............................................................- 12 -
3.3 Scheduling Framework Design................................................- 14 -
3.4 Workflows and Task-Graphs...................................................- 17 -
3.4.1 Workflows.....................................................................- 17 -
3.4.2 Task Graphs...................................................................- 18 -
4. Experiments........................................................................................- 19 -
4.1 Scheduling Algorithms..............................................................- 20 -
4.2 Machine and Network Load......................................................- 21 -
4.3 Benchmarks: Grid-NPB............................................................- 22 -
4.4 Simulation Results.....................................................................- 32 -
5. Conclusions..........................................................................................- 53 -
References................................................................................................- 53 -

[Nakai] Junko Nakai, Rob F. Van Der Wijngaart, “Applicability of Markets to Global Scheduling in Grids”, NAS Technical Report NAS-03-004
[Wijngaart01] Rob F. Van der Wijngaart, Michael Frumkin, “Benchmarking Grid Environments at the User Level”, GGF3, Oct 7-10, 2001
[Wijngaart02a] R. F. Van der Wijngaart and M. A. Frumkin, “NAS Grid Benchmarks Version 1.0”, NAS Technical Report NAS-02-005
[Wijngaart02b] Rob Van Der Wijngaart, “NAS Parallel Benchmarks Version 2.4”, NAS Technical Report NAS-02-007
[Wijngaart04] Rob F. Van der Wijngaart, “Evaluating the Information Power Grid using the NAS Grid Benchmarks”, 18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Workshop 17 p. 275b
[Frumkin01] Michael Frumkin, Rob F. Van der Wijngaart, “NAS Grid Benchmarks: A Tool for Grid Space Exploration”, 10th IEEE International Symposium on High Performance Distributed Computing (HPDC-10'01) p.0315
[Frumkin02] Michael Frumkin, Matthew Schultz, Haoqiang Jin, and Jerry Yan, “Implementation of the NAS parallel benchmarks in Java”, NAS-02-009, NASA Ames Research Center.
[Frumkin03] Michael Frumkin, Robert Hood, “Using Grid Benchmarks for Dynamic Scheduling of Grid Applications”. NAS Technical Report NAS-03-015
[Rob05]Rob F. Van der Wijngarrt, Michael Frumkin, "NAS Grid Benchmarks Version 1.0", NASA Technical Report NAS-02-005
[Wong02] Parkson Wong, Rob F. Van der Wijngaart, “NAS Parallel Benchmarks I/O Version 2.4”, NAS Technical Report NAS-03-002
[Bailey94] D. Bailey, E. Barszcz, J. Barton, D. Browning, R. Carter, L. Dagum, R. Fatoohi, S. Fineberg, P. Frederickson, T. Lasinski, R. Schreiber, H. Simon, V. Venkatakrishnam and S. WeeraTunga, “The NAS PARALLEL BENCHMARKS”, RNR Technical Report RNR-94-007, March 1994
[Buyya00a]Rajkumar Buyya, David Abramson and Jonathan Giddy, “Nimrod/G: An Architecture for a Resource Management and Scheduling System in a Global Computational Grid”, hpc, p. 283, The Fourth International Conference on High-Performance Computing in the Asia-Pacific Region-Volume 1, 2000.
[Buyya02a] Rajkumar Buyya, Manzur Murshed, and David Abramson, “A Deadline and Budget Constrained Cost-Time Optimization Algorithm for Scheduling Task Farming Applications on Global Grids”, Proceedings of the 2002 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'02)
[Buyya02b] Rajkumar Buyya and Manzur Murshed2, “GridSim: a toolkit for the modeling and simulation of distributed resource management and scheduling for Grid computing” Concurrency Computat.: Pract. Exper. 2002; 14:1175–1220.
[Phatanapherom] Sugree Phatanapherom , Putchong Uthayopas, and Voratas Kachitvichyanukul, “FAST SIMULATION MODEL FOR GRID SCHEDULING USING HYPERSIM”, Proceedings of the 2003 Winter Simulation Conference
[Sulistio05] Anthony Sulistio , Gokul Poduvaly, Rajkumar Buyya , and Chen-Khong Thamy, “Constructing A Grid Simulation with Differentiated Network Service Using GridSim”, Proceedings of the 6th International Conference on Internet Computing (ICOMP'05), June 27-30, 2005, Las Vegas, USA.
[Sulistio03] Anthony Sulistio, Chee Shin Yeo, and Rajkumar Buyya, “Visual Modeler for Grid Modeling and Simulation (GridSim) Toolkit”, P.M.A. Sloot et al. (Eds.): ICCS 2003, LNCS 2659, pp. 1123–1132, 2003.
[Sherwani04] Jahanzeb Sherwani, Nosheen Ali, Nausheen Lotia, Zahra Hayat, and Rajkumar Buyya, “Libra: a computational economy-based job scheduling system for clusters”, Softw., Pract. Exper. 34(6): 573-590 (2004)
[Liu03] Xin Liu and Andrew A. Chien. “Traffic-based Load Balance for Scalable Network Emulation”. Conference on High Performance Networking and Computing: Proceedings of the 2003 ACM/IEEE conference on Supercomputing, page 40
[Gallop98] J. Weissman. Gallop, “The benefits of wide-area computing for parallel processing”, Technical report, University of Texas at San Antonio, 1997.
[Murshed02] Manzur Murshed and Rajkumar Buyya, “Using the GridSim Toolkit for Enabling Grid Computing Education”, International Conference on Communication Networks and Distributed Systems Modeling and Simulation (CNDS 2002), January 27-31, 2002, San Antonio, Texas, USA.
[Song X00] H. J. Song X. Liu D. Jakobsen R. Bhagwan X. Zhang K. Taura A. Chien. “The MicroGrid: a Scientific Tool for Modeling Computational Grids”, In Proceedings of SC'2000, Dallas, Texas
[Frey01]J. Frey, T. Tannenbaum, I. Foster, M. Livny, and S. Tuecke, "condor-g: A computation management agent for multiinstitutional grids", In Proceedings of the Tenth IEEE Symposium on High Performance Distributed Computing (HPDC10), pages 55--63, San Francisco, CA, August 2001.
[Job97]Job B. Weissman, "Gallop: The Benefits of Wide-Area Computing for Parallel Processing", NSF ASC-9625000
[Hargras03]Tarek Hagras, Jan Janecek, "A Simple Scheduling Heuristic for Heterogeneous Computing Environments", Proceedings of the Second International Symposium on Parallel and Distributed Computing (ISPDC’03) 0-7695-2069-3/03 $ 17.00 © 2003 IEEE