臺灣博碩士論文加值系統

網格運算是目前較新興且主流的運算架構，透過網格運算平台應用分散在不同地理位置，且軟、硬體平台皆不盡相同的運算資源，來解決需要龐大運算量的計算問題。由於網格中參與工作計算的運算節點其平台的異質性。所以負載平衡對於高效能的網格運算環境是重要的。一個適當的負載平衡演算法能夠減少系統的回應時間及工作往返時間，進而增加系統整體的產出率。然而，如何找出一個最佳的負載平衡演算法是不容易的。我們將提出一個以模糊類神經網路為基礎的負載平衡演算法，以增進網格系統整體的運算效能。在論文中，我們應用模糊理論技術去評估網格系統中運算節點的系統負載情形，透過模糊理論對模糊資訊處理的特性，可以有效的區分運算節點之間的負載差異。然而，當影響系統負載的因子增多時，模糊系統中的歸屬函數，將越來越難用人工以經驗法則的方式手動設定，故我們也整合類神經網路技術自動微調模糊系統中歸屬函數的定義。為了驗證所提出之負載平衡演算法的效能，本論文亦實際以Globus Toolkit v4為網格中介軟體建構網格運算環境。並在網格運算環境上實作資源代理人軟體架構，透過資源代理人整合Globus Toolkit 和所提出之負載平衡演算法。再者，為了驗證所提方法的效能，我們採用NAS Grid Benchmarks (NGB)做為效能評估的工具。最後，在實驗結果也可發現，本篇論文所提之負載平衡演算法能夠有效的減少工作的往返時間，並且相較於前人所提方法之效能，系統整體的效能提升率達20%~25%，明顯的改善了網格系統的運算效能。

Grid computing is an emerging computing architecture that can solve massive computational problems by making use of large numbers of heterogeneous computers. Load balancing is an important issue in the high performance Grid computing environment. An appropriate load balancing algorithm can efficiently reduce the response time, turnaround time and further increase the throughput. However, finding an optimal grid load balancing algorithm is intractable. In this paper, we propose a high performance load balancing algorithm based on Fuzzy Neural Networks an attempt to resolve this problem. In the proposed algorithm, we apply the Fuzzy System technique to evaluate the grid system load status, and adopt the Neural Networks to automatically tune the membership functions. Since there are many factors that influence the system’s load circumstances; as the number of factors increase, it becomes very difficult to set up the system using general experience. We implemented a Fuzzy Neural Network scheduler based on Globus Toolkit v4 to verify the proposed load balancing algorithm performance. NAS Grid Benchmarks (NGB) was utilized to validate the performance of our load balancing approach. The experimental results show that our proposed algorithm can reduce the turnaround time and has better speed-up ratio than previous methods.

摘要 I
ABSTRACT II
目錄 III
圖目錄 V
表目錄 VII
第一章、 緖論 1
1.1 背景與動機 1
1.2 貢獻 2
1.3 論文架構 3
第二章、 相關研究 5
2.1 網格運算 5
2.2 GLOBUS TOOLKIT 9
2.3 負載平衡演算法 16
第三章、 相關技術與工具 23
3.1 模糊理論 23
3.2 模糊系統 25
3.3 類神經網路 28
3.4 NAS GRID BENCHMARKS 31
第四章、 系統設計 34
4.1 三層式網格運算環境 34
4.2 資源代理人軟體架構 35
4.3 負載平衡演算法 38
4.4 模糊神經網路演算法 43
第五章、 系統實作與實驗結果 46
5.1 硬體架構 46
5.2 工作執行流程 47
5.3 實驗環境 48
5.4 實驗結果討論 50
第六章、 結論與未來展望 56
參考文獻 58

[1] A visual tour of Open Grid Services Architecture (2007, August). Available: http://www.ibm.com/developerworks/library/gr-visual/index.html?S_TACT=105AGX52&S_CMP=cn-a-gr
[2] Ahn, H.-C., Youn, H.-Y., "A Fuzzy Grouping-Based Load Balancing for Distributed Object Computing Systems," International Conferences on Computational Science and Its Applications, 2005, pp. 916-925.
[3] Berman, F., Fox, G. and Hey, T., "Grid Computing: Making the Global Infrastructure a Reality," John Wiley & Sons, 2003.
[4] Cheung, L.-S., Kwok, Y.-K., "On Load Balancing Approaches for Distributed Object Computing Systems," The Journal of Supercomputing, Vol. 27, 2004, pp. 149-175.
[5] ChinaGrid (2007, August). Available: http://www.chinagrid.edu.cn/chinagrid/index.jsp
[6] Czajkowski, K., Fitzgerald, S., Foster, I., Kesselman, C., "Grid Information Services for Distributed Resource Sharing," 10th IEEE International Symposium on High-Performance Distributed Computing, 2001, pp. 181.
[7] Condor Project Homepage (2007, August). Available: http://www.cs.wisc.edu/condor/
[8] Dandamudi, S. -P., "Sensitivity evaluation of dynamic load sharing in distributed systems," IEEE Concurrency, Vol. 6, No. 3, 1998, pp. 62–72.
[9] Diskless Remote Boot in Linux (2007, August), Available: http://drbl.nchc.org.tw/
[10] EGEE > gLite (2007, August). Available: http://glite.web.cern.ch/glite/
[11] Elmroth, E., Tordsson, J., "A Grid Resource Broker Supporting Advance Reservations and Benchmark-Based Resource Selection," Lecture Notes in Computer Science (LNCS), Vol. 3732, 2006, pp. 1061-1070.
[12] Elmroth, E., Tordsson, J., "An interoperable, standards-based grid resource broker and job submission service," First International Conference on e-Science and Grid Computing, 2005, pp. 9.
[13] Foster, I., et al., "The Grid2003 Production Grid: Principles and Practice," IEEE International Symposium on High Performance Distributed Computing, 2004, pp. 236-245.
[14] Foster, I., Kesselman, C. and Tuecke, S., "The Anatomy of the Grid: Enabling Scalable Virtual Organizations," International Journal of Supercomputer Applications, Vol. 15, No. 3, 2001, pp. 200-222.
[15] Foster, I., Kesselman, C., "The Grid: Blueprint for a New Computing Infrastructure," Morgan Kaufmann, 1998.
[16] Foster, I., Kesselman, C., Nick, J., Tuecke, S., "Grid Services for Distributed System Integration," IEEE Computer, Vol. 35, Issue 6, 2002, pp. 37-46.
[17] Foster, I., Kesselman, C., Nick, J. and Tuecke, S., "The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration," Open Grid Service Infrastructure WG, Global Grid Forum, 2002.
[18] Foster, I., "The Grid: Computing without Bounds. Scientific American," Vol. 288, No. 4, 2003, pp. 78-85.
[19] Foster, I., Alpert, E., Chervenak, A., Drach, B., Kesselman, C., Nefedova, V., Middleton, D., Shoshani, A., Sim, A. and Williams, D., "The Earth System Grid II: Turning Climate Datasets Into Community Resources," Annual Meeting of the American Meteorological Society, 2002.
[20] GridBench: A tool for Grid Benchmarking. http://grid.ucy.ac.cy/gridbench/
[21] GT 4.0 WS GRAM Approach (2007, August). Available: http://www.globus.org/toolkit/docs/4.0/execution/wsgram/WS_GRAM_Approach.html
[22] Koyama, K., Shimizu, K., Ashihara, H., Zhang, Y., Kameda, H., "Performance Evaluation of Adaptive Load Balancing Policies in Distributed Systems," Proceedings of the Singapore International Conference on Networks/ International Conference on Information Engineering '93, 1993, pp. 606–611.
[23] Kwok, Y.-K., Cheung, L.-S., "A new fuzzy-decision based load balancing system for distributed object computing," Journal of Parallel and Distributed Computing, Vol. 64, 2004, pp. 238-253.
[24] Lin, A., Maas, P., Peltier, S. and Ellisman, M., "Harnessing the Power of the Globus Toolkit," ClusterWorld, Vol. 2, No. 1, 2004.
[25] Messina, P., "Distributed Supercomputing Applications. The Grid: Blueprint for a New Computing Infrastructure," Morgan Kaufmann, 1999, pp. 55-73.
[26] Montero, R.S., Huedo, E., Llorente, I.M., "Benchmarking of high throughput computing applications on Grids," Instituto Nacional de Te’cnica Aeroespacial "Esteban Terradas", 2006, pp. 267-279.
[27] NAS Grid Benchmarks (NGB) (2007, August). Available: http://www.nas.nasa.gov/Resources/Software/npb.html
[28] Network Weather Service: Introduction (2007, August). Available: http://nws.cs.ucsb.edu/ewiki/
[29] OASIS Web Services Resource Framework (WSRF) TC (2007, August). Available: http://www.oasis-open.org/committees/tc_home.php?wg_abbrev=wsrf
[30] Open Grid Services Architecture Data Access and Integration (OGSA-DAI) Project (2007, August). Available: http://www.ogsa-dai.org.uk.
[31] Portable Batch System (2007, August). Available: http://www.openpbs.org/
[32] SETI@home (2007, August). Available: http://setiathome.berkeley.edu/
[33] Shih, P.-C, "Design and Implementation of a Resource Broker with Network Performance Model on Grid Computing Environments," Master Thesis, Tunghai University, 2005.
[34] Song, E.-H., Jeon, Y.-S., Han, S.-K., Jeong, Y.-S., "Hierarchical and Dynamic Information Management Framework on Grid Computing," International Federation for Information Processing, 2006, pp. 151-161.
[35] Sotomayor, B., Childers, L., Globus Toolkit 4 Programming Java Services, 2006.
[36] Sun GridEngine (2007, August). Available: http://gridengine.sunsource.net/
[37] Taiwan UniGrid Project Portal Site (2007, August). Available: http://www.unigrid.org.tw/
[38] TeraGrid (2007, August). Available: http://www.teragrid.org/
[39] The DataGrid Project (2007, August). Available: http://eu-datagrid.web.cern.ch/eu-datagrid/
[40] The Globus Alliance (2007, August). Available: http://www.globus.org/
[41] World Wide Web Consortium (2007, August). Available: http://www.w3.org/
[42] Yagoubi, B., Slimani, Y., "Dynamic Load Balancing Strategy for Grid Computing," Transactions On Engineering, Computing And Technology 13, May 2006, pp. 260-265.
[43] Yan, K.-Q., Wang, S.-C., Chang, C.-P., Lin, J.-S., "A hybrid load balancing policy underlying grid computing environment," International Journal of Computer Standards & Interfaces 29, 2007, pp. 161-173.
[44] Yang, L.-A., "The Design and Implementation of a Dynamic Resource Broker Framework in a Grid Environment," Master Thesis, Chung Hua University, 2006.
[45] Zadeh, L.A., "Fuzzy Sets, Information and Control," 8, 1965, pp. 338-353.
[46] Zhang, X., Qu, Y., Xiao, L., "Improving Distributed Workload Performance by Sharing Both CPU and Memory Resources," Proceedings of the 20th Int'l Conf. Distributed Computing Systems, Apr. 2000, pp. 233–241.
[47] Zhou, J., Yu, K.-M., Chou, C.-H., Yang, L.-A., Luo, Z.-J., "A Dynamic Resource Broker and Fuzzy Logic Based Scheduling Algorithm in Grid Environment," accepted by the International Conference on Adaptive and Natural Computing Algorithms, Lecture Notes in Computer Science (LNCS), Springer-Verlag Heidelberg, 2007.
[48] Zurada, J.M., "Introduction to Artificial Neural Systems," West Publishing Company, New York, 1992.